最快的方法来整理文本文件中的整数
题
假设你有一个大的ASCII文本文件，每行有一个随机的非负整数，每个范围从0到1,000,000,000。 文件中有100,000,000行。 读通过文件并计算所有整数的总和的最快方法是什么？
约束：我们有10MB的RAM来处理。 这个文件的大小是1GB，所以我们不想把整个文件读入然后处理。
以下是我尝试过的各种解决scheme。 我发现结果相当令人惊讶。
有没有更快的，我错过了？
请注意：下面给出的所有时间是总共运行10次的algorithm（运行一次并丢弃;启动计时器;运行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，它仍然很容易适应，所以我们不必担心溢出。
在我的机器上，运行这11次，折扣第一次运行大约需要92.9秒 。
方法2：一个小调整
受这个问题的评论的启发，我试着不创build一个新的int k来存储parsing行的结果，而是直接将parsing的值添加到total 。 所以这：
while ((line = br.readLine()) != null) { int k = Integer.parseInt(line); total += k; }
变成这样：
while ((line = br.readLine()) != null) total += Integer.parseInt(line);
我确信这不会有什么区别，并认为编译器很可能会为这两个版本生成相同的字节码。 但是，令我惊讶的是，它确实刮了一点时间：我们降到了92.1秒 。
方法3：手动parsing整数
到目前为止，困扰我的代码之一是我们把String变成一个int ，然后在最后添加它。 当我们去时可能不会更快？ 如果我们自己parsingString ，会发生什么？ 像这样的东西…
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秒 。
方法4：以二进制处理
我们可以尝试的最后一件事是将文件作为二进制数据处理。
如果你不知道它的长度，从前面parsing一个整数是很尴尬的。 向后parsing要容易得多：遇到的第一位数字是单位，下一位数字是十位，依此类推。 所以最简单的方法就是向后读取文件。
如果我们分配一个8MB的byte[]缓冲区，我们可以用文件的最后8MB来填充它，处理它，然后读取前面的8MB，依此类推。 我们需要小心一点，当我们移动到下一个块时，我们不会搞乱一个正在parsing的数字，但这是唯一的问题。
当我们遇到一个数字时，我们把它加上（根据它在数字中的位置适当地相乘）到总数，然后乘以系数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的读取效率低下的原因并不是创build所有String对象所花费的时间，而是因为它们如此短暂：我们得到其中有1亿个垃圾收集器要处理。 那肯定会让它心烦。
现在根据人们发布的答案/评论进行一些实验。
我在用缓冲区的大小作弊吗？
一个build议是，由于BufferedReader使用16KB的默认缓冲区，而且我使用了8MB的缓冲区，所以我不会像like一样比较。 如果使用更大的缓冲区，它肯定会更快。
这是震惊。 sumBinary()方法（方法4）在昨天用一个8MB缓冲区在30.8秒内运行。 今天，代码不变，风向已经改变，我们在30.4秒。 如果我把缓冲区大小降到16KB，看看它变慢了多less，速度会变快！ 它现在运行23.7秒 。 疯。 谁看到那个来的？
一些实验表明16KB是最佳的。 也许Java的人做了相同的实验，这就是为什么他们去了16KB！
问题I / O绑定？
我也想知道这个。 在磁盘访问上花费了多less时间，以及在数据处理上花了多less时间？ 如果几乎所有的磁盘访问都是正确的，就像对其中一个build议的答案提供支持的评论所表明的那样，那么无论我们做什么，我们都无法取得很大的进步。
通过运行代码，所有的parsing和数字运算都被注释掉了，这很容易testing，但读数仍然保持不变：
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速度将来自磁盘caching命中。 但是这并不是真正的重点：我们仍然需要20秒钟的CPU时间（也使用Linux的time命令来确认），这个time足够大，可以减less这个时间。
向前扫描而不是向后扫描
我在原来的文章中保留说有理由将文件向后扫描而不是向前扫描。 我没有解释得很好。 这个想法是，如果您向前扫描一个数字，则必须累积扫描的数字的总值，然后将其添加。 如果向后扫描，则可以随时将其添加到累计总数中。 我的潜意识对自己有一定的意义（后面会提到），但是我错过了一个关键点，在其中一个答案中指出了：向后扫描，每次迭代都进行两次乘法，但是向前扫描你只需要一个。 所以我编码了一个正向扫描版本：
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秒内运行，击退向后扫描版本的距离。 尼斯。
乘法caching
但是，我在夜间意识到的是，尽pipe我每次迭代执行两次乘法运算，但仍有可能使用caching来存储这些乘法运算，这样我可以避免在向后迭代过程中执行这些乘法运算。 我很高兴看到当我醒来时，有人有同样的想法！
问题是，我们正在扫描的数字中最多只有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秒内运行。 令人失望的，至less可以说。 在I / O方面，向后读取效率不高，但是我们已经看到I / O不是这里最头痛的问题。 我曾预料到这会带来很大的积极影响。 也许arrays查找和我们所取代的乘法一样昂贵。 （我曾尝试制作16x16arrays，并使用bitshifts进行索引，但没有帮助。）
看起来向前扫描是在哪里。
使用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秒 。 我们已经取消了我们个人最好的一秒！
那么multithreading呢？
其中一个build议的答案涉及使用多个核心。 我有点惭愧，那是我没有想到的！
答案来了一些棒，因为这是一个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 。 原因是我们想保持顺序的磁盘访问。 我们将采取相当大的块，叉/join，然后移动到下一个块。
这是做这个的方法。 请注意，我们已经将缓冲区大小推到了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; }
现在这里是令人心碎的失望：这个很好的multithreading代码现在需要32.2秒 。 为什么这么慢？ 我花了很长一段时间debugging这个，假设我做了一些非常错误的事情。
结果只有一个小小的调整需要。 我认为在小问题和大问题之间64的门槛是合理的; 事实certificate，这是完全荒谬的。
像这样想想。 子问题的大小完全相同，所以它们应该几乎在同一时间完成。 所以没有什么比分配处理器更重要的东西了。 在我使用的机器上，只有两个内核，下降到64的阈值是荒谬的：它只是增加了更多的开销。
现在你不想限制事物，所以即使有更多的可用，它也只使用两个核心。 也许正确的做法是在运行时找出处理器的数量，并将其分成许多部分。
在任何情况下，如果我将阈值更改为512KB（缓冲区大小的一半），则现在在13.3秒内完成。 下降到128KB或64KB将允许使用更多的内核（分别高达8或16），并且不会显着影响运行时间。
所以multithreading确实有很大的不同。
这是一段相当漫长的旅程，但是我们开始的时间是92.9秒，现在是13.3秒，这是原始码速度的七倍 。 而这并不是通过改善渐近（大哦）的时间复杂度，从一开始就是线性的（最优的）…这一切都是为了改善常数因子。
一天的工作。
我想我应该尝试下一步使用GPU …
后记：生成随机数的文件
我用下面的代码生成了随机数字，我运行并redirect到一个文件。 显然，我不能保证你会得到完全一样的随机数，我有:)
public static void genRandoms() { Random r = new Random(); for (int i = 0; i < 100000000; i++) System.out.println(r.nextInt(1000000000)); }
我认为还有另外一种方法。
这是传统的多进程编程问题。 在C语言中有库MPI可以解决这类问题。
它的思想是将整数列表分成4部分，每部分按不同的过程进行汇总。 完成后，stream程汇总在一起。
在java中，这可以通过线程（伪并行）和java并发来完成。
例如，4个不同的线程总结列表的4个不同部分。 最后他们总结在一起。
电话公司使用这种并行编程技术的网格计算机对其事务进行求和。
这里唯一的问题（瓶颈）是IO操作。 读取文件将需要很多时间。 如果以某种方式，你可以让多个线程读取文件的不同部分…这是非常复杂的方法，我认为这不会有太大的好处，因为磁盘不会因为被许multithreading使用而旋转得更快，其他做类似的东西的技术。 你可以在这里阅读更多关于这个： 通过multithreading访问文件和在这里读 多个线程 的单个文件：应该加快？
你的主要瓶颈将是文件IO。 parsing和累加数字不应该影响algorithm，因为可以在File I / O正在等待磁盘时在单独的线程中完成。
几年前我研究了如何以最快的方式从文件中读取数据，并且遇到了一些很好的build议 – 我把它作为一个扫描例程来实现，如下所示：
// 4k buffer size. static final int SIZE = 4 * 1024; static byte[] buffer = new byte[SIZE]; // Fastest because a FileInputStream has an associated channel. private static void ScanDataFile(Hunter p, FileInputStream f) throws FileNotFoundException, IOException { // Use a mapped and buffered stream for best speed. // See: http://nadeausoftware.com/articles/2008/02/java_tip_how_read_files_quickly final FileChannel ch = f.getChannel(); long red = 0L; do { final long read = Math.min(Integer.MAX_VALUE, ch.size() - red); final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, red, read); int nGet; while (mb.hasRemaining() && p.ok()) { nGet = Math.min(mb.remaining(), SIZE); mb.get(buffer, 0, nGet); for (int i = 0; i < nGet && p.ok(); i++) { p.check(buffer[i]); //size += 1; } } red += read; } while (red < ch.size() && p.ok()); // Finish off. p.close(); ch.close(); f.close(); }
在testing它的速度之前，你可能希望调整这个技术，因为它利用一个名为Hunter的接口对象来search数据。
正如你所看到的，这个build议是在2008年推出的，从那以后，Java已经有很多增强function，所以这可能不会提供改进。
添加
我没有testing过这个，但这应该适合你的testing，并使用相同的技术：
class Summer { long sum = 0; long val = 0; public void add(byte b) { if (b >= '0' && b <= '9') { val = (val * 10) + (b - '0'); } else { sum += val; val = 0; } } public long getSum() { return sum + val; } } private long sumMapped() throws IOException { Summer sum = new Summer(); FileInputStream f = new FileInputStream(file); final FileChannel ch = f.getChannel(); long red = 0L; do { final long read = Math.min(Integer.MAX_VALUE, ch.size() - red); final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, red, read); int nGet; while (mb.hasRemaining()) { nGet = Math.min(mb.remaining(), SIZE); mb.get(buffer, 0, nGet); for (int i = 0; i < nGet; i++) { sum.add(buffer[i]); } } red += read; } while (red < ch.size()); // Finish off. ch.close(); f.close(); return sum.getSum(); }
为什么这么快？
创build一个string比一个小math要贵得多。
通过使用MappedByteBuffer帮助，我们可以做得更好吗？
有一点，是的。 它是我使用的。 它将内存保存到内存拷贝中。 即不需要byte []。
我有一种感觉，调用方法从缓冲区中读取的开销会减慢速度，
如果方法简单，则方法被内联。
特别是当从缓冲区向后读取时。
它不会更慢，事实上parsing向前更简单/更快，因为你使用一个而不是两个。
向前读取文件而不是向后读取文件会更好，但是仍然向后扫描缓冲区？
我不明白你为什么需要往后看。
这个想法是，你读取文件的第一个块，然后向后扫描，但在最后丢弃半数。 然后，当你读下一个块时，你设置偏移量，以便你从你丢弃的数字开始读取。
听起来不必要的复杂。 我会一次性读取整个文件中的内存映射。 除非文件大小为2+ GB，否则不需要使用块。 即使如此，我也会一口气读完。
有什么我没有想到的，可以做出重大的改变？
如果数据在磁盘caching中，它会比其他任何东西都有更多的不同。
你可以去更大的缓冲区大小，更快的编码到string（到Unicode）。
BufferedReader br = new BufferedReader(new InputStreamReader( new FileInputStream(file), StandardCharsets.US_ASCII), 1_024_000_000);
你使用二进制InputStream / RandomAccessFile消除String使用的方法是值得的。
那么如果源文件被压缩，它也可能会很好。 在Unix下，可以selectgzip格式，其中xxx.txt.gz解压缩为xxx.txt 。 这将是可读的GZipInputStream 。 它具有整体加速文件传入和传出服务器目录的优点。
资料来源： http : //nadeausoftware.com/articles/2008/02/java_tip_how_read_files_quickly
为了获得最佳的Java读取性能，需要记住四点：
- 通过一次读取一个数组，而不是一次一个字节，最大限度地减lessI / O操作。 一个8K字节的arrays是一个好的尺寸。
- 通过一次获取数组数据来最小化方法调用，而不是一次一个字节。 使用数组索引来获取数组中的字节。
- 如果您不需要线程安全性，请最小化线程同步locking。 要么对线程安全的类进行更less的方法调用，要么使用像FileChannel和MappedByteBuffer这样的非线程安全的类。
- 尽量减lessJVM / OS，内部缓冲区和应用程序arrays之间的数据复制。 使用带有内存映射的FileChannel，或直接或包装数组ByteBuffer。
根据这个评论 ：“简单地总结所有的字节更快”，我提出了一个接受的答案的变化。
接受的答案提出将问题分解成块，使用multithreading计算每个卡盘的总和，并在最后加起来。
这个想法可以用来减less向后扫描中O（1）的乘法次数，不需要查找任何表，也不需要线程（或者把它和线程结合起来）。 简单地利用乘法分配加法的方式，并将所有的数字加到一个累加器中，数十个分别放入一个单独的累加器中，成百上千个累加器。 这不需要乘法。
也可以使用每个位置的累加器来完成多个线程的缩减步骤组合结果。 计算总和的最后一步将需要乘法（或者利用10只有两个位被设置并使用位移和相加的事实），但是只有9次乘法就足够了。
这里有几个问题。
- 任何基于读线的解决scheme都会处理每个字符两次。 编译器例如不这样做，他们一次只读一个字符并直接发送。
- 任何基于
readLine()解决scheme都将创buildstring。 - 您正在使用不同的缓冲区大小。
- 您正在使用不同的I / O技术。
- 在某些情况下，您正在使用字符转换，而在其他情况下则不是。
- 你正在分析文件。 只要将数字彼此分开，你就不会在乎空白的地方，或者有多less空间。
我的解决scheme
BufferedInputStream bis = new BufferedInputStream(new FileInputStream(file), 8*1024*1024/2); long total = 0; int i; while ((i = bis.read()) != -1) { byte b = (byte)i; long number = 0; while (b >= '0' && b <= '9') { number = number*10+b-'0'; if ((i = bis.read()) == -1) break; b = (byte)i; } total += number; }
