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

姜弘化

2023-03-14

问题内容：

假设您有一个较大的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，它仍然很容易放入long，因此我们不必担心溢出。

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

方法2：轻微调整

受到对此问题的评论的启发，我尝试不创建新代码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秒 。

方法3：手动解析整数

到目前为止，困扰我的一件事是我们将String变成了int，然后将其添加到最后。进行添加可能不是更快吗？如果我们分析String自己会怎样？像这样

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：用二进制处理

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

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

如果我们分配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倍的速度增长 较前最好。

后续问题

为什么这么快？ 我原以为它会赢，但并不是那么令人印象深刻。主要是转换为的间接费用String吗？以及所有有关字符集等的幕后担忧？
通过使用a MappedByteBuffer可以帮助我们做得更好吗？我有一种感觉，调用从缓冲区读取方法的开销会减慢速度，特别是从缓冲区向后读取时。
向前读取文件而不是向后读取文件，但仍然向后扫描缓冲区会更好吗？这样的想法是，您先读取文件的第一个块，然后向后扫描，但最后丢弃一半的数字。然后，当您读取下一个块时，请设置偏移量，以便从丢弃的数字的开头开始读取。
有什么我没想到的事情可以带来重大改变吗？

更新：更令人惊讶的结果

首先，观察。这本来应该在我之前发生过，但是我认为String基于-
读取效率低下的原因不是创建所有String对象所花费的时间，而是它们寿命很短的事实：我们有1亿个对象它们供垃圾收集器处理。那势必会使其不安。

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

我在欺骗缓冲区的大小吗？

一个建议是，由于a
BufferedReader使用了16KB的默认缓冲区，而我使用了8MB的缓冲区，因此我没有进行like之类的比较。如果使用更大的缓冲区，势必会更快。

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

一点实验表明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，并使用位移位进行索引，但这没有帮助。）

看起来正向扫描就在这里。

使用MappedByteBuffer

接下来要添加的是a MappedByteBuffer，以了解这是否比使用raw更有效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;
    }
}

现在关键是：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;
    }

}

请注意，这是对a
byte[]而不是对整体进行操作MappedByteBuffer。这样做的原因是我们要保持磁盘访问顺序。我们将占用很大的块，进行fork /
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;
}

现在，这是令人震惊的失望：这个漂亮的多线程代码现在需要 32.2秒 。为何这么慢？假设我做错了什么，我花了很长时间调试它。

事实证明，只需要进行一个小调整。我认为小问题和大问题之间的阈值64是合理的。原来那完全是荒谬的。

这样想吧。子问题的大小完全相同，因此它们应该在几乎相同的时间内完成。因此，将可用的处理器拆分成更多的片段实际上是没有意义的。在我使用的只有两个内核的机器上，降至64的阈值是荒谬的：这只会增加更多的开销。

现在，您不想限制事物，即使有更多可用空间，它也仅使用两个内核。也许正确的做法是在运行时找出处理器的数量，然后分成许多部分。

无论如何，如果我将阈值更改为512KB（缓冲区大小的一半），它现在将在 13.3秒内
完成。减小到128KB或64KB将允许使用更多的内核（分别最多8个或16个），并且不会显着影响运行时间。

因此，多线程确实有很大的不同。

这是一段漫长的旅程，但是我们开始时花费了92.9秒，现在我们已经减少到13.3秒……这是原始代码速度的七倍
。但这并不是通过提高渐近时间（big-Oh）的时间复杂度来实现的，而这种复杂度从一开始就是线性的（最佳）……这都与提高常数因子有关。

辛苦了

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

后记：生成随机数文件

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

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

问题答案：

我认为还有另一种方法。

这是经典的多进程编程问题。在C语言中，有库MPI可以解决此类问题。

它的想法是将整数列表分块，例如分为4部分，每部分通过不同的过程求和。完成后，将过程汇总在一起。

在Java中，这可以通过线程（伪并行）和Java并发来完成。

例如，4个不同的线程合计了列表的4个不同部分。最后将它们加在一起。

电话公司使用执行这种并行编程技术的网格计算机来汇总其事务。

唯一的问题（瓶颈）是IO操作。读取文件将花费很多时间。如果可以使多个线程读取文件的不同
部分……这是一种非常复杂的方法，我认为这样做不会有什么好处，因为磁盘不会因为仅被多个线程使用而旋转得更快。做类似事情的其他技术。