40亿个数中快速查找

题目描述

给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

分析与解法

海量数据处理往往会很有趣，有趣在什么地方呢？

• 空间，available的内存不够，需要反复交换内存
• 时间，速度太慢不行，毕竟那是海量数据
• 处理，数据是一次调用还是反复调用，因为针对时间和空间，通常来说，多次调用的话，势必会增加预处理以减少每次调用的时候的时间代价。

解法一

咱们回到眼前要解决的这个问题，1个unsigned int占用4字节，40亿大约是4G个数，那么一共大约要用16G的内存空间，如果内存不够大，反复和硬盘交换数据的话，后果不堪设想。

那么怎么储存这么多的数据呢？还记得伴随数组么？还是那种思想，利用内存地址代替下标。

先举例，在内存中应该是1个byte=8bit，那么明显有

0 = 0000 0000

255 = 1111 1111

69 = 0100 0101

那么69可以表示0.2.6三个数存在，其余的7以下的数不存在，0表示0-7都不存在，255表示0-7都存在，这就是位图算法：通过全部置0，存在置1，这样一种模式来通过连续的地址存贮数据，和检验数据的方法。

那么1个 unsigned int代表多少个数呢？1个unsigned int 是一个2^32以内的数，那么也就是这样的1个数，可以表示32个数是否存在。同理申请一个unsigned int的数组a[n]则可以表示连续的 n*32的数。也就是a[0]表示0-31的数是否存在，a[1]表示32-63的数是否存在，依次类推。

这时候需要用多大的内存呢？

16G/32=512M

512M和16G之间的区别，却是是否一个32位寻址的CPU能否办得到的事儿了，众所周知，32位CPU最大寻址不超过4G，固然，你会说，现在都是64位的CPU之类的云云，但是，对于底层的设计者来说，寻址范围越小越好操控的事实是不争的。

问题到这里，其实基本上已经完事了，判断本身，在位图算法这里就是找到对应的内存位置是否为1就可以了。

解法二

当然，下面就要开始说一说，当数据超出了可以接受的范围之后的事情了。比如， 2^66范围的数据检索，也会是一个问题

4倍于64位CPU寻址范围，如果加上CPU本身的偏移寄存器占用的资源，可能应该是6-8个64位CPU的寻址范围，如果反复从内存到硬盘的读写，过程本身就是可怕的。

算法，更多的是用来解决瓶颈的，就想现在，根本不用考虑内存超出8M的问题，但是20年前，8086的年代，内存4M，或者内存8M，你怎么处理?固然做软件的不需要完全考虑摩尔定律，但是摩尔定律绝对是影响软件和算法编写者得想法的。

再比如，乌克兰俄罗斯的一批压缩高手，比如国内有名的R大，为什么压缩会出现？就是因为，要么存不下，要么传输时间过长。网络再好，64G的高清怎么的也得下遍历n个元素取出等概率载个一段时间吧。海量数据处理，永远是考虑超过了当前硬件条件的时候，该怎么办？！

那么我们可以发现一个更加有趣的问题，如果存不下，但是还要存，怎么办！

压缩！这里简单的说一嘴，无损压缩常见的为Huffman算法和LZW(Lenpel-Ziv &Welch)压缩算法，前者研究不多，后者却经常使用。

因为上面提到了位图算法，我就用常见的位图类的数据举例：

以下引自我的摘抄出处忘记了，请作者见谅：

对原始数据ABCCAABCDDAACCDB进行LZW压缩

原始数据中，只包括4个字符(Character),A,B,C,D,四个字符可以用一个2bit的数表示，0-A,1-B,2-C,3-D,从最直观的角度看，原始字符串存在重复字符：ABCCAABCDDAACCDB，用4代表AB,5代表CC，上面的字符串可以替代表示为:45A4CDDAA5DB,这样是不是就比原数据短了一些呢！

问题扩展

为了区别代表串的值(Code)和原来的单个的数据值(String)，需要使它们的数值域不重合，上面用0-3来代表A-D,那么AB就必须用大于3的数值来代替，再举另外一个例子，原来的数值范围可以用8bit来表示，那么就认为原始的数的范围是0～255，压缩程序生成的标号的范围就不能为0～255（如果是0-255，就重复了）。只能从256开始，但是这样一来就超过了8位的表示范围了，所以必须要扩展数据的位数，至少扩展一位，但是这样不是增加了1个字符占用的空间了么？但是却可以用一个字符代表几个字符，比如原来255是8bit,但是现在用256来表示254，255两个数，还是划得来的。从这个原理可以看出LZW算法的适用范围是原始数据串最好是有大量的子串多次重复出现，重复的越多，压缩效果越好。反之则越差，可能真的不减反增了。

伪代码如下

  STRING = get input character
  WHILE there are still input characters DO
    CHARACTER = get input character
    IF STRING+CHARACTER is in the string table then
      STRING = STRING+character
    ELSE
      output the code for STRING
      add STRING+CHARACTER to the string table
      STRING = CHARACTER
    END of IF
  END of WHILE
  output the code for STRING

看过上面的适用范围再联想本题，数据有多少种，根据同余模的原理，可以惊人的发现，其实真的非常适合压缩，但是压缩之后，尽管存下了，在查找的时候，势必又需要解码，那么又回到了我们当初学习算法时的那句经典话，算法本身，就是为了解决时间和空间的均衡问题，要么时间换空间，要么空间换时间。

更多的，请读者自行思考，因为，压缩本身只是想引起读者思考，已经是题外话了~本部分完—上善若水.qinyu。