题目大意:移动公司需要对已经发放的所有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数组的类,代码如下:
-
public class BitArray {
-
private int[] bits = null;
-
private int length;
-
-
private final static int[] bitValue = {
-
0x80000000,
-
0x40000000,
-
0x20000000,
-
0x10000000,
-
0x08000000,
-
0x04000000,
-
0x02000000,
-
0x01000000,
-
0x00800000,
-
0x00400000,
-
0x00200000,
-
0x00100000,
-
0x00080000,
-
0x00040000,
-
0x00020000,
-
0x00010000,
-
0x00008000,
-
0x00004000,
-
0x00002000,
-
0x00001000,
-
0x00000800,
-
0x00000400,
-
0x00000200,
-
0x00000100,
-
0x00000080,
-
0x00000040,
-
0x00000020,
-
0x00000010,
-
0x00000008,
-
0x00000004,
-
0x00000002,
-
0x00000001
-
};
-
public BitArray(int length) {
-
if(length < 0){
-
throw new IllegalArgumentException("length必须大于零!");
-
}
-
bits = new int[length / 32 + (length % 32 > 0 ? 1 : 0)];
-
this.length = length;
-
}
-
-
public int getBit(int index){
-
if(index <0 || index > length){
-
throw new IllegalArgumentException("length必须大于零小于" + length);
-
}
-
int intData = bits[index/32];
-
return (intData & bitValue[index%32]) >>> (32 - index%32 -1);
-
}
-
-
public void setBit(int index,int value){
-
if(index <0 || index > length){
-
throw new IllegalArgumentException("length必须大于零小于" + length);
-
}
-
if(value!=1&&value!=0){
-
throw new IllegalArgumentException("value必须为0或者1");
-
}
-
int intData = bits[index/32];
-
if(value == 1){
-
bits[index/32] = intData | bitValue[index%32];
-
}else{
-
bits[index/32] = intData & ~bitValue[index%32];
-
}
-
}
-
public int getLength(){
-
return length;
-
}
-
}
-
-
public class BitArray {
-
private int[] bits = null;
-
private int length;
-
-
private final static int[] bitValue = {
-
0x80000000,
-
0x40000000,
-
0x20000000,
-
0x10000000,
-
0x08000000,
-
0x04000000,
-
0x02000000,
-
0x01000000,
-
0x00800000,
-
0x00400000,
-
0x00200000,
-
0x00100000,
-
0x00080000,
-
0x00040000,
-
0x00020000,
-
0x00010000,
-
0x00008000,
-
0x00004000,
-
0x00002000,
-
0x00001000,
-
0x00000800,
-
0x00000400,
-
0x00000200,
-
0x00000100,
-
0x00000080,
-
0x00000040,
-
0x00000020,
-
0x00000010,
-
0x00000008,
-
0x00000004,
-
0x00000002,
-
0x00000001
-
};
-
public BitArray(int length) {
-
if(length < 0){
-
throw new IllegalArgumentException("length必须大于零!");
-
}
-
bits = new int[length / 32 + (length % 32 > 0 ? 1 : 0)];
-
this.length = length;
-
}
-
-
public int getBit(int index){
-
if(index <0 || index > length){
-
throw new IllegalArgumentException("length必须大于零小于" + length);
-
}
-
int intData = bits[index/32];
-
return (intData & bitValue[index%32]) >>> (32 - index%32 -1);
-
}
-
-
public void setBit(int index,int value){
-
if(index <0 || index > length){
-
throw new IllegalArgumentException("length必须大于零小于" + length);
-
}
-
if(value!=1&&value!=0){
-
throw new IllegalArgumentException("value必须为0或者1");
-
}
-
int intData = bits[index/32];
-
if(value == 1){
-
bits[index/32] = intData | bitValue[index%32];
-
}else{
-
bits[index/32] = intData & ~bitValue[index%32];
-
}
-
}
-
public int getLength(){
-
return length;
-
}
-
}
-
bit数组有了,剩下就是算法代码,核心代码如下:
-
bitArray = new BitArray(100000000);
-
-
while((phoneNum = bufferedReader.readLine())!=null){
-
phoneNum = phoneNum.trim().substring(3);
-
-
phoneNumAsInt = Integer.valueOf(phoneNum);
-
-
bitArray.setBit(phoneNumAsInt, 1);
-
}
-
-
for(int i = 0;i
-
if(bitArray.getBit(i)==1){
-
writer.write("139" + leftPad(String.valueOf(i + sortUnit*times), 8));
-
writer.newLine();
-
}
-
}
-
writer.flush();
-
-
bitArray = new BitArray(100000000);
-
-
while((phoneNum = bufferedReader.readLine())!=null){
-
phoneNum = phoneNum.trim().substring(3);
-
-
phoneNumAsInt = Integer.valueOf(phoneNum);
-
-
bitArray.setBit(phoneNumAsInt, 1);
-
}
-
-
for(int i = 0;i
-
if(bitArray.getBit(i)==1){
-
writer.write("139" + leftPad(String.valueOf(i + sortUnit*times), 8));
-
writer.newLine();
-
}
-
}
-
writer.flush();
-
经测试,修改后的算法排序时只需要20多M的内存,一亿条电话号码排序只要10分钟(时间主要花在IO上),看来效果还是很明显的。
这个算法很快,不过也有他的局限性:
1.只能用于整数的排序,或者可以准确映射到正整数(对象不同对应的正整数也不相同)的数据的排序。
2.不能处理重复的数据,重复的数据排序后只有一条(如果有这种需求可以在这个算法的基础上修改,给出现次数大于1的数据添加个计数器,然后存入Map中)
3.对于数据量极其大的数据处理可能还是比较占用空间,这种情况可配合多通道排序算法解决。
PS:这个算法的思想源于《编程珠玑》,有兴趣的可以读读那本书,非常不错!
阅读(602) | 评论(0) | 转发(0) |