在Java中尽快加载五千万个整数

我正在通过Euler项目工作。许多问题涉及素数计算：这是可以提取到单独的类中并重用的代码类型。

虽然可以使用某些方法快速完成素数的计算，但我能够通过使用磁盘上的质数列表并加载它们来加快“获取质数”的过程。它比任何计算都快一个数量级，但从SSD加载仍需要大约三分钟。

我所做的： -前五千万个质数的可用列表（某些问题确实使用了这些数字的很大一部分）。
我编写了一个程序，使用Java的DataOutputStream将数字从其文本表示形式转换为二进制形式。该文件只是连续五千万个四字节整数。
下面的实用程序方法使用DataInputStream将每个整数加载到数组中。它可以产生正确的结果，但是速度很慢。

有什么方法可以加快加载50,000,000个整数的过程吗？如果我需要对数据进行不同的预处理，我愿意这样做。

 import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;

public class Test {

  public static int[] loadByQuantity(int argNumPrimes) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (DataInputStream in = new DataInputStream(new FileInputStream("primes.bin"))) {
      for (int i = 0; i < primes.length; ++i) {
        primes[i] = in.readInt();
      }
    }
    catch (IOException ex) {
      throw new RuntimeException(ex);
    }
    return primes;
  }

}

如何加载50.000.000亿个整数需要这么长时间（严重3分钟？）？它只有190 MB。在任何机器上只需要一秒钟的时间（即使没有SSD，最多也要花几秒钟）。

@DarioOO很好的问题，这就是为什么我问。事实证明，这是有充分理由的，因为在您的评论之前已发布了答案。

您应该生成它们。我已经经历了前120个问题，而不需要使用sqrt（1e9）（〜= 31k）质数。

@DarioOO，因为他正在阅读每个素数，而不是阅读更大的块。当前代码具有5000万个“磁盘”操作。如果他一次读取一个兆字节，那么只需几秒钟即可完成。

将FileInputStream包装在BufferedInputStream中。会创造奇迹。

#1 楼

您的代码有点混乱，将文件名硬编码到函数中并不好。另外，“匈牙利符号”（使用arg之类的东西作为函数参数的前缀-顺便说一句，它是一个参数，而不是参数）...不是常规的。

我理解这是测试性能的一种方法。...这还与代码的可重用性有关。

我仍然从经验中知道会发生可重用性

我还从经验中知道，Java中的内存映射IO比其他IO形式要快得多，所以我认为自己可以解决这个问题。 >
我使用了之前在Code Review上回顾过的我的素数生成器（Thread Safe Prime Generator），并在我自己的系统上的文件中生成了前50,000,000个素数，然后针对它测试了您的代码将文件名更改为参数即可。）

出于兴趣，生成和写入素数文件在我的计算机上花费了大约5分钟-311秒-muc h可能也是IO时间。

然后，我将您的函数转换为：

public static int[] loadByQuantity(int argNumPrimes, String fname) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (DataInputStream in = new DataInputStream(new FileInputStream(fname))) {
        for (int i = 0; i < primes.length; ++i) {
            primes[i] = in.readInt();
        }
    } catch (IOException ex) {
        throw new RuntimeException(ex);
    }
    return primes;
}

唯一的区别是文件-名称现在是一个参数。

然后我写了一个小测试系统来计时您的代码花了我多长时间：

public static void time(Supplier<int[]> task, String name) {
    long nanos = System.nanoTime();
    int[] primes = task.get();
    System.out.printf("Task %s took %.3fms\n", name, (System.nanoTime() - nanos) / 1000000.0);
    System.out.printf("Count %d\nFirst %d\nLast %d\n", primes.length, primes[0], primes[primes.length - 1]);
    System.out.println("----");
}

public static void main(String[] args) {
    int count = 50000000;
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
}

我然后使用内存映射IO的NIO机制实现了相同的功能：http://docs.oracle.com/javase/8/docs/api/java/nio/MappedByteBuffer.html

此类型IO的设计旨在显着减少由输入文件制成的内存副本的数量。这也意味着Java从操作系统中读取内容，而无需先将其复制到Java的内存空间中。

此外，MappedByteBuffer具有方法getInt()，该方法还可以为您将4个字节解码为int：http://docs.oracle.com/javase/8/docs/api/java/nio/ByteBuffer.html#getInt--

这是我想出的代码。注意，我使用了与您使用的相同的异常处理以及相同的数组初始化。我相信您应该从这些方法引发异常，而不仅仅是将它们包装在运行时异常中：

