公司的一道考试题算法分析——大数据量整数排序

墨蓝 2023-10-17 15:33 1阅读 0赞

题目大意：移动公司需要对已经发放的所有139段的号码进行统计排序，已经发放的139号码段的文件都存放在一个文本文件中（原题是放在两个文件中），一个号码一行，现在需要将文件里的所有号码进行排序，并写入到一个新的文件中；号码可能会有很多，最多可能有一亿个不同的号码（所有的139段号码），存入文本文件中大概要占1.2G的空间；jvm最大的内存在300以内，程序要考虑程序的可执行性及效率；只能使用Java标准库，不得使用第三方工具。   
 这是个典型的大数据量的排序算法问题，首先要考虑空间问题，一下把1.2G的数据读入内存是不太可能的，就算把1一亿条数据，转都转换成int类型存储也要占接近400M的空间。当时做个题目我并没有想太多的执行效率问题，主要就考虑了空间，而且习惯性的想到合并排序，基本思想是原文件分割成若干个小文件并排序，再将排序好的小文件合并得到最后结果，算法大概如下：   
  
 1.顺序读取存放号码文件的中所有号码，并取139之后的八位转换为int类型；每读取号码数满一百万个（这个数据可配置）将已经读取的号码排序并存入新建的临时文件。  
2.将所有生成的号码有序的临时文件合并存入结果文件。  
  
 这个算法虽然解决了空间问题，但是运行效率极低，由于IO读写操作太多，加上步骤1中的排序的算法（快速排序）本来效率就不高（对于电话排序这种特殊情况来说），导致1亿条数据排序运行3个小时才有结果。   
  
 如果和能够减少排序的时间呢？首当其冲的减少IO操作，另外如果能够有更加好排序算法也行。前天无聊再看这个题目时突然想到大三时看《编程珠玑》时上面也有个问题的需求这个这个题目差不多，记得好像使用是位向量（实际上就是一个bit数组），用电话作为index，心中大喜，找到了解决此问题的最完美方案啦：用位向量存储电话号码，一个号码占一个bit，一亿个电话号码也只需要大概12M的空间；算法大概如下：   
 1.初始化bits\[capacity\]；  
2.顺序所有读入电话号码，并转换为int类型，修改位向量值：bits\[phoneNum\]=1；  
3.遍历bits数组，如果bits\[index\]=1，转换index为电话号码输出。  
 Java中没有bit类型，一个boolean值占空间为1byte（感兴趣的可以自己写程序验证），我自己写个个用int模拟bit数组的类，代码如下：

Java代码 ![收藏代码][icon_star.png]

