问题：

对文本文件中的整数求和的最快方法

陈铭晨

2023-03-14

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

限制：我们有 10MB 的 RAM 可以使用。该文件的大小为1GB，因此我们不想读取整个内容然后对其进行处理。

以下是我尝试过的各种解决方案。我发现结果相当令人惊讶。

我错过了什么更快的吗？

请注意：下面给出的所有计时总共运行算法 10 次（运行一次并丢弃;启动计时器;运行 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 秒。

受到对这个问题的评论的启发，我尝试不创建一个新的 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，然后在末尾添加它。我们边走边加不是更快吗？如果我们自己解析字符串会发生什么？像这样的东西...

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 倍。

为什么这快这么多？我期待它能赢，但不是那么令人印象深刻。主要是转换为字符串的开销吗？以及所有关于角色集之类的幕后担忧？
通过使用MappedByteBuffer来提供帮助，我们能做得更好吗？我有一种感觉，调用方法从缓冲区读取的开销会减慢速度，尤其是在从缓冲区向后读取时。
比向后读取文件更好，但仍向后扫描缓冲区会更好吗？这个想法是，你读取文件的第一个块，然后向后扫描，但在最后丢弃半个数字。然后，当您读取下一个块时，设置偏移量，以便从丢弃的数字的开头读取。
有什么我没有想到的可以产生重大影响吗？

首先，观察。我之前应该想到过，但我认为基于 String 的读取效率低下的原因不是创建所有 String 对象所花费的时间，而是它们寿命太短的事实：我们有 100，000，000 个供垃圾收集器处理。这势必会打扰它。

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

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

这是震惊。sumBinary（）方法（方法 4）昨天在 30.8 秒内运行，使用 8MB 缓冲区。今天，代码不变，风向发生了变化，我们的时间是30.4秒。如果我将缓冲区大小降低到 16KB 以查看它变慢了多少，它会变得更快！它现在在 23.7 秒内运行。疯狂。谁看到那个人来了？！

一些实验表明，16KB大约是最佳的。也许Java的人做了同样的实验，这就是为什么他们选择了16KB！

我也想知道这一点。在磁盘访问上花费了多少时间，在数字运算上花费了多少时间？如果几乎都是磁盘访问，正如对其中一个提议的答案的充分支持的评论所建议的那样，那么无论我们做什么，我们都无法做出太大的改进。

这很容易通过运行代码来测试，并注释掉所有解析和数字处理，但读数仍然完好无损：

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 的时间命令确认），这足以试图减少它。

我在最初的帖子中坚持认为，有充分的理由向后而不是向前扫描文件。我没有很好地解释。这个想法是，如果你向前扫描一个号码，你必须累积扫描号码的总值，然后添加它。如果向后扫描，则可以将其添加到累积总计中。我的潜意识对自己有某种意义（稍后会详细介绍），但我错过了一个关键点，其中一个答案中指出了这一点：向后扫描，我每次迭代都要做两次乘法，但是向前扫描，你 n只有一个。所以我编写了一个正向扫描版本：

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，看看它是否比使用原始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;
    }
}

现在是关键位：计算结果的递归任务。对于小问题（少于 64 个字符），它调用 computeDirect（） 在单个线程中计算结果;对于较大的问题，它会一分为二，在单独的线程中解决两个子问题，然后合并结果。

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

共有3个答案

麻昌翰

2023-03-14

你可以选择更大的缓冲区大小，以及更快的编码到字符串（到 Unicode）。

BufferedReader br = new BufferedReader(new InputStreamReader(
        new FileInputStream(file), StandardCharsets.US_ASCII),
        1_024_000_000);

通过使用二进制 InputStream/RandomAccessFile 来消除字符串使用的方法值得。

那么如果源文件被压缩，那也可能很好。在Unix下，人们会选择gzip格式，其中xxx.txt.gz解压缩为xxx.txt。这将可以通过GZipInputStream读取。它具有整体速度与服务器目录之间的文件传输速度的优点。

司徒兴思

2023-03-14

为什么这快这么多？

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

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

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

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

如果方法很简单，它们就会内联。

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

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

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

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

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

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

有什么我没有想到的可以产生重大影响吗？

如果数据在磁盘缓存中，它将比其他任何事情都大不相同。

公良修竹

2023-03-14

您的主要瓶颈将是文件 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();
}

您可能希望在测试速度之前调整此技术，因为它使用称为 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();
}

对文本文件中的整数求和的最快方法

共有3个答案

相关问答

相关文章

相关阅读

相关工具

相关文档