public static int[] loadByNIO(int argNumPrimes, String fname) {
    int numPrimes = Math.min(argNumPrimes, 50_000_000);
    int[] primes = new int[numPrimes];
    try (FileChannel fc = FileChannel.open(Paths.get(fname))) {
        MappedByteBuffer mbb = fc.map(MapMode.READ_ONLY, 0, numPrimes * 4l);
        for (int i = 0; i < numPrimes; i++) {
            primes[i] = mbb.getInt();
        }
    } catch (IOException ex) {
        throw new RuntimeException(ex);
    }
    return primes;
}

然后我在main方法中运行了几次该过程，并比较结果： >

public static void main(String[] args) {
    int count = 50_000_000;
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
    time(() -> loadByNIO(count, "primes.dat"), "NIO");
    time(() -> loadByQuantity(count, "primes.dat"), "OP");
    time(() -> loadByNIO(count, "primes.dat"), "NIO");
}

我承认，它也比我预期的要快得多。。但是，结果是正确的。

现在，我鼓励你尝试将这一概念放在Java流之后，而不是将整个50,000,000填充到数组中。通过流式传输结果，您可以更快地开始“真实”计算，而不必等待从文件中读取所有素数的等待时间。例如，考虑使用逻辑可以做什么：

Task OP took 214163.250ms
Count 50000000
First 2
Last 982451653
----
Task NIO took 141.511ms
Count 50000000
First 2
Last 982451653
----
Task OP took 214633.128ms
Count 50000000
First 2
Last 982451653
----
Task NIO took 159.571ms
Count 50000000
First 2
Last 982451653
----

质数从文件中按需读取值。

这是我一直在运行的完整代码：

primes.stream().....

\ $ \ begingroup \ $
我不是唯一一个惊讶于Java的内存映射I / O更快的人，我对此感到宽慰。（或者，我应该说，有多少开销流。）我相信这会产生很大的变化，但是其数量确实令人惊讶。
\ $ \ endgroup \ $
– 5gon12eder
17年1月28日在21:14

\ $ \ begingroup \ $
感谢你们两个都建议使用内存映射文件。这个答案非常彻底，我很欣赏比较和基准。我将尝试一下，看看是否能获得相同的结果（应该）。关于命名-这是我在前雇主那里养的一个坏习惯（这是他们的编码标准）。我正在尝试删除它，但有时它会潜回去。
\ $ \ endgroup \ $
–user31517
17年1月28日在22:10

\ $ \ begingroup \ $
值得注意的是，在我的机器上以700ms的速度添加如此处所述的BufferedInputStream，这比214秒要好得多，但不及NIO的140ms
\ $ \ endgroup \ $
–rolfl
17年1月29日在5:43

\ $ \ begingroup \ $
实际上，在通常情况下，内存映射的IO根本不执行任何IO，因为文件通常被缓存在磁盘缓冲区中（很有可能“仅” 50m整数，即200 MB文件）-磁盘缓存页面只是直接映射到进程空间，您就可以像读取其他任何内存源一样从它们读取数据。在本机语言中，您可以将其直接用作基础数组，但是在Java中，托管数组之间的不匹配是“直接缓冲区”。您可以简单地将ByteBuffer输入到算法中，然后直接使用数字。
\ $ \ endgroup \ $
–BeeOnRope
17年1月29日在15:28

\ $ \ begingroup \ $
之所以更快，是因为操作系统从上次读取开始将磁盘文件缓存在内存中。
\ $ \ endgroup \ $
–索比昂·拉文·安德森（ThorbjørnRavn Andersen）
17年1月30日在12:18

#2 楼

使用BufferedInputStream将是一种快速解决方案，只需对当前代码进行较小的修改。 DataInputStream只需加载文件块以减少所需的IO操作数量。另一种解决方案是使用read（）方法将文件的（全部或部分）加载到字节数组中，然后从字节数组中检索这些整数。

\ $ \ begingroup \ $
欢迎使用代码审查！我给您+1是因为您已经指出了原始代码中的一个简单但重要的疏忽，而任何现有答案都未提及。如果您使用某种推理来扩充它，并且（理想情况下）还显示一些数据，您的答案将会更强。对我来说，包装一个额外的BufferedInputStream可以使速度提高30倍，这非常了不起。
\ $ \ endgroup \ $
– 5gon12eder
17年1月29日在2:04

