最快的方法来整理文本文件中的整数

假设你有一个大的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倍的速度增加

后续问题

  1. 为什么这么快? 我期待着它能赢,但不是那么令人印象深刻。 它主要是转换为String的开销? 而所有关于字符集之类的背景都令人担忧?
  2. 我们可以通过使用MappedByteBuffer来帮助吗? 我有一种感觉,调用方法从缓冲区中读取的开销会减慢速度,特别是从缓冲区向后读时。
  3. 向前读取文件而不是向后读取文件会更好,但是仍然向后扫描缓冲区? 这个想法是,你读取文件的第一个块,然后向后扫描,但在最后丢弃半数。 然后,当你读下一个块时,你设置偏移量,以便你从你丢弃的数字开始读取。
  4. 有什么我没有想到的,可以做出重大的改变?

更新:更令人惊讶的结果

首先是观察。 我之前应该已经想到了,但是我认为基于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次乘法就足够了。

这里有几个问题。

  1. 任何基于读线的解决scheme都会处理每个字符两次。 编译器例如不这样做,他们一次只读一个字符并直接发送。
  2. 任何基于readLine()解决scheme都将创buildstring。
  3. 您正在使用不同的缓冲区大小。
  4. 您正在使用不同的I / O技术。
  5. 在某些情况下,您正在使用字符转换,而在其他情况下则不是。
  6. 你正在分析文件。 只要将数字彼此分开,你就不会在乎空白的地方,或者有多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; }