首页 > 代码库 > 【读书笔记】《编程珠玑》第一章之位向量&位图

【读书笔记】《编程珠玑》第一章之位向量&位图

此书的叙述模式是借由一个具体问题来引出的一系列算法,数据结构等等方面的技巧性策略。共分三篇,基础,性能,应用。每篇涵盖数章,章内案例都非常切实棘手,解说也生动有趣。

自个呢也是头一次接触编程技巧类的书籍,而且算法数据结构方面的知识储备实在是薄弱,这么看来,纯粹找虐啊orz。今此行为,歇业养伤,实属无聊。也可说是自打毕业后,看书如打仗,自视身处“安安稳稳的和平年代”,闲来了也就闲着,忧患意识甚少,有也退退缩缩。话说回来,这本书不像CLRS那种难打的硬仗(现在想想都脑仁疼啊),《Programming Pearls》这么个好对手,排烦解闷也正好练练身手!

废话了一大堆,嘿嘿,看官轻拍。那下面就来看看第一章讲了些啥~

问题

怎样给一个最多包含1千万条记录且每条记录都是7位的整数的磁盘文件排序?

准确描述

这里书本对问题抽象出了精确的描述:

输入:一个最多包涵n个正整数的文件,每个数都小于n,其中n=10^7。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。

输出:按升序排列的输入整数的列表。

约束:最多有(大约)1MB的内存空间可用,有充足的磁盘存储空间可用。运行时间最多几分钟,运行时间为10秒就不需要进一步优化了。

解决方案

  1. 归并排序。联想下归并排序的缺点:需要O(n)的辅助空间,可知他必将多次的多写一块额外的工作文件or内存。优势:只需读取一次。劣势:需要数次操作额外文件。

  2. 分批读入数据,然后使用快速排序。每个整数用32位即4字节表示最多可表示带符号的2^31-1>9 999 999,计算10^7/(10^6/4)可得,40次读取排序可以达到目标。优势:快。劣势:多次读取数据,多趟算法。

  3. 使用位图数据结构。这个一个(10^7/32 + 1) 行 (32) 列的大表:

    31 30 ... 1 0
    31 30 ... 1 0
    ......
    31 30 ... 1 0
    31 30 ... 1 0

  如果数据是{2,3,5},那么第一行上就会是:0000 0000 0000 0000 0000 0000 0010 1100。很明显的,文件里所有的整数都可以在这张表里找到对应的位置,聪明如你,这就是一个大小为10^7/32 + 1的int[],具体的算法是这样的:

package chpt1;

import java.util.List;

/**
 * Created by wqi on 2016/10/22.
 */
public class BitSort  {
    // 位向量,也可称作位图,这里为了形象化,取作bitMap.
    private int[] bitMap;

    // i >> 5即每32个数为一组,也就是数组重的一个int元素。 i & 0x1f 相当于取该数对32取模,就找到了该数对应的位,|= 即为置1。
    private void set(int i) {
        this.bitMap[i >> 5] |= (1 << (i & 0x1f));
    }

    // 和set()本质上的区别就是 &= 将该数对应的位置0
    private void clr(int i) {
        this.bitMap[i >> 5] &= ~(1 << (i & 0x1f));
    }

    // 返回该数对应的位为1或为0
    private int test(int i) {
        return (this.bitMap[i >> 5] & (1 << (i & 0x1f)));
    }

    public void sort(List<Integer> list) {
        this.bitMap = new int[list.size() / 32 + 1];
        
        for (int i = 0; i < this.bitMap.length; i++) {
            clr(i);// 第一阶段将所有的位都置为0。
        }
        for (int i = 0; i < list.size(); i++) {
            set(list.get(i));// 第二阶段读入文件中的每个整数来建立集合,将每个对应的位都置为1。
        }
        for (int i = 0; i < list.size(); i++) {
            if (test(i) == 1){
                // 第三阶段检验每一位,如果该位为1,则输出这个数。
            }
        }
    }
}

优势:只需要读取一次文件数据,且不需要额外文件。而且使用的是基本的位操作,速度会更快。劣势:没有,这算法相当友好。

总结  

这一章在英文原版中名为 Cracking the Oyster ,直译为「美妙的(也可作开裂的)牡蛎」。和开篇概览中提到的『对实例研究的深入思考不仅很有趣,而且可以获得实际的益处』很贴切,牡蛎多鲜啊,pearls 的美也很直观的看到。再扯句题外话,貌似在西方国家 Oyster 这个词的意味是很好的,沙翁的台词中有 the world is my oyster 意译可表示成——我可以为所欲为啦。

位图这种数据抽象确实很有趣!巧妙的解决了这种看上去很乍乎的大数据问题。在网上也了解到,很多时候在处理大批量数据时,都可以考虑使用该数据结构,这点往后有待补充,希望在这再写几篇做到『举一隅,不以三隅反』。另外,针对位图这一数据概念,Java已经有操作起来非常简单的实现了,就是BitSet(),该集合类初始范围在0~63(JDK Version: 1.8.0_101),如果这时候BitSet().set(64),它会自动扩容至当前容量的翻倍,也就是*2,在这即0~127。

就先写到这,2016年10月22日16:56:01。课后习题部分是很依赖对前文的理解,且变化不是太大,书后答案代码部分大都是用C/C++写的,但只会Java的我看起来也不麻烦(看到qsort好羡慕C系的程序员啊),明天看看有没有有意思的题目再补充吧。#明日债明日还#

;-)

 

【读书笔记】《编程珠玑》第一章之位向量&位图