首页 ❯

在文本文件中对整数求和的最快方法问题方法1：自然方法方法2：小幅调整方法 3：手动解析整数方法 4：以二进制文件进行处理后续问题更新：更多令人惊讶的结果

performance file-io java
2022-08-31 22:13:59

问题

假设您有一个大型 ASCII 文本文件，每行都有一个随机的非负整数，每行的范围从 0 到 1，000，000，000。文件中有 100，000，000 行。通读文件并计算所有整数之和的最快方法是什么？

约束：我们有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，这仍然很容易适应 a ，因此我们不必担心溢出。long

在我的机器上，运行 11 次并打折第一次运行大约需要 92.9 秒。

方法2：小幅调整

受到对这个问题的评论的启发，我尝试不创建一个新的来存储解析行的结果，而只是将解析的值直接添加到.所以这个：int ktotal

    while ((line = br.readLine()) != null) {
        int k = Integer.parseInt(line);
        total += k;
    }

变成这个：

    while ((line = br.readLine()) != null)
        total += Integer.parseInt(line);

我确信这不会有任何区别，并认为编译器很可能会为两个版本生成相同的字节码。但是，令我惊讶的是，它确实缩短了一点时间：我们下降到92.1秒。

方法 3：手动解析整数

到目前为止，关于代码困扰我的一件事是，我们将 转换为 ，然后在最后添加它。随着我们的前进，添加不是更快吗？如果我们解析自己会发生什么？像这样的东西...StringintString

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：以二进制文件进行处理

我们可以尝试的最后一件事是将文件作为二进制数据进行处理。

如果您不知道整数的长度，则从前面解析该整数很尴尬。向后解析要容易得多：您遇到的第一个数字是单位，下一个数字是十，依此类推。因此，处理整个事情的最简单方法是向后读取文件。

如果我们分配一个（比如）8MB的缓冲区，我们可以用文件的最后8MB填充它，处理它，然后读取前面的8MB，依此类推。我们需要小心一点，当我们移动到下一个块时，我们不会搞砸一个我们正在解析的数字，但这是唯一的问题。byte[]

当我们遇到一个数字时，我们将其（根据其在数字中的位置适当地相乘）与总数相加，然后将系数乘以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. 我们能通过使用 a 来提供帮助来做得更好吗？我有一种感觉，调用方法从缓冲区读取的开销会减慢速度，尤其是在从缓冲区向后读取时。MappedByteBuffer
  3. 向前而不是向后读取文件，但仍然向后扫描缓冲区会更好吗？这个想法是，您读取文件的第一个块，然后向后扫描，但丢弃末尾的半数。然后，当您读取下一个块时，您可以设置偏移量，以便从丢弃的数字的开头开始读取。
  4. 有没有我没有想到的东西可以产生重大影响？

更新：更多令人惊讶的结果

首先，观察。我以前应该想到过，但我认为基于读取的效率低下的原因不在于创建所有对象所花费的时间，而在于它们是如此短暂的事实：我们有100，000，000个对象供垃圾收集器处理。这势必会使它感到不安。StringString

现在，一些实验基于人们发布的答案/评论。

我是否在欺骗缓冲区的大小？

一个建议是，由于a使用默认的16KB缓冲区，而我使用的缓冲区为8MB，所以我不会比较喜欢和喜欢。如果您使用更大的缓冲区，它肯定会更快。BufferedReader

这是令人震惊的。该方法（方法4）昨天以8MB缓冲区在30.8秒内运行。今天，代码保持不变，风向已经改变，我们处于30.4秒。如果我把缓冲区大小减小到16KB，看看它的速度有多慢，它就会变得更快！它现在在23.7秒内运行。疯狂。谁看到那个人来了？！sumBinary()

一些实验表明，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，并使用bitshifts来编制索引，但这没有帮助。

看起来前向扫描就是它所处的位置。

使用映射字节缓冲区

接下来要添加的是 一个 ，看看这是否比使用 raw 更有效。它不需要对代码进行太多更改。MappedByteBufferRandomAccessFile

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的结果，这似乎有点苛刻！无论如何，当然值得一试。

我们将使用分叉/连接来完成此操作。下面是一个类，用于表示对文件部分进行计算的结果，请记住，左侧可能有部分结果（如果我们从数字开始一半），右侧可能有部分结果（如果缓冲区在数字的一半处完成）。该类还有一种方法，允许我们将两个这样的结果粘合在一起，形成两个相邻子任务的组合结果。

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;
    }
}

现在是密钥位：计算结果的位。对于小问题（少于64个字符），它调用以计算单个线程中的结果;对于较大的问题，它分成两个，在单独的线程中解决两个子问题，然后将结果合并。RecursiveTaskcomputeDirectly()

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秒......这是原始代码速度的七倍。这并不是通过提高渐近（大哦）时间复杂度，从一开始就是线性（最佳）的......这一切都是为了改善恒定因子。

美好的一天工作。

我想我接下来应该尝试使用GPU...

后记：生成随机数文件

我使用以下代码生成了随机数，并运行并重定向到文件。显然，我不能保证你最终会得到与我完全相同的随机数:)

public static void genRandoms() {
    Random r = new Random();
    for (int i = 0; i < 100000000; i++)
        System.out.println(r.nextInt(1000000000));
}

答案 1

您的主要瓶颈将是文件 IO。解析和相加数字不应对算法产生影响，因为这可以在文件 I/O 等待磁盘时在单独的线程中完成。

几年前，我研究了如何以最快的方式读取文件，并遇到了一些很好的建议 - 我将其实现为扫描例程，如下所示：

// 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();
}

您可能希望在测试其速度之前调整此技术，因为它正在使用称为 a 的接口对象来查找数据。Hunter

正如你所看到的，这个建议是在2008年派生的，从那时起，Java已经得到了许多增强，所以这可能不会提供改进。

添加

我还没有测试过这个，但这应该适合你的测试并使用相同的技术：

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();
}

答案 2

为什么这要快得多？

创建字符串比一点点数学要昂贵得多。

我们能通过使用MappedByteBuffer帮助来做得更好吗？

一点点，是的。这是我使用的。它将内存保存到内存副本，即不需要字节[]。

我有一种感觉，调用方法从缓冲区读取的开销会减慢速度，

如果这些方法很简单，则内联这些方法。

特别是当从缓冲区向后读取时。

它不会变慢，事实上，向前解析更简单/更快，因为你使用一个而不是两个。*

向前而不是向后读取文件，但仍然向后扫描缓冲区会更好吗？

我不明白为什么你需要倒着读。

这个想法是，您读取文件的第一个块，然后向后扫描，但丢弃末尾的半数。然后，当您读取下一个块时，您可以设置偏移量，以便从丢弃的数字的开头开始读取。

听起来不必要地复杂。我会一次性读取整个文件中的内存映射。无需使用块，除非文件的大小超过 2 GB。即使这样，我也会一口气读完。

有没有我没有想到的东西可以产生重大影响？

如果数据位于磁盘缓存中，它将比其他任何东西都大。


推荐
更多 »
标签
更多 »
php pass-by-reference optional-parameters default-value javascript arrays dom function string object serialization tostring visibility syntax jslint use-strict operators equality equality-operator identity-operator datetime timestamp date-arithmetic redirect angularjs loops foreach iteration scope variables
推荐
更多 »