1.  **public** **class** BitArray \{ 
2.  **private** **int**\[\] bits = **null**; 
3.  **private** **int** length; 
4.  //用于设置或者提取int类型的数据的某一位(bit)的值时使用
5.  **private** **final** **static** **int**\[\] bitValue = \{ 
6.  0x80000000,//10000000 00000000 00000000 00000000 
7.  0x40000000,//01000000 00000000 00000000 00000000 
8.  0x20000000,//00100000 00000000 00000000 00000000 
9.  0x10000000,//00010000 00000000 00000000 00000000 
10. 0x08000000,//00001000 00000000 00000000 00000000 
11. 0x04000000,//00000100 00000000 00000000 00000000 
12. 0x02000000,//00000010 00000000 00000000 00000000 
13. 0x01000000,//00000001 00000000 00000000 00000000 
14. 0x00800000,//00000000 10000000 00000000 00000000 
15. 0x00400000,//00000000 01000000 00000000 00000000 
16. 0x00200000,//00000000 00100000 00000000 00000000 
17. 0x00100000,//00000000 00010000 00000000 00000000 
18. 0x00080000,//00000000 00001000 00000000 00000000 
19. 0x00040000,//00000000 00000100 00000000 00000000 
20. 0x00020000,//00000000 00000010 00000000 00000000 
21. 0x00010000,//00000000 00000001 00000000 00000000 
22. 0x00008000,//00000000 00000000 10000000 00000000 
23. 0x00004000,//00000000 00000000 01000000 00000000 
24. 0x00002000,//00000000 00000000 00100000 00000000 
25. 0x00001000,//00000000 00000000 00010000 00000000 
26. 0x00000800,//00000000 00000000 00001000 00000000 
27. 0x00000400,//00000000 00000000 00000100 00000000 
28. 0x00000200,//00000000 00000000 00000010 00000000 
29. 0x00000100,//00000000 00000000 00000001 00000000 
30. 0x00000080,//00000000 00000000 00000000 10000000 
31. 0x00000040,//00000000 00000000 00000000 01000000 
32. 0x00000020,//00000000 00000000 00000000 00100000 
33. 0x00000010,//00000000 00000000 00000000 00010000 
34. 0x00000008,//00000000 00000000 00000000 00001000 
35. 0x00000004,//00000000 00000000 00000000 00000100 
36. 0x00000002,//00000000 00000000 00000000 00000010 
37. 0x00000001 //00000000 00000000 00000000 00000001 
38.  \}; 
39. **public** BitArray(**int** length) \{ 
40. **if**(length < 0)\{ 
41. **throw** **new** IllegalArgumentException("length必须大于零！"); 
42.  \} 
43.  bits = **new** **int**\[length / 32 \+ (length % 32 > 0 ? 1 : 0)\]; 
44. **this**.length = length; 
45.  \} 
46. //取index位的值
47. **public** **int** getBit(**int** index)\{ 
48. **if**(index <0 || index > length)\{ 
49. **throw** **new** IllegalArgumentException("length必须大于零小于" \+ length); 
50.  \} 
51. **int** intData = bits\[index/32\]; 
52. **return** (intData & bitValue\[index%32\]) >>> (32 \- index%32 \-1); 
53.  \} 
54. //设置index位的值，只能为0或者1
55. **public** **void** setBit(**int** index,**int** value)\{ 
56. **if**(index <0 || index > length)\{ 
57. **throw** **new** IllegalArgumentException("length必须大于零小于" \+ length); 
58.  \} 
59. **if**(value!=1&&value!=0)\{ 
60. **throw** **new** IllegalArgumentException("value必须为0或者1"); 
61.  \} 
62. **int** intData = bits\[index/32\]; 
63. **if**(value == 1)\{ 
64.  bits\[index/32\] = intData | bitValue\[index%32\]; 
65.  \}**else**\{ 
66.  bits\[index/32\] = intData & ~bitValue\[index%32\]; 
67.  \} 
68.  \} 
69. **public** **int** getLength()\{ 
70. **return** length; 
71.  \} 
72. \} 
73.

bit数组有了，剩下就是算法代码，核心代码如下：

Java代码 ![收藏代码][icon_star.png]

1.  bitArray = **new** BitArray(100000000); 
2.  //顺序读取所有的手机号码
3.  **while**((phoneNum = bufferedReader.readLine())!=**null**)\{ 
4.   phoneNum = phoneNum.trim().substring(3);//13573228432
5.  //取139后8位转换为int类型
6.   phoneNumAsInt = Integer.valueOf(phoneNum); 
7.  //设置对应bit值为1
8.   bitArray.setBit(phoneNumAsInt, 1); 
9.  \} 
10. //遍历bit数组输出所有存在的号码
11. **for**(**int** i = 0;i<sortUnit;i++)\{ 
12. **if**(bitArray.getBit(i)==1)\{ 
13.  writer.write("139" \+ leftPad(String.valueOf(i + sortUnit\*times), 8)); 
14.  writer.newLine(); 
15.  \} 
16. \} 
17. writer.flush(); 
18.

经测试，修改后的算法排序时只需要20多M的内存，一亿条电话号码排序只要10分钟（时间主要花在IO上），看来效果还是很明显的。   
 这个算法很快，不过也有他的局限性：   
 1.只能用于整数的排序，或者可以准确映射到正整数（对象不同对应的正整数也不相同）的数据的排序。   
 2.不能处理重复的数据，重复的数据排序后只有一条（如果有这种需求可以在这个算法的基础上修改， 给出现次数大于1的数据添加个计数器 ，然后存入Map中）   
 3.对于数据量极其大的数据处理可能还是比较占用空间， 这种情况可配合多通道排序算法解决。   
  
 PS:这个算法的思想源于《编程珠玑》，有兴趣的可以读读那本书，非常不错！

来源：http://pisces-java.iteye.com/blog/766745

[icon_star.png]: http://pisces-java.iteye.com/images/icon_star.png