我已经注意到,Clojure中的懒惰序列似乎在内部被表示为链表(或至少它们被视为只能顺序访问元素的序列).即使在缓存到内存中之后,第n个的懒惰seq的访问时间是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片段：
Designing a lazy vector: problem with const
解决方法
是的,Clojure中的序列被描述为
“logical lists”,具有三个操作(第一,下一个和缺点).
序列本质上是迭代器的Clojure版本(尽管clojure.org坚持序列不是迭代器,因为它们不具有本身的状态),并且只能以线性前端到端的方式移动通过后台集合.
懒惰的矢量不存在,至少不在Clojure.
如果您希望在一系列索引上进行恒定时间查找,而不需要计算不需要的中间元素,则可以使用即时计算结果的函数.结合记忆(或者将结果缓存在自己的参数结果哈希中),您可以获得与我从懒惰向量中想要的效果几乎相同的效果.
这显然只有当有一些算法可以直接计算f(n),而不是通过所有先前的f(0)… f(n-1)来计算.如果没有这样的算法,当每个元素的结果取决于每个先前元素的结果时,在任何情况下都不能比序列迭代器更好.
编辑
BTW,如果你想要的结果是一个向量,所以你以后快速查找,你不介意元素是第一次顺序创建,这很简单.
这是使用矢量的斐波纳契实现：
(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]
这里我们使用一个懒惰的序列来推迟函数调用直到被请求(迭代返回一个惰性序列),但是结果被收集并返回到一个向量中.
矢量根据需要增长,我们只添加最后一个要素的元素,一旦计算出它是一个恒定的时间查找.
你是这样想的吗？
