标签归档:算法

整数的可变字节编码压缩算法

在各个平台中整数占用的字节数一直比较固定,通常是4个字节。它的表示的整数范围是-2147483648~2147483647。然而对于一些数值较小的整数,因为有大量的位数是前导0,这些比特在数值的表示中是没有意义的,仍旧花费4个字节去存储则显得有些浪费。这里的一篇文章『Variable byte codesd』,讲述正整数的可变字节编码的压缩,它可以在需要存储大量正整数的情况下有着较为实际的应用。

正整数可变字节编码压缩算法的思路是:
将每个字节分为2个部分:低7位为负载位(payload),用于存储数值,最高位为标志位(continuation bit),取值0或者1,用于标识当前字节是否是该整数在可变字节编码中的最后一个字节。

例如正整数130,它的二进制表示(4字节,共32位)为:00000000 00000000 00000000 10000010。经过可变字节编码压缩之后,130可压缩为2个字节:
Byte0: 0 0000010
Byte1: 1 0000001
Byte0的最高位为0,表示该字节并不是最后一个字节,低7位存储原比特流中的低7位。Byte1的最高位为1,表示该字节已经是最后一个字节,低7为存储原比特流中的第8位-第14位。舍弃原比特流中的所有前导0。

整数可变字节编码压缩算法的Java实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * 对正整数列表进行可变字节编码,返回压缩后的字节数组。
 * @param intList
 * @return
 */
private static List<Byte> intToByte(List<Integer> intList) {
    List<Byte> list = new ArrayList<Byte>();
    if (intList == null) {
        return null;
    }
    for (int n : intList) {
        //遍历列表中的每个正整数。
        while (n > 0) {
            int byteOf = n % 128; //得到正整数的低7位。
            if (n < 128) {
                //如果n值已经能由7位表示,则该字节是最后一个字节。
                byteOf += 128; //将该字节的最高位置为1。
                list.add((byte) byteOf);
                break; //当前整数的可变字节编码结束。
            } else {
                list.add((byte) byteOf);
            }
            n /= 128;
        }
    }
    return list;
}
 
/**
 * 将可变字节编码形式存储的字节数组还原为正整数列表。
 * @param byteList
 * @return
 */
private static List<Integer> byteToInt(List<Byte> byteList) {
    List<Integer> list = new ArrayList<Integer>();
    int n = 0;
    int byteStartPerInt = 0;
    for (int i = 0; i < byteList.size(); i++) {
        //依次读取字节数组。
        if (byteList.get(i) >= 0) {
            //如果当前字节的值大于0,则表示最高位是0,该字节不是最后的字节。
            n += byteList.get(i) * Math.pow(128, i - byteStartPerInt);
        } else {
            //如果当前字节的值小于0,则表示最高位是1,该字节是最后的字节。
            n += (byteList.get(i) + 128) * Math.pow(128, i - byteStartPerInt);
            list.add(n);
            n = 0;
            byteStartPerInt = i + 1;
        }
    }
    return list;
}

经过简单的测试,随机生成1w个值为1-105之间的正整数,上述算法的压缩比约为0.29。也就是说,本来需要4w个字节存储的整数现在只需要2.8w左右的存储空间。随着测试数据的值越大,压缩率会变小,而当测试数据的值越小,压缩率会变大。极端情况下,上述算法的压缩率最大能达到75%。

由于可变字节编码压缩算法是建立在标识位的基础上的,因此,当待编码的正整数大于1284时(针对4个字节表示整数的情况),算法会失去作用,非但不能压缩,反而会引起数据膨胀,这也是该算法的最大缺陷。另外,如果对待编码正整数的顺序没有要求的话,可以先对整数列表排序,然后存储相邻两个正整数之间的差值,通过这样的操作之后,待编码的整数就以“差值”的形式变小了,从而提高压缩率。

--EOF--

单链表快速排序算法

