posts - 200, comments - 8, trackbacks - 0, articles - 0

程序员编程艺术-----第十一 ~ 十四章-----海量整数处理、蓄水池抽样、回文

Posted on 2013-05-15 21:37 鑫龙 阅读(271) 评论(0)  编辑 收藏 引用 所属分类: JULY_程序员编程艺术

       程序员编程艺术第十二~十五章：中签概率，IP访问次数，回文等问题（初稿）

作者：上善若水.qinyu，BigPotato，luuillu，well，July。编程艺术室出品。

前言

    本文的全部稿件是由我们编程艺术室的部分成员：上善若水.qinyu，BigPotato，luuillu，well，July共同完成，共分4个部分，即4道题：

  • 第一部分、从一道题，漫谈数据结构、以及压缩、位图算法，由上善若水.qinyu完成，
  • 第二部分、遍历n个元素取出等概率随机取出其中之一元素，由BigPotato完成，
  • 第三部分、提取出某日访问百度次数最多的那个IP，由luuillu完成，
  • 第四部分、回文判断，由well完成。全文由July统稿完成。

    由于本人在这周时间上实在是过于仓促，来不及过多整理，所以我尽量保持上述我的几位伙伴的原话原文，基本没做多少改动。因此，标明为初稿，以后会更加详尽细致的进行修补完善。

    前十一章请见这：程序员编程艺术第一~十章集锦与总结。吾以咱们编程艺术室的朋友为傲，以能识尽天下各路朋友为傲，以诸君为傲。

第一部分、从一道题，漫谈数据结构、以及压缩、位图算法

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

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

题目如下

7、腾讯面试题：给40亿个不重复的unsignedint的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

分析：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+1)*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位U的寻址范围，如果反复从内存到硬盘的读写，过程本身就是可怕的。

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

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

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

    压缩！这里简单的说一嘴，无损压缩常见的为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,这样是不是就比原数据短了一些呢！

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

伪代码如下

1 STRING = get input character
 2 WHILE there are still input characters DO
 3     CHARACTER = get input character
 4     IF STRING+CHARACTER is in the string table then
 5         STRING = STRING+character
 6     ELSE
 7         output the code for STRING
 8         add STRING+CHARACTER to the string table
 9         STRING = CHARACTER
10     END of IF
11 END of WHILE
12 output the code for STRING 

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

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

第二部分、遍历n个元素取出等概率随机取出其中之一元素

问题描述

1．一个文件中含有n个元素，只能遍历一遍，要求等概率随机取出其中之一。

    先讲一个例子，5个人抽5个签，只有一个签意味着“中签”，轮流抽签，那么这种情况，估计这5个人都不会有异议，都觉得这种方法是公平的，这确实也是公平的，“抓阄”的方法已经有很长的历史了，要是不公平的话老祖先们就不干了。

    或许有人觉得先抓的人中签的概率会大一些，因为要是前面的人中了，后面的中签概率就是0了，也可能有人会觉得后面抓的人更有优势，因为前面拿去了不中的签，后面中签的概率就大，那么我们就计算一下吧。

问题分析

    第一个人中签的概率是1/5,

    第二个人中签的情况只能在第一个人未中时才有可能，所以他中的概率是4/5 X 1/4 = 1/5（4/5表示第一个人未中，1/4表示在剩下的4个签里中签的概率），所以，第二个人最终的中签概率也是1/5，

    同理，第三个人中签的概率为：第一个人未中的概率X 第二个人未中的概率X第三个人中的概率，即为：4/5 X 3/4 X 1/3 = 1/5，

    一样的可以求出第四和第五个人的概率都为1/5，也就是说先后顺序不影响公平性。

    说这个问题是要说明这种前后有关联的事件的概率计算的方式，我们回到第1个问题。前几天我的一个同学电面百度是被问到这个问题，他想了想回答说，依次遍历，遇到每一个元素都生成一个随机数作为标记，如果当前生成的随机数大于为之前保留的元素生成的随机数就替换，这样操作直到文件结束。

    但面试官问到：如果生成的随机数和之前保留的元素的随机数一样大的话，要不要替换呢？

    你也许会想，一个double的范围可以是-1.79E+308 ~ +1.79E+308，要让两个随机生成的double相等的概率不是一般的微乎其微啊！但计算机世界里有条很让人伤心的“真理”：可能发生的事件，总会发生！

    那我们遇到这种情况，是换还是不换？To be or not to be， that’s a question！

    就好比，两个人百米赛跑，测出来的时间一样，如果只能有一个人得冠军的话，对于另一个人始终是不公平的，那么只能再跑一次，一决雌雄了！

