Question
假设您有一个大型 ASCII 文本文件，每行都有一个随机非负整数，每个整数的范围从 0 到 1,000,000,000。文件中有 100,000,000 行。读取文件并计算所有整数之和的最快方法是什么？
限制：我们有 10MB 的 RAM 可供使用。该文件大小为 1GB，因此我们不想读取整个文件然后对其进行处理。
以下是我尝试过的各种解决方案。我发现结果相当令人惊讶。
有什么比我错过的更快的事情吗？
请注意：下面给出的所有时间均用于运行算法10 times总共（运行一次并丢弃；启动计时器；运行 10 次；停止计时器）。该机器是相当慢的 Core 2 Duo。
方法一：自然法
首先要尝试的是显而易见的方法：
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秒.
方法二：小幅调整
受到评论的启发这个问题 https://stackoverflow.com/questions/25595844/optimal-solution-for-reading-from-file，我尝试不创建一个新的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秒.
方法四：二进制处理
我们可以尝试的最后一件事是将文件作为二进制数据处理。
如果您不知道整数的长度，从前面解析它会很困难。向后解析它要容易得多：遇到的第一个数字是个位，下一个数字是十位，依此类推。因此，处理整个问题的最简单方法是向后读取文件。
如果我们分配一个byte[]（比如说）8MB 的缓冲区，我们可以用文件的最后 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 倍超过之前的最好成绩。
后续问题
-
为什么这么快？我原本以为它会获胜，但并没有那么令人印象深刻。主要是转换为a的开销吗？
String？还有所有幕后关于角色设置之类的担忧吗？
- 我们可以通过使用一个比这更好的方法吗？
MappedByteBuffer帮助？我有一种感觉，调用从缓冲区读取的方法的开销会减慢速度，尤其是从缓冲区向后读取时。
- 向前读取文件而不是向后读取文件会更好，但仍向后扫描缓冲区吗？这个想法是，您读取文件的第一个块，然后向后扫描，但丢弃最后的半数。然后，当您读取下一个块时，您可以设置偏移量，以便从您丢弃的数字的开头读取。
- 有什么我没有想到的可以产生重大影响的事情吗？
更新：更多令人惊讶的结果
首先，观察。我以前就应该想到这一点，但我认为造成效率低下的原因是String基于阅读的内容并不是创造所有内容所花费的时间String但事实上它们的生命周期非常短暂：我们有 100,000,000 个对象供垃圾收集器处理。这势必会让它心烦意乱。
现在一些基于人们发布的答案/评论的实验。
我是否在缓冲区的大小上作弊？
一个建议是，既然BufferedReader使用默认的 16KB 缓冲区，我使用了 8MB 的缓冲区，我不是在比较。如果使用更大的缓冲区，速度肯定会更快。
这就是震惊。这sumBinary()昨天，方法（方法 4）在 8MB 缓冲区下运行了 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()在单线程中计算结果；对于较大的问题，它会分成两个，在单独的线程中解决两个子问题，然后合并结果。
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 个），并且不会显着影响运行时间。
所以多线程does有很大的不同。
这是一段相当漫长的旅程，但我们一开始需要 92.9 秒，现在已经减少到 13.3 秒……那就是七倍的速度的原始代码。这并不是通过改进渐近（大哦）时间复杂度，它从一开始就是线性（最优）的……这一切都是为了改进常数因子。
美好的一天的工作。
我想接下来我应该尝试使用 GPU...
后记：生成随机数文件
我使用以下代码生成了随机数，运行该代码并将其重定向到一个文件。显然我不能保证你最终会得到与我完全相同的随机数:)
public static void genRandoms() {
Random r = new Random();
for (int i = 0; i < 100000000; i++)
System.out.println(r.nextInt(1000000000));
}
