大数据量整数排序.docx
7页
公司的一道考试题算法分析——大数据量整数排序题目大意：移动公司需要对已经发放的所有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代码 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. view plain1. public class BitArray { 2. private int[] bits = null; 3. private int length; 4. 。
