迭代最快的标准ocaml数据结构是什么?

您不太可能比内置数组和列表做得更好,因为它们是用C编写的,除非您绑定到自己的迭代器本机实现。数组的行为几乎与c中的数组(包含一系列元素值的连续分配内存块)完全相同,可能由于装箱而有一些额外的指针间接指向。list正是按照您的预期实现的:作为带有值和“next”指针的单元格。数组将为未绑定类型(特别是 float 有一个超级特殊的未绑定实现)。

有关数组和列表实现的信息,请参见 Section 18.3 of the OCaml manual 以及档案 byterun/mlvalues.h , byterun/array.c 和 byterun/alloc.c 在ocaml源代码中。

发问者 事实上, Array 似乎是最快的解决方案。不过,它只会跑赢 List 到7%点。可能是因为数组元素的类型不够简单:它是代数类型。 Hashtbl 表现比预期差4倍。

所以,我会选择 数组 我接受这个。很好。

要确定,你必须测量 . 根据编译器可能生成的机器指令,我会尝试一个数组,然后是一个列表。

• 访问数组元素需要边界检查、地址算术和加载

• 访问列表头需要加载、空列表测试和已知编译时偏移量的加载。

具体的速度可能取决于您的应用程序和您的计算机上正在发生的其他事情。它们还取决于元素的类型;例如,如果它们是浮点数, ocamlopt 可能很聪明,可以创建一个未绑定的数组,这样可以节省一定程度的间接寻址。

其他常见的数据结构(如哈希表或平衡树)通常要求您在某个地方分配一些上下文以跟踪您的位置。对于数组,保持跟踪只需要一个整数索引;对于列表,保持跟踪需要一个指针。我认为这在另一个数据结构中是很难克服的。

最后请注意,可能只有一个ocaml编译器,但它有 二 后端:字节码和本机代码。当然,如果您关心这个性能级别,您将使用本机代码 奥克洛普特 版本。对吗?

请测量并将结果编辑到您的问题中。

别忘了 Bigarray 它们最接近C数组(只是一块平面内存),但不能包含任意的OCAML值。还可以考虑关闭边界检查(不安全的设置/获取)。当然你应该先做个侧写。

数组-一个按顺序访问的项目的线性内存块-最好使用CPU的一级数据缓存。

所有常见的数据结构在o(n)时间内都是可iterable的,因此数据结构之间的差异将只是常数(而且很可能不显著)。

至少列表和数组允许迭代,而不需要很大的开销。我想不出那种情况会不够快。