快速排序的算法思想是:确定一个枢轴元素,通过一趟排序将待排关键字分成两个部分,其中一部分元素均比枢轴元素小,另一部分元素均比枢轴元素大,这样的一趟排序称为快速排序的一次划分。再对两个部分分别再递归进行划分操作,最后获得的序列就是排好序的关键字序列。可见,快速排序的性能与枢轴元素的选取有关,快排的时间复杂度在最好、最坏、平均的情况下分别为:O(nlog2n)、O(n2)和O(nlog2n),空间复杂度在最好、最坏、平均情况下分别为:O(log2n)、O(n)和O(log2n),快排的C++实现和效率分析见『六种基本内部排序算法的C++实现』『六种基本内部排序算法效率分析』

上述快排算法的实现中采用的存储结构是数组,采用数组有一个好处,就是待排元素可以随机存取。而以单链表方式存储的待排序列就无法随机存取元素了,其实根据快排思想,稍作改动,对单链表的快速排序算法也能实现。

因为快排最核心的思想就是划分,确定一个枢轴元素(pivot),每一趟划分的目的就是把待排序列分为两部分,前一部分比枢轴小(序列A),后一部分比枢轴大(序列B)。经过一趟划分之后序列变为:{A} pivot {B}。以下是具体步骤:
1、确定每一次划分的枢轴元素为当前待排序列的头节点。
2、设置Slow和Fast两个游标,Slow指向序列A中的最后一个元素,初始化为枢轴本身(待排序列头节点)。让Fast遍历一遍待排序列,当所指元素比枢轴小时,将Slow往前游一格,交换Slow和Fast所指元素的值,这样仍能保证Slow指向的元素是序列A中的最后一个元素。
3、交换Slow所指元素和枢轴元素的值。
4、对序列A和B重复步骤1~4。

下面是单链表快速排序算法的Java实现:
1、单链表节点的定义。

1
2
3
4
5
/* 单链表节点 */
class Element {
    public int     data;
    public Element next;
}

2、单链表的快排算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
 * @param ListHead 待排序列的头节点
 * @param ListEnd 待排序列的尾节点
 */
public static void qsort(Element ListHead, Element ListEnd) {
    if (ListHead == null || ListEnd == null)
        return;
    if (ListHead == ListEnd) {
        return;
    }
    //Slow游标,指向序列A的最末尾元素。
    Element Slow = ListHead;
    //Fast游标,用于遍历整个待排序列。
    Element Fast = ListHead.next;
    //TempEnd游标,总是指向Slow游标的前驱节点,递归调用时需要。
    Element TempEnd = ListHead;
    int temp;
    while (Fast != null) {
        //当前节点的值比枢轴小,进行交换。
        if (Fast.data < ListHead.data) {
            //TempEnd游标总是指向Slow的前驱。
            TempEnd = Slow;
            Slow = Slow.next;
 
            //交换Slow和Fast游标所指的元素的值
            temp = Slow.data;
            Slow.data = Fast.data;
            Fast.data = temp;
        }
        Fast = Fast.next;
    }
 
    //交换Slow游标所指的元素和枢轴元素的值,使序列成为{A} povit {B}形式
    temp = ListHead.data;
    ListHead.data = Slow.data;
    Slow.data = temp;
 
    //递归调用
    qsort(ListHead, TempEnd);
    qsort(Slow.next, ListEnd);
}

--EOF--

Fibonacci数列的O(log2n)解法

Fibonacci数列(斐波那契数列)用递归实现最符合其定义要求,但是计算机实现起来的时间复杂度为O(2n)。改进一点的做法是通过一个O(n)的空间换取时间复杂度为O(n)的非递归计算方法。更好一些的方法就是通过Fibonacci数列的递归公式构建出一个矩阵方程,通过对矩阵方程的代数运算,可以在O(log2n)时间复杂度内得到任意第n个Fibonacci数列中数字。

由Fibonacci数列公式F(n+1) = F(n) + F(n-1),我们可以构建出下列的矩阵方程:

由此可以推导出:

因为F(0)=1,F(1)=1是已知的,所以只要求出矩阵(1, 1, 1, 0)n的值,那么F(n)值也就知道了。

对于两个数的乘方,我们可以用分而治之在O(log2n)的时间复杂度内求得,将它运用在矩阵计算中也是一样的。如下:

程序中只需先定义两个矩阵的乘法,然后便可以递归求得Mn的值。

1、首先定义矩阵类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * | m00 m01 |
 * | m10 m11 |
 */
