问题
假设你有一个大的 ASCII 纯文本文件，每行都有一个随机非负整数，每个整数的范围从 0 到 1,000,000,000。文件有 1 亿行。如何最快地读取文件并计算所有整数的总和？
限制条件：我们只有 10MB 的 RAM 可以使用。文件大小为 1GB，因此我们不想读取整个文件然后处理。
下面是我尝试过的各种解决方案。结果让我感到相当惊讶。
我是否遗漏了更快的方法？
请注意：下面给出的所有时间都是运行该算法共计 10 次的时间（运行一次并丢弃；启动计时器；运行 10 次；停止计时器）。该机器是一台相对较慢的 Core 2 Duo。
方法 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;
}
请注意，最大可能的返回值为10^17，而这个值很容易放入一个long中，因此我们不必担心溢出问题。
在我的电脑上，运行11次并排除第一次运行大约需要92.9秒。
方法2：微小的调整
受到这个问题中的评论启发，我尝试不创建一个新的int k来存储解析行的结果，而是直接将解析的值添加到total中。所以代码变成了这样：
while ((line = br.readLine()) != null) {
int k = Integer.parseInt(line);
total += k;
}
变成了这样：
while ((line = br.readLine()) != null)
total += Integer.parseInt(line);
我确信这不会有任何影响，而且认为编译器生成的两个版本的字节码应该是相同的。但出乎意料的是，它确实缩短了一点时间：我们将时间降低到92.1秒。
方法三：手动解析整数
目前代码中让我困扰的一件事是我们将String转换为int，然后在最后进行相加，这样做可能会更快吗？如果我们自己解析String会怎么样呢？类似这样...
private long sumLineByLineManualParse() throws NumberFormatException,
IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
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;
}
我认为这可能会节省一些时间，特别是使用一些位移优化来进行乘法操作。但将其转换为字符数组的开销可能会抵消所有的收益：现在需要148.2秒。
第四种方法：二进制处理
我们可以尝试的最后一件事是以二进制数据的方式处理文件。
如果您不知道整数的长度，则从前面解析整数很麻烦。反向解析要容易得多：首个数字是个位数，下一个是十位数，以此类推。因此，处理整个文件最简单的方法是从后往前读取。
如果我们分配一个（比如）8MB的byte[]缓冲区，我们可以用文件的最后8MB填充它，处理它，然后读取前面的8MB，以此类推。我们需要小心，不要在移动到下一个块时搞乱正在解析的数字，但这是唯一的问题。
当我们遇到数字时，我们将其加入总数中（根据其在数字中的位置适当地乘以系数），然后将系数乘以10，以便准备好下一个数字。如果我们遇到任何不是数字的东西（CR或LF），我们只需重置系数即可。
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秒！比以前最好的结果快了3倍。
后续问题
- 为什么速度提升这么明显？我本来就期望它能赢，但没有想到会如此出色。是不是主要是将其转换为
String的开销？以及所有与字符集相关的内部担忧？ - 如果使用
MappedByteBuffer可以帮助减少开销吗？我有一种感觉，调用从缓冲区中读取数据的方法的开销会减慢速度，特别是在从缓冲区倒序读取时。 - 将文件正向读取而不是反向读取，但仍然向后扫描缓冲区，这样会更好吗？想法是先读取文件的第一个块，然后向后扫描，但舍弃末尾的一半数字。然后当你读取下一个块时，设置偏移量，以便从丢弃的数字的开头读取。
- 还有没有我没想到的可能会有显着差异的东西？
更新：更多意外的结果
首先，有一个观察。我应该早就意识到了，但我认为基于String 的读取效率低下的原因不是创建所有String对象所花费的时间，而是它们的生命周期太短暂：我们有1亿个对象需要垃圾收集器处理。这肯定会让它受挫。
现在根据人们发布的答案/评论进行一些实验。
使用较大的缓冲区是否有欺骗性？
有人建议由于BufferedReader使用默认缓冲区大小为16KB，而我使用了8MB的缓冲区，所以我没有进行合理的比较。如果你使用更大的缓冲区，它肯定会更快。
结果令人震惊。用8MB的缓冲区运行sumBinary()方法（方法4）昨天需要30.8秒。今天，代码没有改变，风向改变了，运行时间为30.4秒。如果我将缓冲区大小降至16KB以查看其速度降低多少，它反而变得更快了！现在只需23.7秒即可运行。疯狂吧。谁料到呢？！
一些实验表明，16KB是最优的。也许Java的人也做了同样的实验，这就是为什么他们选择了16KB！
问题是否受到I/O限制？
我也在想这个问题。花费多少时间在磁盘访问上，多少时间用于计算数字？如果像一个被广泛支持的答案建议的那样，几乎全部时间都花费在磁盘访问上，那么无论我们做什么改进，都不会有太大的提高。
可以通过注释掉所有的解析和数字计算代码，但保留文件读取代码来测试。
private long sumBinary() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[16 * 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--) {
if ((buf[i] >= 48) && (buf[i] <= 57)) {
total += mul * (buf[i] - 48);
mul *= 10;
} else
mul = 1;
}*/
}
raf.close();
return total;
}
现在执行时间只有3.7秒！我认为这并不是I/O限制导致的。
当然，一些I/O速度可能来自磁盘缓存命中。但这并不是重点：我们仍然需要20秒的CPU时间（还可以使用Linux的time命令进行确认），这足以尝试减少它。
向前扫描而不是向后扫描
在我的原帖中，我坚持认为反向扫描文件比正向扫描更有道理。我没有解释清楚。我的想法是，如果您向前扫描一个数字，则必须累加扫描数字的总值，然后再加上它。如果您向后扫描，则可以在扫描时将其添加到累积总数中。我的潜意识对自己有某种意义（稍后会有更多解释），但我错过了一个关键点，其中一个答案指出：为了向后扫描，我每次迭代都要进行两次乘法，但是向前扫描只需要一次。所以我编写了一个向前扫描的版本：
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秒，比向后扫描版本效率更高。不错！
乘法缓存
然而我在晚上意识到的一件事是，虽然每次迭代需要执行两个乘法运算，但有可能使用缓存来存储这些乘法计算结果，这样就可以避免在向后迭代时重复计算。当我醒来时很高兴发现有人也想到了同样的方法！
关键在于，我们要扫描的数字中最多只有10个数字，且仅有10种可能的数字，因此对于一个数字对总和的贡献值最多有100种可能。我们可以预先计算好这些贡献值，并在向后扫描代码中使用它们。这应该能够超过向前扫描版本的效率，因为我们已经完全摆脱了乘法运算。（请注意，我们无法用向前扫描的方式实现这一点，因为累加器的乘积可能达到10^9。只有在后向扫描的情况下，两个操作数都受到了一些限制。）
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;
}
这个程序运行了26.1秒，可以说是令人失望的。倒序阅读从I/O角度来看不太高效，但我们已经发现 I/O 不是主要问题。我本以为这会带来很大的积极差异。也许数组查找的开销和我们替换的乘法一样昂贵。(我确实尝试过将数组变为 16x16，并使用位移进行索引，但没有帮助。)
看起来前向扫描是解决问题的关键。
使用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秒。我们又创造了一个人生新纪录！
多线程如何呢？
其中一个提出的答案是使用多个核心。我有点惭愧，没有想到这一点！
这个答案因为假设这是一个I/O受限的问题而备受争议。考虑到I/O的结果，这似乎有点过于苛刻了！无论如何，值得一试。
我们将使用fork/join来实现。这里有一个类来表示文件部分计算的结果，要注意可能会有左边的部分结果（如果我们从一个数字的一半开始），以及右边的部分结果（如果缓冲区在数字的一半结束）。该类还有一个方法，允许我们将两个这样的结果粘合在一起，成为相邻子任务的组合结果。
private class SumTaskResult {
long subtotal;
int leftPartial;
int leftMulCount;
int rightPartial;
public void append(SumTaskResult rightward) {
subtotal += rightward.subtotal + rightPartial
* rightward.leftMulCount + rightward.leftPartial;
rightPartial = rightward.rightPartial;
}
}
RecursiveTask。对于小问题（少于64个字符），它调用computeDirectly()在单个线程中计算结果；对于更大的问题，它将问题分成两部分，在不同的线程中解决这两个子问题，然后合并结果。
现在重点来了：计算结果的RecursiveTask。对于小问题（少于64个字符），它调用computeDirectly()在单个线程中计算结果；对于更大的问题，它将问题分成两部分，在不同的线程中解决这两个子问题，然后合并结果。
private class SumForkTask extends RecursiveTask<SumTaskResult> {
private byte buf[];
// startPos inclusive, endPos exclusive
private int startPos;
private int endPos;
public SumForkTask(byte buf[], int startPos, int endPos) {
this.buf = buf;
this.startPos = startPos;
this.endPos = endPos;
}
private SumTaskResult computeDirectly() {
SumTaskResult result = new SumTaskResult();
int pos = startPos;
result.leftMulCount = 1;
while ((buf[pos] >= 48) && (buf[pos] <= 57)) {
result.leftPartial = result.leftPartial * 10 + buf[pos] - 48;
result.leftMulCount *= 10;
pos++;
}
int acc = 0;
for (int i = pos; i < endPos; i++)
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
result.subtotal += acc;
acc = 0;
}
result.rightPartial = acc;
return result;
}
@Override
protected SumTaskResult compute() {
if (endPos - startPos < 64)
return computeDirectly();
int mid = (endPos + startPos) / 2;
SumForkTask left = new SumForkTask(buf, startPos, mid);
left.fork();
SumForkTask right = new SumForkTask(buf, mid, endPos);
SumTaskResult rRes = right.compute();
SumTaskResult lRes = left.join();
lRes.append(rRes);
return lRes;
}
}
byte[]，而不是整个MappedByteBuffer。 这样做的原因是我们希望保持磁盘访问的顺序性。 我们将采用相当大的块，进行分叉/合并，然后移动到下一个块。以下是执行此操作的方法。 请注意，我们将缓冲区大小提高到1MB（之前不太理想，但在这里更明智）。
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;
}
现在，令人沮丧的是，这段很好的多线程代码现在需要32.2秒。为什么这么慢？我花了相当长的时间调试，认为我做错了什么。
事实证明只需要进行一点小调整。我原本认为64是解决小问题和大问题之间的合理阈值，结果证明那完全荒谬。
就像这样考虑。子问题的大小完全相同，因此它们应该在几乎相同的时间内完成。所以切分成的块数不应该超过可用处理器的数量。在我使用的机器上，只有两个核心，将阈值降到64是荒谬的：它只会增加额外的开销。
现在不要限制它只使用两个核心，即使有更多可用。也许正确的做法是在运行时找出处理器的数量，并将其分割成那么多块。
无论如何，如果我将阈值更改为512KB（缓冲区大小的一半），它现在可以在13.3秒内完成。将其降至128KB或64KB将允许使用更多核心（最多8或16个），并且不会显着影响运行时间。
因此，多线程确实起了很大的作用。
这是一个漫长的过程，但我们从需要92.9秒开始，现在只需要13.3秒...这是原始代码速度的七倍。而这不是通过改善渐近（大Oh）时间复杂度来实现的，它从一开始就是线性（最优的）...这一切都是为了改善常数因子。
干得好。
我想下一步应该尝试使用GPU...
附：生成随机数文件
我使用以下代码生成了随机数，并将其重定向到文件中。显然，我不能保证您会获得完全相同的随机数 :)
public static void genRandoms() {
Random r = new Random();
for (int i = 0; i < 100000000; i++)
System.out.println(r.nextInt(1000000000));
}
BufferedReader使用16k。即使倒序读取文件会更有效率（实际上并不是这样！），但只需将读取器中的缓冲区增加到相同的级别，就可以获得更多的收益。你正在比较苹果和橙子。 - Thomas Jungblutfstream很慢并不重要，因为CPU比磁盘快得多。基准测试总是表明这是错误的。需要非常小心才能跟上现代磁盘流传输速度为120MB/s（旋转）或500MB/s（固态），当然缓存速度更快。 - Ben Voigt