列表或向量访问两个最新条目(在 Clojure 中)的速度是否更快

Question

这是这个问题的后续问题。

假设我们需要访问集合中最近插入的两个元素。对于该操作，列表或向量会更快吗？

这些是最快的选择吗？

; for list
(def l '(3 2 1))
(peek l)
=> 3
(peek (pop l))
=> 2
; for vector
(def v [1 2 3])
(peek v)
=> 3
(peek (pop v))
=> 2

或者做这样的事情会更快：

(v (- (count v) 1))
=> 3
(v (- (count v) 2))
=> 2

我将非常感谢如何正确分析这种情况的解释。这是我的第一个游戏和Clojure程序，这就是为什么我担心性能。:)我不将这两个值打包在一起的原因是为了避免解包/映射它们，因为整个集合也有用处。

谢谢！

Answer 1

如果我必须使用列表或向量，我会使用 vector，因为它非常快subvec。

(let [a (vec (take 100000 (range)))]
    (time (subvec a (- (count a) 2))))
"Elapsed time: 0.045805 msecs"
=> [99998 99999]

但目前尚不清楚你想做什么。也许您的情况有更好的数据结构。

Answer 2

Clojure 的向量使用树外尾部优化，这基本上意味着在它填满之前，结构中的最新节点位于对象标头中，而不是放在树中。 因此，您应该看到n元素树中n % 32索引最高的元素的恒定时间查找。

对于最严格的列表，到达第二个元素总是涉及通过元素 1(两个步骤(的链，但是如果您执行的任何操作对 seq 进行隐式调用，则会引入缓存并且变得不太清楚。