class Matrix {
    public long m00;
    public long m01;
    public long m10;
    public long m11;
 
    public Matrix(long m00, long m01, long m10, long m11) {
        this.m00 = m00;
        this.m01 = m01;
        this.m10 = m10;
        this.m11 = m11;
    }
}

2、定义矩阵乘法

1
2
3
4
5
6
7
public static Matrix multiplyMatrix(Matrix m1, Matrix m2) {
    return new Matrix(
        m1.m00 * m2.m00 + m1.m01 * m2.m10, 
        m1.m00 * m2.m01 + m1.m01 * m2.m11,
        m1.m10 * m2.m00 + m1.m11 * m2.m10, 
        m1.m10 * m2.m01 + m1.m11 * m2.m11);
}

3、对矩阵M进行n次幂运算

1
2
3
4
5
6
7
8
9
10
11
12
13
public static Matrix calculate(int n) {
    if (n == 1) {
        return new Matrix(1, 1, 1, 0);
    }
    if (n % 2 == 0) { //n为偶数
        Matrix m = calculate(n / 2);
        return multiplyMatrix(m, m);
    } else { //n为奇数
        Matrix m = calculate((n - 1) / 2);
        m = multiplyMatrix(m, m);
        return multiplyMatrix(m, new Matrix(1, 1, 1, 0));
    }
}

这样,求解第n个Fabonacci数列中数字的问题就被转化成为矩阵(1, 1, 1, 0)的n次幂运算,时间复杂度降为O(log2n)。

完整代码参见这里

Reference:
[1] Fibonacci Sequence. Wikipedia. 2011-10-21 accessed.

--EOF--

在一个有序数组中查找给定数

题目要求为在一个有序数组中查找一个给定值的数,这个数组是升序还是降序未知。这样就比普通的二分查找要多一步骤,用于判定该数组是升序还是降序,其余就跟普通二分查找一样了。

详见代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/***
 * args:	IN num[]: 有序数组
 *		IN start: 起始下标
 *		IN end: 终点下标
 *		IN value: 待查数值
 *		OUT pos: 待查数值下标
 * return:	true:命中 false:未命中
 */
bool binary_search(int num[], int start, int end, int value, int& pos)
{
    int order = 1; //顺序标记,默认升序
 
    if (num[start] > num[end-1])
    {
        order = 0; //逆序
    }
 
    while (start <= end)
    {
        int mid = (start+end)/2;
 
        if(num[mid] == value){
            pos = mid;
            return true;
        }else{
            if (order == 1) //如果是升序数组
            {
                if (value < num[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } 
            else //如果是降序数组
            {
                if (value < num[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
    }
 
    return false;
}

--EOF--

二叉树遍历的非递归实现

二叉树的定义是递归的,因此要遍历二叉树,用递归方法最为简便和直观,但是,二叉树的遍历也可以用非递归方法实现。

 一、非递归前序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 前序遍历二叉树  非递归法
 * @param root
 */
public static void preOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            System.out.print(root.getValue());
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.pop();
            root = root.getrChild();
        }
    }
}
 二、非递归中序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 中序遍历二叉树  非递归法
 * @param root
 */
public static void inOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.pop();
            System.out.print(root.getValue());
            root = root.getrChild();
        }
    }
}
 三、非递归后序遍历二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 后序遍历二叉树  非递归法
 * @param root
 */
public static void postOrderNoRecusive(BTree root) {
    Stack<BTree> s = new Stack<BTree>();
    while (root != null || !s.empty()) {
        while (root != null) {
            s.push(root);
            root = root.getlChild();
        }
        if (!s.empty()) {
            root = s.peek();
            if (root.getTag() == false) {
                root.setTag(true);
                root = root.getrChild();
            } else {
                System.out.print(root.getValue());
                s.pop();
                root = null;
            }
        }
    }
}

非递归的后序遍历与前两者有些不同,它需要在二叉树的定义中加入一个tag标签,初始为false,只有当一个节点的右孩子已经遍历过之后,才将它置为true,表示下次可以访问它并输出值了。

附件提供的源代码是二叉树前序、中序、后序遍历的递归和非递归算法,以及一个层序遍历的Java实现:源代码

--EOF--