原文地址: Fastest way to sum integers in text file.
文末提供源码下载.
问题描述:
假如你有一个很大的文本文件（1G大小）, 里面有100,000,000 行数字.每个数字范围从0到1,000,000,000. 那么如何计算可以使计算时间最短?
方法1、逐行读取数字再累加。
private long sumLineByLine() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
String line;
long total = 0;
while ((line = br.readLine()) != null) {
int k = Integer.parseInt(line);
total += k;
}
br.close();
return total;
}
这是最容易想到的一种处理方式. 题主的机器上运行了11次, 然后平均值为92.9 秒.
方法2、一点小改变。
经过评论的提醒, 题主想到可以在循环里减少局部变量来提高性能.
while ((line = br.readLine()) != null) {
int k = Integer.parseInt(line);
total += k;
}
改为
while ((line = br.readLine()) != null) {
total += Integer.parseInt(line);
}
这一次的平均值为92.1 秒, 提高了1%. 好像不太乐观.
方法3、通过字符数组来解析数字
使用字符数组和位运算来解析数字
public long sumLineByLineManualParse() throws NumberFormatException,IOException {
BufferedReader br = new BufferedReader(new FileReader(DataProcess.path));
String line;
long total = 0;
while ((line = br.readLine()) != null) {
char chs[] = line.toCharArray();
int mul = 1;
for (int i = chs.length - 1; i >= 0; i--) {
char c = chs[i];
switch (c) {
case '0':
break;
case '1':
total += mul;
break;
case '2':
total += (mul << 1);
break;
case '4':
total += (mul << 2);
break;
case '8':
total += (mul << 3);
break;
default:
total += (mul * ((byte) c - (byte) ('0')));
}
mul *= 10;
}
}
br.close();
return total;
}
题主本以为不用之前的parseInt方法，而改用基于字符的位运算会提高性能，但是没想到最后的结果反而更差。平均时间为148.2 秒。
方法4、基于字节流来处理（从后往前扫描）。
缓存数组设置为8M大小，然后对每个字节进行数学计算。这种方式比较好理解：碰到第一个数字在个位，第二个数字在十位……，对应的加权因子为1,10……。
private long sumBinary() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[8*1024*1024];
int mul = 1;
long total = 0;
while (lastRead>0) {
int len = Math.min(buf.length, lastRead);
raf.seek(lastRead-len);
raf.readFully(buf, 0, len);
//计算剩余未读字节长度
lastRead-=len;
for (int i=len-1; i>=0; i--) {
//48 is '0' and 57 is '9'
if ((buf[i]>=48) && (buf[i]<=57)) {
total+=mul*(buf[i]-48);
mul*=10;
} else
mul=1;
}
}
raf.close();
return total;
}
这一次的平均运行时间为30.8 秒! 题主很激动， 因为这比方法1足足提高了三倍效率.
做到这一步，题主做了大量的思考，从各个角度思考为什么字节流的方式效率会这么高。甚至还想到了垃圾回收对字符流处理的影响，我真的对此佩服的五体投地，这需要多么扎实的java基础才能有如此丰富的联想啊。原文行文流畅，条理清晰，特别推荐大家去看。
另外基于这种方法，题主还对缓存数组做了一点改造，将8M缓存改为了16K，计算时间也下降到23.7秒。题主对此的解释是：也许java的设计者们也做了类似的测试，所以才在16K的缓存时拥有较好的性能。
方法5、基于字节流来处理（从前往后扫描）
private long sumBinaryForward() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int fileLength = (int) raf.length();
byte buf[] = new byte[16 * 1024];
int acc = 0;
long total = 0;
int read = 0;
while (read < fileLength) {
int len = Math.min(buf.length, fileLength - read);
raf.readFully(buf, 0, len);
read += len;
for (int i = 0; i < len; i++) {
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
total += acc;
acc = 0;
}
}
}
raf.close();
return total;
}
这次的平均时间为20.0 秒,目前为止最快. 题主给的原因是方法5比方法4少用了一次乘法。那么题主思维又发散了，如果一次乘法都不用呢？还真让他找到了一种巧妙的方法，不过实验证明效率反而下降了。
private long sumBinaryCached() throws IOException {
int mulCache[][] = new int[10][10];
int coeff = 1;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++)
mulCache[i][j] = coeff * j;
coeff *= 10;
}
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[16 * 1024];
int mul = 0;
long total = 0;
while (lastRead > 0) {
int len = Math.min(buf.length, lastRead);
raf.seek(lastRead - len);
raf.readFully(buf, 0, len);
lastRead -= len;
for (int i = len - 1; i >= 0; i--) {
if ((buf[i] >= 48) && (buf[i] <= 57))
total += mulCache[mul++][buf[i] - 48];
else
mul = 0;
}
}
raf.close();
return total;
}
至于原因？也许数组寻址不比一次乘法的代价小吧。
方法6、使用MappedByteBuffer
接下来使用MappedByteBuffer来代替RandomAccessFile进行字节操作，看看效率是否有提高。
private long sumBinaryForwardMap() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
byte buf[] = new byte[16 * 1024];
final FileChannel ch = raf.getChannel();
int fileLength = (int) ch.size();
final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, 0,
fileLength);
int acc = 0;
long total = 0;
while (mb.hasRemaining()) {
int len = Math.min(mb.remaining(), buf.length);
mb.get(buf, 0, len);
for (int i = 0; i < len; i++)
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
total += acc;
acc = 0;
}
}
ch.close();
raf.close();
return total;
}
平均时间为19.0 秒，比之前又有5%的提升。
方法7、使用多线程
这个方法实现起来比较复杂，有两个问题要解决：①在使用字节流处理的时候，因为无法保证最后一个字节是空字符。所以如何保证数字字符的连续性。②如何把子线程的计算结果汇总起来。
题主用到了分治法，使用的是Fork/Join框架，从前向后扫描文件并且严格保证执行顺序。入口方法如下：
private long sumBinaryForwardMapForked() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
ForkJoinPool pool = new ForkJoinPool();
byte buf[] = new byte[1 * 1024 * 1024];
final FileChannel ch = raf.getChannel();
int fileLength = (int) ch.size();
final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, 0,
fileLength);
SumTaskResult result = new SumTaskResult();
while (mb.hasRemaining()) {
int len = Math.min(mb.remaining(), buf.length);
mb.get(buf, 0, len);
SumForkTask task = new SumForkTask(buf, 0, len);
result.append(pool.invoke(task));
}
ch.close();
raf.close();
pool.shutdown();
return result.subtotal;
}
其他部分可以参考原文或者我的可测试代码
PS
在方法4,5,6中, 有48和57两个魔法数， 如果使用常量来代替48和57会严重的影响性能。暂时不清楚原因。
网友评论