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,所以我猜我会在几个线程之间拆分线处理.矢量的长度没有限制(长度可能是几千个元素),但很可能长约100个元素.

Answer 1

Clojure vector是持久的数据结构.更新向量中的元素时,它不会复制整个元素,并且基本上需要时间,这意味着O(log ₃₂ n).

但似乎每次迭代都会更新向量中的几乎每个元素.也许您想要引用瞬态数据结构.