\ $ \ begingroup \ $
BufferedInputStream是一个很好的建议。我将其添加到性能测试中，并将214秒的读取时间提高到仅700毫秒（这很好，但不如140ms的NIO那样好）
\ $ \ endgroup \ $
–rolfl
17年1月29日在5:42

#3 楼

考虑内存映射文件

免责声明：这也是我第一次使用Java来处理内存映射文件。我的操作方式可能不是最佳选择，甚至更糟。解决问题的最快方法就是将文件DataInputStream放入内存，假设它包含主机本地字节顺序的32位整数压缩数组。

这是解决方案我想出了。

static int[] load(final File file, final int n) throws IOException {
    try (final FileChannel channel = FileChannel.open(
            file.toPath(),
            StandardOpenOption.READ
    )) {
        final MappedByteBuffer mapping = channel.map(
            FileChannel.MapMode.READ_ONLY,
            0,                 // offset
            n * Integer.BYTES  // length
        );
        mapping.order(ByteOrder.nativeOrder());
        final IntBuffer integers = mapping.asIntBuffer();
        final int[] array = new int[n];
        integers.get(array);
        return array;
    }
}

为了写数据，我使用了以下函数。

static void store(final File file, final int[] array) throws IOException {
    try (final FileChannel channel = FileChannel.open(
            file.toPath(),
            StandardOpenOption.READ,
            StandardOpenOption.WRITE,
            StandardOpenOption.CREATE,
            StandardOpenOption.TRUNCATE_EXISTING
    )) {
        final MappedByteBuffer mapping = channel.map(
            FileChannel.MapMode.READ_WRITE,
            0,                            // offset
            array.length * Integer.BYTES  // length
        );
        mapping.order(ByteOrder.nativeOrder());
        final IntBuffer integers = mapping.asIntBuffer();
        integers.put(array);
    }
}

我已经使用50M随机整数数组对这些函数进行了基准测试。加载数组后，我还计算了其总和并将其打印出来，以确保没有优化加载操作。结果是使用mmap() Shell工具获得的，因此还包括随机数据的生成，JVM启动和任何其他开销。结果仍然非常清楚。 >我相信我不会在这里告诉您任何新信息，只是为了记录：将用于从文件中读取整数数组的逻辑与解释这些整数（作为质数）的逻辑分离。也不要将文件名或数组的大小硬编码到加载它们的函数中。

不要伪装异常

Java是否“处理它或声明它”关于例外的哲学是一个好主意，值得商debate。但是，考虑到它的现状，我认为对系统进行工作没有帮助。我们要与现在的生活一起生活。

当心规则

我只是简单地研究了Euler项目，不知道他们的规则，但是如果从外部资源加载数据被认为是作弊行为，我不会感到惊讶。当然，如果您只是出于娱乐目的而这样做，则可以自由设置自己的规则。

#4 楼

对于素数，您的初始假设是错误的。在几乎所有情况下，筛选都比从磁盘读取更快。

以primesieve为例，在最近的Intel CPU上生成前10 ^ 9个素数需要0.05s。为了“比任何计算都快一个数量级”，您需要使读取时间低于5ms。内存映射方法甚至不在那个球场上。

最大的优化是使用Eratosthenes的真正筛子。实际上是试用版的Phony版本非常常见。与mod 30轮一起使用时，您应该在纯Java方面领先于I / O，但要落后于像primesieve这样经过高度优化的东西。素数。关键在于，生成素数实际上比尝试加载素数更快。（计数用作基准，因为即使在屏幕上打印列表也要比筛分花费更长的时间。）原始代码的全部前提是，它比不正确的I / O快几个数量级。我只是指出要获得更大的算法性能。

要明确一点，那就是仅在质数的情况下。加载数百万个任意整数将是一个不同的命题，其中所有其他答案都将非常有帮助。

为了清楚起见，我不建议对primesieve库进行本机绑定，实现细分的筛子（对于如此少量的素数来说会过分杀伤）或其他任何疯狂的东西。我只是指出，在纯Java中，单线程的简单筛子和砂轮可能会更健壮，更省力（无需担心I / O异常，无需将文件添加到项目等），并且比从磁盘读取它们。就像在边缘情况下“慢速”排序算法最快一样。

至于有关内存带宽的评论，这里有两个安全的假设。 1）素数列表将用于某些事物。 2）如果它们是即时生成的，则存在很大的变化，它们在使用时仍将保留在缓存中。