我的策略

    下面，说一个个人认为比较满足要求的选取策略：

  •  顺序遍历，当前遍历的元素为第L个元素，变量e表示之前选取了的某一个元素，此时生成一个随机数r，如果r%L == 0(当然0也可以是0~L-1中的任何一个，概率都是一样的), 我们将e的值替换为当前值，否则扫描下一个元素直到文件结束。

    你要是给面试官说明了这样一个策略后，面试官百分之一千会问你这样做是等概率吗？那我们来证明一下。

证明

     在遍历到第1个元素的时候，即L为1，那么r%L必然为0，所以e为第一个元素，p=100%，

    遍历到第2个元素时，L为2，r%L==0的概率为1/2, 这个时候，第1个元素不被替换的概率为1X(1-1/2)=1/2,

     第1个元素被替换，也就是第2个元素被选中的概率为1/2 = 1/2,你可以看到，只有2时，这两个元素是等概率的机会被选中的。

    继续，遍历到第3个元素的时候，r%L==0的概率为1/3，前面被选中的元素不被替换的概率为1/2 X (1-1/3)=1/3,前面被选中的元素被替换的概率，即第3个元素被选中的概率为1/3

    归纳法证明，这样走到第L个元素时，这L个元素中任一被选中的概率都是1/L，那么走到L+1时，第L+1个元素选中的概率为1/(L+1), 之前选中的元素不被替换，即继续被选中的概率为1/L X ( 1-1/(L+1) ) = 1/(L+1)。证毕。

    也就是说，走到文件最后，每一个元素最终被选出的概率为1/n， n为文件中元素的总数。好歹我们是一个技术博客，看不到一丁点代码多少有点遗憾，给出一个选取策略的伪代码，如下：

伪代码

Element RandomPick(file):

Int length = 1;

While( length <= file.size )

   If( rand() % length == 0)

        Picked = File[length];

   Length++;

Return picked

    近日，看见我的一些同学在他们的面经里面常推荐结构之法算法之道这个博客，感谢东南大学计算机学院即将找工作的同学们对本博的关注，欢迎批评指正！--BigPotato。

第三部分、提取出某日访问百度次数最多的那个IP

问题描述：海量日志数据，提取出某日访问百度次数最多的那个IP。

方法: 计数法

    假设一天之内某个IP访问百度的次数不超过40亿次,则访问次数可以用unsigned表示.用数组统计出每个IP地址出现的次数,  即可得到访问次数最大的IP地址.

    IP地址是32位的二进制数,所以共有N=2^32=4G个不同的IP地址, 创建一个unsigned count[N];的数组,即可统计出每个IP的访问次数,而sizeof(count) == 4G*4=16G, 远远超过了32位计算机所支持的内存大小,因此不能直接创建这个数组.下面采用划分法解决这个问题.

    假设允许使用的内存是512M,  512M/4=128M 即512M内存可以统计128M个不同的IP地址的访问次数.而N/128M =4G/128M = 32 ,所以只要把IP地址划分成32个不同的区间,分别统计出每个区间中访问次数最大的IP, 然后就可以计算出所有IP地址中访问次数最大的IP了.

    因为2^5=32, 所以可以把IP地址的最高5位作为区间编号, 剩下的27为作为区间内的值,建立32个临时文件,代表32个区间,把相同区间的IP地址保存到同一的临时文件中.

例如:

ip1=0x1f4e2342

ip1的高5位是id1  =  ip1 >>27 = 0x11 = 3

