multithreading - Clojure - 有效地同时增加列表中的数字

Question

简短版本:在 Clojure 中存储数百个数字的列表的正确方法是什么，其中每个数字都被递增数百万次(可能跨多个线程)？

长版:程序从一个空向量开始，其中每个值都初始化为 0:

[0 0 0 0 0 0 0 0 0 ...]

然后它逐行读取数百万行文件。在对一行执行一些任意计算之后，程序会增加向量中的一些值。在第一行之后，向量可能如下所示:

[1 1 1 2 0 1 0 1 1 ...]

第二行之后:

[2 2 3 2 2 1 0 2 2 ...]

大约 5000 行之后，它可能看起来像:

[5000 4998 5008 5002 4225 5098 5002 5043 ...]

由于 Clojure 的数据结构是不可变的，只需使用 assoc在向量中增加一个值似乎非常浪费，因为每次增量都会复制整个向量。

在不花费所有 CPU 时间复制不可变数据结构的情况下进行这种并发数据聚合的正确方法是什么？我是否应该有一个向量，其中每个元素都类似于 ref 或 atom，所有线程都增加这些共享值？或者，是否有某种线程级的数据结构可以存储计数，然后最后一步是合并来自每个线程的计数？

这可能不会是单个线程上的 I/O 绑定(bind)，所以我猜我会将行处理拆分为多个线程。向量的长度没有限制(它可能有几千个元素长)，但它很可能是大约 100 个元素长。

Answer 1

Clojure 的 vector是持久化的数据结构。更新向量中的元素时，它不会复制整个元素，并且需要基本恒定的时间，这意味着 O(log32 n)。

但似乎您每次迭代都会更新向量中的几乎每个元素。或许你想引用 Transient Data Structures .