总结需要整数而不是位域。对于这么少的素数列表，您无论如何都会简单地筛选一个整数数组。即使您出于任何原因使用压缩列表来节省空间并需要填充数组，也将是一个完全没有问题的问题，因为原始问题是从文本文件中读取素数。那是到cpu并解析数字的往返，这样可能会做更多工作。 ]

\ $ \ begingroup \ $
我明白了。公平地说，IO（在正确的情况下）可能非常快，但不会快10倍！如果您对文件进行内存映射并且已经被缓存，则IO是无操作的，您可以直接使用缓冲区缓存中的内存映射页面。这通常以大约memcpy的速度工作。公平地说，0.05中的10 ^ 9素数是相当不可思议的。假设4字节素数，即4 GB / 0.05s = 100 GB / s，远远超出了典型4核系统的内存带宽（通常达到25 GB / s左右）。所以我什至不知道这怎么可能（也许在GPU上？）。
\ $ \ endgroup \ $
–BeeOnRope
17年1月29日在16:34

\ $ \ begingroup \ $
...查看primesieve页面上的基准结果，我想您的意思是“可以在0.05秒内找到所有小于10 ^ 9的质数”，而不是“生成前10 ^ 9个质数... ”。这样就好像前5000万个素数。
\ $ \ endgroup \ $
–BeeOnRope
17年1月29日在16:37

\ $ \ begingroup \ $
还值得注意的是，引用页面上的基准测试同时使用8个CPU内核。从本质上讲，这并不是一件坏事，但是，在基于IO的系统中更聪明地使用其他7个内核将使它们有时间在加载质数的同时使用质数，而不是在生成时就消耗所有CPU资源。此外，基准测试只计算了素数（是的，“简单”），但是如果必须以int格式填充所有这些素数的数组，则会降低速度。这些小差异可能会产生很大的影响，具体取决于您对素数的处理方式。
\ $ \ endgroup \ $
–rolfl
17年1月29日在20:16

\ $ \ begingroup \ $
“伪筛”的问题仅真正适用于像Haskell这样的函数式编程语言，在该函数编程语言中，有许多可爱的一类衬板会产生质数，表面上似乎遵循该算法，但实际上只是变相的试验划分。像Java这样的命令式语言没有这个问题，因为它们通常没有那些可爱的衬里。两种样式正确执行所需的代码量大致相同。
\ $ \ endgroup \ $
–詹姆斯·霍利斯（James Hollis）
17年1月31日在15:55

\ $ \ begingroup \ $
从理论上讲，从文件中加载比筛子要快，这是因为即使理论上最好的筛子也将以O（n）为界，而从文件中加载是O（m ），其中m是素数（不是输入大小）。对于足够大的n，m为log log n，因此从文件加载理论上为O（log log n）。实际上，这个交叉点将非常大
\ $ \ endgroup \ $
– mirhagk
17年1月31日在21:05

#5 楼

一个BitSet

每个奇数一个位，最大为1,000,000,000，如果设置为质数。那是50847533质数，不包括2。应该花费大约64MB，而整数数组需要200MB。对于任何奇数，您都应除以2并查找该索引。

顺便说一句，一个相当简单的Eratosthenes筛网用不到30分钟即可筛分Java中的十亿个数字，更像是十秒钟。这个例子就是这样做的。

\ $ \ begingroup \ $
除此之外，“对于某些k，每个素数都可以表示为30k±1、30k±7、30k±11或30k±13”stackoverflow.com/questions/2614147/…
\ $ \ endgroup \ $
– JollyJoker
17年1月30日在9:39

\ $ \ begingroup \ $
以这种大小，您最好使用BitSet-请参见此答案。
\ $ \ endgroup \ $
–蜘蛛鲍里斯（Boris）
17年1月30日在10:15

\ $ \ begingroup \ $
此外，零的游程长度编码可能会有所帮助。每30个数字1字节将为您提供30兆字节= 240兆字节的数据，最多可容纳10亿个质数，但由于其中只有5000万个是1，因此您会长时间零。
\ $ \ endgroup \ $
– JollyJoker
17年1月30日在12:51

\ $ \ begingroup \ $
@鲍里斯，您是对的，我认为布尔数组将以BitSet实际的方式表示，而实际上并未听说过BitSet。布尔数组实际上过筛的速度稍快一些，但比简单的质数数组紧凑，因此我将所有内容都切换到了BitSet上。我的示例在那里展示了数据结构，而不仅仅是Eratosthenes筛。
\ $ \ endgroup \ $
–詹姆斯·霍利斯（James Hollis）
17年1月30日在16:42

编程黑洞网