Clojure懒惰序列是向量

Question

我已经注意到，Clojure中的懒惰序列似乎在内部表示为链接列表（或者至少将它们视为仅对元素的顺序访问）。即使被缓存到内存之后，也可以通过 nth 是o（n），而不是与向量那样恒定时间。

;; ...created my-lazy-seq here and used the first 50,000 items

(time (nth my-lazy-seq 10000))
"Elapsed time: 1.081325 msecs"

(time (nth my-lazy-seq 20000))
"Elapsed time: 2.554563 msecs"

如何在Clojure中获得恒定的时间查找或创建懒惰的矢量？

想象一下，在懒惰向量的生成过程中，每个元素都是以前所有元素的函数，因此遍历列表所花费的时间成为一个重要因素。

相关问题只会出现此不完整的Java片段：设计一个懒惰的向量：const的问题

Answer 1

是的，Clojure中的序列被描述为 “逻辑列表” 具有三个操作（首先，下一个和缺点）。

序列本质上是迭代器的Clojure版本（尽管Clojure.org坚持认为序列不是迭代器，因为它们不持有ITERNAL状态），并且只能以线性的前到端方式在衬托集合中移动。

懒惰的向量不存在，至少不存在。

如果您希望在一系列索引上进行恒定的时间查找，而无需计算不需要的中间元素，则可以使用可以即时计算结果的函数。结合回忆（或单独使用ard-ressult哈希的结果缓存），您的效果与我想从懒惰矢量中想要的效果几乎相同。

显然，只有在有算法可以直接计算f（n）的算法比遍历所有先前的f（0）... f（n-1）时。如果没有这样的算法，则当每个元素的结果取决于每个以前元素的结果时，在任何情况下，您都不能比序列迭代器更好。

编辑

顺便说一句，如果您想要的只是结果是矢量，这样就可以快速查找，并且您不介意第一次是第一次创建元素，那就足够简单了。

这是使用向量的斐波那契实现：

(defn vector-fib [v]
  (let [a (v (- (count v) 2)) ; next-to-last element
        b (peek v)]   ; last element
    (conj v (+ a b))))

(def fib (iterate vector-fib [1 1]))

(first (drop 10 fib))
  => [1 1 2 3 5 8 13 21 34 55 89 144]

在这里，我们使用懒惰的序列推迟函数调用，直到要求（iterate 返回一个懒惰的序列），但结果被收集并返回到向量中。

向量会根据需要增长，我们仅将元素添加到最后一个要求的元素，一旦计算出来，它是一个持续的时间查找。

您想到的是这样吗？