ip1的其余27位是value1  =  ip1 &0x07ffffff = 0x074e2342

所以把 value1 保存在tmp3文件中.

由id1和value1可以还原成ip1, 即 ip1 =(id1<<27)|value1

    按照上面的方法可以得到32个临时文件,每个临时文件中的IP地址的取值范围属于[0-128M),因此可以统计出每个IP地址的访问次数.从而找到访问次数最大的IP地址

程序源码:

test.cpp是c++源码.

  1. #include <fstream>  
  2. #include <iostream>  
  3. #include <ctime>  
  4.   
  5. using namespace std;  
  6. #define N 32           //临时文件数  
  7.   
  8. #define ID(x)  (x>>27)                 //x对应的文件编号  
  9. #define VALUE(x) (x&0x07ffffff)        //x在文件中保存的值  
  10. #define MAKE_IP(x,y)  ((x<<27)|y)      //由文件编号和值得到IP地址.  
  11.   
  12. #define MEM_SIZE  128*1024*1024       //需分配内存的大小为 MEM_SIZE*sizeof(unsigned)     
  13.   
  14. char* data_path="D:/test/ip.dat";        //ip数据  
  15.   
  16.  //产生n个随机IP地址  
  17. void make_data(const int& n)         
  18. {  
  19.     ofstream out(data_path,ios::out|ios::binary);  
  20.     srand((unsigned)(time(NULL)));  
  21.     if (out)  
  22.     {  
  23.         for (int i=0; i<n; ++i)  
  24.         {  
  25.             unsigned val=unsigned(rand());           
  26.             val = (val<<24)|val;              //产生unsigned类型的随机数  
  27.   
  28.             out.write((char *)&val,sizeof (unsigned));  
  29.         }  
  30.     }  
  31. }  
  32.   
  33. //找到访问次数最大的ip地址  
  34. int main()  
  35. {  
  36.     //make_data(100);     //   
  37.     make_data(100000000);       //产生测试用的IP数据  
  38.     fstream arr[N];  
  39.       
  40.     for (int i=0; i<N; ++i)                 //创建N个临时文件  
  41.     {  
  42.         char tmp_path[128];     //临时文件路径  
  43.         sprintf(tmp_path,"D:/test/tmp%d.dat",i);  
  44.         arr[i].open(tmp_path, ios::trunc|ios::in|ios::out|ios::binary);  //打开第i个文件  
  45.   
  46.         if( !arr[i])  
  47.         {  
  48.             cout<<"open file"<<i<<"error"<<endl;  
  49.         }  
  50.     }  
  51.   
  52.     ifstream infile(data_path,ios::in|ios::binary);   //读入测试用的IP数据  
  53.     unsigned data;  
  54.   
  55.     while(infile.read((char*)(&data), sizeof(data)))  
  56.     {  
  57.         unsigned val=VALUE(data);  
  58.         int key=ID(data);  
  59.         arr[ID(data)].write((char*)(&val), sizeof(val));           //保存到临时文件件中  
  60.     }  
  61.   
  62.     for(unsigned i=0; i<N; ++i)  
  63.     {  
  64.         arr[i].seekg(0);  
  65.     }  
  66.     unsigned max_ip = 0;    //出现次数最多的ip地址  
  67.     unsigned max_times = 0;     //最大只出现的次数  
  68.   
  69.     //分配512M内存,用于统计每个数出现的次数  
  70.     unsigned *count = new unsigned[MEM_SIZE];    
  71.   
  72.     for (unsigned i=0; i<N; ++i)  
  73.     {  
  74.         memset(count, 0, sizeof(unsigned)*MEM_SIZE);  
  75.   
  76.         //统计每个临时文件件中不同数字出现的次数  
  77.         unsigned data;  
  78.         while(arr[i].read((char*)(&data), sizeof(unsigned)))       
  79.         {  
  80.             ++count[data];  
  81.         }  
  82.           
  83.         //找出出现次数最多的IP地址  
  84.         for(unsigned j=0; j<MEM_SIZE; ++j)                             
  85.         {  
  86.             if(max_times<count[j])             
  87.             {  
  88.                 max_times = count[j];  
  89.                 max_ip = MAKE_IP(i,j);        // 恢复成原ip地址.  
  90.             }  
  91.         }  
  92.     }  
  93.     delete[] count;  
  94.     unsigned char *result=(unsigned char *)(&max_ip);  
  95.     printf("出现次数最多的IP为:%d.%d.%d.%d,共出现%d次",   
  96.         result[0], result[1], result[2], result[3], max_times);  
  97. }  

