ITeye博客

深度学院

chiyx · 共 21 篇文章

SICP读书笔记-huffman编码的实现

huffman 编码是一种变长前缀式编码,通过利用被编码消息中符号的出现频率(频率出现越高的用越少的码),可以有效的节约空间。在 SICP 的2.3.4节通过实现一个huffman编码树来阐述通过表和数据抽象去操作集合和数的例子。 构建 huffman 编码树 huffman 树以表的方式来表示,将树分为 叶子节点*和 *非叶子节点 ('leaf symbol weight) : 叶子节点,包含标示叶子的符号'leaf, 实际字符 symbol,权重 weight (left right symbols weight): 非叶子节点, 包含左子树 left, 右子树 right, 实际字符表…

2014-03-30 22:52 · scheme · 评论(0)

数据结构之-跳跃表(skip list, scala版)

概述 SkipList 是由William Pugh发明的一种数据结构,它的作用类似平衡二叉树,对查找,删除,插入操作的时间复杂度为O(logN),是一种十分高效的查找结构。SkipList使用随机化的平衡方案取代了平衡二叉树的严格的平衡方案,因此它也是一种随机化的数据结构。SkipList基于并联的链表,是对有序的链表附加上随机个数的前进的链接,使得在查找过程中可以快速地跳过部分链表而得名。 如上图所示,a为普通的排好序的LinkList,在a中查找一个元素,最坏情况下,我们需要对比所有的节点,如果修改成如b那样,间隔的list中的元素加上指向前面第二个的元素指针,则查找一个元素最多需要【…

2013-09-03 10:42 · 算法 · 评论(0)

Bash-shell的启动文件

Linux系统用环境变量来在程序和脚本中标识它自己。这为你的程序提供了获得系统信息的一个简单方法。 问题是如何设置这些变量。 在你登陆Linux系统启动一个bash shell时,默认情况下bash在几个文件中查找并执行其中的命令。这些文 件称作启动文件。bash检查的启动文件取决于你启动bash shell的方式。启动bash shell有3种方式: 登陆时当做默认登陆shell 作为非登陆shell的交互式shell 作为运行脚本的非交互式shell 登陆shell 当你登陆Linux时,bash shell会作为登陆的shell启动。登陆shell会从4个不同的启动文件里读取命令下面是…

2013-06-14 22:37 · linux · 评论(0)

(转)配置多个git远程仓库的ssh-Key切换

转载地址:http://omiga.org/blog/archives/2269 目前的git仓库如github都是通过使用SSH与客户端连接,如果只是固定使用单个git仓库的单个用户 (first),生成生成密钥对后,将公钥保存至github,每次连接时SSH客户端发送本地私钥(默认~/.ssh/id_rsa)到服务端验证。单用户情况下,连接的服务器上保存的公钥和发送的私钥自然是配对的。 但是在实际工作中,一般公司内部都有自己的独立的git仓库(gitlab.xxx.com),于是就会存在这样的情 况,在github有私人的账号first,公司的gitlab中的工作账号sencord,fi…

2013-05-20 23:28 · 开发工具 · 评论(4)

python标准库学习系列2-真值测试

在python中任何对象都能被用于真值测试的表达式中,满足以下任意条件的对象的真值被认为是False: None False 数值对象中的0值,如0,0L,0.0,0j 空序列,如'',,() 空map,{} 用户自定义类型中,如果类中包含__nonzore__(),当该方法返回False时,或者类中含有__len__()方法,当该方法返回0时.

2013-04-06 15:58 · python · 评论(0)

python标准库学习系列1-BIFS

abs(x) 返回数值的绝对值,参数x为整形或者浮点型 all(iterable) 判断迭代器对象中的元素是否全为真,若是则返回真,等价代码如下: def all(iterable): for element in iterable: if not element: return False return True any(iterable) 判断迭代器对象中的元素是否有任意一个元素为真,若是则返回真。 basestring() str 和 unicode的超类,不能被实例化。但是可以用于判断一个对象是否是字符串型的,isinstance(obj, basestring)=isinstanc…

2013-04-06 00:18 · python · 评论(0)

数据结构之-红黑树的实现(C语言版)

二叉查找树的效率依赖于其高度,为O(h),普通的具有N个结点的二叉查找树树的高度落差会很大,极端情况下会出现h=n的情况(插入结点序列为排好序的情况下),这样二叉查找树就退化为一个列表了。于是就出现了平衡树的概念,它能保证树的高度h在lgn这个数量级上。 红黑树是许多“平衡树”中的一种,它确保没有一条路径比其他的路径长出2倍左右,因而是接近平衡的。 红黑树的数据结构和操作定义如下: /*file:RBTree.h*/ #ifndef CHIYX_RBTREE_ #define CHIYX_RBTREE_ #ifndef NULL #define NULL 0 #endif #define B…

2012-08-26 00:30 · 算法 · 评论(1)

数据结构之-二叉查找树的实现(C语言版)

修正:前驱与后继操作有误,修正 二叉查找树是满足如下性质的二叉树: 设x为二叉树中的一个结点,如果y是x的左子树中的一个结点,则key<=key 如果y是x的右子树,则key<=key 二叉查找树的数据结构和操作定义如下: /*file:biTree.h*/ #ifndef CHIYX_BITREE #define CHIYX_BITREE #ifndef NULL #define NULL 0 #endif typedef int DataType; //二叉树的节点结构 typedef struct BiTreeNode { DataType data; struct BiTreeNod…

2012-08-11 00:32 · 算法 · 评论(1)

常用排序算法的实现(C语言版)-基数排序

基数排序: #include <stdlib.h> #include "algosort.h" /*被排序元素的最大位数,4则意味着只能排序< 10000 的数*/ #define WIDTH 4 #define MAXK 10 //位数划分基于的基数,10表示为10进制划分 void radixSort(int a[], int n) { int i; void innerCountingSort(int a[], int n, int d); for (i = 0; i < WIDTH; i++) { innerCountingSort(a, n, i); } } void innerC…

2012-08-01 22:14 · 算法 · 评论(0)

常用排序算法的实现(C语言版)-快速排序

快速排序: /* *将r位置中的位置移动到正确位置q上,并返回q,使得在a[p]..a[q-1] < a[q], a[q+1]..a[r] > a[q] */ int partition(int a[], int p, int r); void qSort(int a[], int p, int r); void quickSort(int a[], int n) { qSort(a, 0, n - 1); } void qSort(int a[], int p, int r) { int q; while (p < r) { q = partition(a, p, r); qSort(a,…

2012-08-01 22:08 · 算法 · 评论(0)

常用排序算法的实现(C语言版)-堆排序

堆排序: /** *排序过程中使用到的堆的结构 */ typedef struct heap { int heapSize; int *ap; int apLength; } Heap; /* *调整i位置上的元素,以保持最大堆的性质 */ void maxHeapify(int a[], int i, int hSize) { int l, r, largest; l = 2 * i + 1; r = l + 1; if (l < hSize && a[l] > a[i]) { largest = l; } else { largest = i; } if (r < hSize && a[…

2012-08-01 22:01 · 算法 · 评论(0)

不一样的二分查找-只比较一次的2分查找实现

正常进行2次比较的二分查找实现,取列表中点值,(1)先比较x是否小于v,若小于则说明在mid的左侧,(2)继续比较x是否大于v,若大于则说明在mid的右侧 (3)否则mid即为x的位置 int binsearch(int x, int v[], int n) { int low, high, mid; low = 0; high = n - 1; while(low <= high) { mid = low + high; if (x < v[mid]) { high = mid - 1; } else if (x > v[mid]) { low = mid + 1; }else { ret…

2012-07-11 00:49 · 算法 · 评论(0)

Spring AOP中JoinPoint的表达式定义描述

在使用Spring AOP的过程中,经常需要使用到各种不同的JoinPoint的定义,Spring AOP遵循了AspectJ形式的JoinPoint的定义形式,但是Spring目前只支持部分的AspectJ形式的Joinpoint的定义,同时Spring AOP只支持方法级别的JoinPoint。以下是我在学习Spring开发者手册时总结的一些JoinPoint的定义,不完整,欢迎补充。 |execution |方法签名需要满足execution中描述的方法签名| |within |包或者类型满足within中描述的包或者类型的类的所有非私有方法| |this |Spring AOP 的代…

2012-06-26 23:37 · JAVA · Spring · 评论(0)

HIVE中row_number函数的描述与使用场景

假设一个场景:存在表user_score,该表的数据如下 |id|rate|score| |1|'0-4'|10| |2|'0-4'|40| |3|'0-4'|30| |4|'0-4'|20| |5|'5-10'|10| |6|'5-10'|40| |7|'5-10'|30| |8|'5-10'|20| |9|'11-20'|10| |10|'11-20'|40| |11|'11-20'|30| |12|'11-20'|20| 现在要求用一条查询语句取出每种rate下score最大的两条记录,也就算取出id为:2,3,6,7,10,11的记录,要求分别给出SQL和HIVESQL的查询语句 以…

2012-06-12 23:37 · HIVE · 评论(2)

Hive对形如f(column)进行分组的两种办法

在使用HIVE时,如果某个列应用了某个函数并使用如f(col) 重新命名列f(col) as fc, 对想基于fc直接直接group by时,如: select f(col) as fc, count(*) from table_name group by fc HIVE是不支持的,运行该语句会报错。 可以使用以下的两种方式来达到相同的目的: (1)使用子查询 select sq.fc, count(*) from (select f(col), col from tableName) sq group by sq.fc (2)不使用别名进行分组 select f(col) as fc, c…

2012-06-04 18:53 · HIVE · 评论(0)