我正在寻找一个容器,通过封装元素提供最快的无序迭代.换句话说,"添加一次,多次迭代".
OCaml的标准模块中是否有一个足够快(这样进一步优化它将是无用的)？还是某种第三方GPL准备好的？
AFAIK只有一个OCaml编译器,所以快速的概念或多或少都清晰......
......但在我看到几个答案之后,它似乎并非如此.当然,有大量的数据结构允许O(n)迭代通过大小为n的容器.但我正在解决的任务之一是O(n)和O(2n)之间的差异很重要;-).
我还看到Arrays和Lists提供了有关添加元素顺序的不必要信息,我不需要这些信息.也许在"功能世界"中存在数据结构,这样可以以一点迭代速度交换该信息.
CI会完全选择一个普通阵列.问题是,我应该在OCaml中选择什么？
你不可能比内置数组和列表做得更好,因为它们是用C语言编写的,除非你绑定到你自己的迭代器本机实现.一个数组的行为几乎就像C中的一个数组(一个连续分配的内存块,包含一系列元素值),可能还有一些由于装箱引起的额外指针间接.列表完全按照您的预期实现:作为具有值和"下一个"指针的单元格.数组将为您提供未装箱类型的最佳位置(特别是floats,它具有超级特殊的未装箱实现).
有关数组和列表的执行信息,请参阅OCaml的手册第18.3和文件byterun/mlvalues.h,byterun/array.c以及byterun/alloc.c在OCaml的源代码.
来自提问者:确实,Array似乎是最快的解决方案.然而,它的表现仅超过List7%.也许是因为数组元素的类型不够明确:它是一种代数类型. Hashtbl正如预期的那样,表现差了4倍.
所以,我会选择Array,我接受这个.好.
要确切知道,你将不得不衡量.基于编译器可能生成的机器指令,我会尝试一个数组,然后是一个列表.
访问数组元素需要边界检查,地址算法和加载
访问列表头部需要加载,空列表测试和已知编译时偏移量的加载.
详细信息更快可能取决于您的应用程序以及您的计算机上发生的其他事情.它们还取决于元素的类型; 例如,如果它们是浮点数,ocamlopt可能足够聪明,可以创建一个未装箱的数组,这将为您节省一个间接级别.
其他常见的数据结构(如散列表或平衡树)通常要求您在某处分配一些上下文以跟踪您的位置.对于数组,保持跟踪只需要一个整数索引; 使用列表,保持跟踪需要一个指针.我认为这在其他数据结构中很难被击败.
最后请注意,可能只有一个OCaml编译器,但它有两个后端:字节码和本机代码.当然,如果您关心此级别的性能,则使用的是本机代码ocamlopt版本.对？
请进行测量并将结果编辑到您的问题中.
不要忘记Bigarrays,它们最接近C数组(只是一块平坦的内存),但不能包含任意的OCaml值.还要考虑切换边界检查(unsafe_set/get).当然,你应该首先介绍一下.
京公网安备 11010802040832号 | 京ICP备19059560号-6 