执行结果.

--luuillu。

第四部分、回文判断

（初稿，写的比较急，请审阅、增补、修改）

    回文判断是一类典型的问题，尤其是与字符串结合后呈现出多姿多彩，在实际中使用也比较广泛，而且也是面试题中的常客，所以本文就结合几个典型的例子来体味下回文之趣。

    回文，英文palindrome，指一个顺着读和反过来读都一样的字符串，比如 madam、我爱我，这样的短句在智力性、趣味性和艺术性上都颇有特色，中国历史上还有很多有趣的回文诗呢  ：）

一、回文判断

    那么，我们的第一个问题就是：判断一个字串是否是回文

    通过对回文字串的考察，最直接的方法显然是将字符串逆转，存入另外一个字符串，然后比较原字符串和逆转后的字符串是否一样，一样就是回文，这个方法的时空复杂度都是 O(n)。

    我们还很容易想到只要从两头开始同时向中间扫描字串，如果直到相遇两端的字符都一样，那么这个字串就是一个回文。我们只需要维护头部和尾部两个扫描指针即可，代码如下：

  1. /**  
  2.  *check weather s is a palindrome, n is the length of string s 
  3.  *Copyright(C) fairywell 2011 
  4.  */  
  5. bool IsPalindrome(const char *s, int n)  
  6. {  
  7.    if (s == 0 || n < 1) return false; // invalid string  
  8.    char *front, *back;  
  9.    front = s; back = s + n - 1; // set front and back to the begin and endof the string  
  10.    while (front < back) {  
  11.        if (*front != *back) return false; // not a palindrome  
  12.        ++front; --back;  
  13.     }  
  14.    return true; // check over, it's a palindrome  
  15.   
  16. }  

    这是一个直白且效率不错的实现，只需要附加 2 个额外的指针，在 O(n) 时间内我们可以判断出字符串是否是回文。

    是否还有其他方法？呵呵，聪明的读者因该想到了不少变种吧，不过时空复杂度因为不会有显著提升了（为什么？），下面再介绍一种回文判断方法，先上代码：

  1. /**  
  2.  *check weather s is a palindrome, n is the length of string s 
  3.  *Copyright(C) fairywell 2011 
  4.  */  
  5. bool IsPalindrome2(const char *s, int n)  
  6. {  
  7.    if (s == 0 || n < 1) return false; // invalid string  
  8.    char *first, *second;  
  9.    int m = ((n>>1) - 1) >= 0 ? (n>>1) - 1 : 0; // m is themiddle point of s      
  10.    first = s + m; second = s + n - 1 - m;  
  11.    while (first >= s)  
  12.            if (s[first--] !=s[second++]) return false; // not equal, so it's not apalindrome  
  13.    return true; // check over, it's a palindrome  
  14. }  

    代码略有些小技巧，不过相信我们聪明的读者已经看清了意思，这里就是从中间开始、向两边扩展查看字符是否相等的一种方法，时空复杂度和上一个方法是一模一样的，既然一样，那么我们为什么还需要这种方法呢？首先，世界的美存在于它的多样性；其次，我们很快会看到，在某些回文问题里面，这个方法有着自己的独到之处，可以方便的解决一类问题。

    那么除了直接用数组，我们还可以采用其他的数据结构来判断回文吗呢？请读者朋友稍作休息想想看。相信我们聪明的读者肯定想到了不少好方法吧，也一定想到了经典的单链表和栈这两种方法吧，这也是面试中常常出现的两种回文数据结构类型。

    对于单链表结构，处理的思想不难想到：用两个指针从两端或者中间遍历并判断对应字符是否相等。所以这里的关键就是如何朝两个方向遍历。单链表是单向的，所以要向两个方向遍历不太容易。一个简单的方法是，用经典的快慢指针的方法，定位到链表的中间位置，将链表的后半逆置，然后用两个指针同时从链表头部和中间开始同时遍历并比较即可。

    对于栈就简单些，只需要将字符串全部压入栈，然后依次将各字符出栈，这样得到的就是原字符串的逆置串，分别和原字符串各个字符比较，就可以判断了。

