基本上我在ocaml程序中使用了list，最初它是这样的
val mutable ll : string list = []
.....
ll <- ll@[(foo ar1 ar2)]
然后在相对较大的数据集(超过50k)上测试时，我的程序运行得太慢了。
我认为这是因为在上面的代码中有一个整个列表复制过程，(每次当ll <- ll@[])
所以我这样修改了代码:
ll <- (foo ar1 ar2)::ll (* extend the head for N times *)
.....
List.rev ll
然而，令我惊讶的是，似乎没有明显的性能改进……
然后我尝试这样的数组:
let arr = Array.make len "" in
arr.(counter) <- (foo ar1 ar2);
counter := !counter + 1
.....
Array.to_list arr
在我的理解中，它应该比第一种方法更好，然而，可能因为我的代码中可能存在其他低性能错误，即使我改变了上面方法中的list操作代码，我仍然不能显式地提高性能。
所以我的问题是，理论上，在以上三种策略中，哪一种表现最好?
我应该可以自己做一些实验，但是作为一个更普遍的问题，在处理相关问题时是否有更好的性能策略?
在列表的末尾添加元素对列表的长度是线性的，并且需要复制整个列表。如果你以这种方式建立一个完整的列表，你会得到二次复杂度。
如果您通过将列表反转到末尾，然后将其添加到前面，然后再次反转，则同样成立。反转列表需要复制列表。
通常的技术是完全以反向顺序构建列表，然后在完成后反转一次。总的来说，这只有线性复杂性。在列表的前面添加操作是一个常量时间操作。
如果你不需要增加数组的大小(这需要数组的副本)，使用数组也有线性复杂性。
在你的代码中可能有其他慢点掩盖了你对这个点的更改。
在我看来，如果你大部分时间没有完成编码，你应该只考虑基本的复杂性(线性，n log n，二次等)。如果您确实需要担心性能问题，您可以稍后对其进行改进。您不希望最终丢掉花费了大量时间进行调整的代码。