二、回文的应用

    我们已经了解了回文的判断方法，接下来可以来尝试回文的其他应用了。回文不是很简单的东西吗，还有其他应用？是的，比如：查找一个字符串中的最长回文字串

    Hum，还是请读者朋友们先自己想想看看。嗯，有什么好方法了吗？枚举所有的子串，分别判断其是否为回文？这个思路是正确的，但却做了很多无用功，如果一个长的子串包含另一个短一些的子串，那么对子串的回文判断其实是不需要的。

    那么如何高效的进行判断呢？既然对短的子串的判断和包含它的长的子串的判断重复了，我们何不复用下短的子串的判断呢（哈，算法里也跑出软件工程了），让短的子串的判断成为长的子串的判断的一个部分！想到怎么做了吗？Aha，没错，扩展法。从一个字符开始，向两边扩展，看看最多能到多长，使其保持为回文。这也就是为什么我们在上一节里面要提出 IsPalindrome2 的原因。

    具体而言，我们可以枚举中心位置，然后再在该位置上用扩展法，记录并更新得到的最长的回文长度，即为所求。代码如下：

  1. /**  
  2.  *find the longest palindrome in a string, n is the length of string s 
  3.  *Copyright(C) fairywell 2011 
  4.  */  
  5. int LongestPalindrome(const char *s, int n)  
  6. {  
  7.    int i, j, max;  
  8.    if (s == 0 || n < 1) return 0;  
  9.    max = 0;  
  10.    for (i = 0; i < n; ++i) { // i is the middle point of the palindrome  
  11.        for (j = 0; (i-j >= 0) && (i+j < n); ++j) // if the lengthof the palindrome is odd  
  12.            if (s[i-j] != s[i+j]) break;  
  13.        if (j*2+1 > max) max = j * 2 + 1;  
  14.        for (j = 0; (i-j >= 0) && (i+j+1 < n); ++j) // for theeven case  
  15.            if (s[i-j] != s[i+j+1]) break;  
  16.        if (j*2+2 > max) max = j * 2 + 2;  
  17.     }  
  18.    return max;  
  19. }  

    代码稍微难懂一点的地方就是内层的两个 for 循环，它们分别对于以 i 为中心的，长度为奇数和偶数的两种情况，整个代码遍历中心位置 i 并以之扩展，找出最长的回文。

    当然，还有更先进但也更复杂的方法，比如用 s 和逆置 s' 的组合 s$s' 来建立后缀树的方法也能找到最长回文，但构建的过程比较复杂，所以在实践中用的比较少，感兴趣的朋友可以参考相应资料。

    回文的内容还有不少，但主要的部分通过上面的内容相信大家已经掌握，希望大家能抓住实质，在实践中灵活运用，回文的内容我就暂时介绍到这里了，谢谢大家--well。

    附注：

  • 如果读者对本文的内容或形式，语言和表达不甚满意。完全理解。我之前也跟编程艺术室内的朋友们开玩笑的说：我暂不做任何修改，题目会标明为初稿。这样的话，你们才会相信或者知晓，你们的才情只有通过我的语言和表达才能最大限度的发挥出来，被最广泛的人轻而易举的所认同和接受（不过，以上4位兄弟的思维灵活度都在本人之上）。呵呵，开个玩笑。
  • 本文日后会抽取时间再做修补和完善。若有任何问题，欢迎随时不吝指正。谢谢。

    完。


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理