作为矢量的Clojure惰性序列

我注意到Clojure中的惰性序列似乎在内部被表示为链表（或者至少它们被当作只有顺序访问元素的序列）。即使在被缓存到内存之后，使用nth的lazy-seq访问时间是O（n），而不是像向量一样的常量时间。作为矢量的Clojure惰性序列

;; ...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

来源

2010-06-21 ivar

是，Clojure中的序列有三个操作（第一，下一个和缺点）描述为"logical lists"。

一个序列本质上是一个迭代器的Clojure版本（虽然clojure.org坚持认为序列不是迭代器，因为它们不持有本地状态），并且只能通过线性前端的后备集合来移动 - 时尚。

懒惰的载体不存在，至少在Clojure中不存在。

如果您希望在一系列索引上进行恒定时间查找，而无需计算不需要的中间元素，则可以使用函数来即时计算结果。结合memoization（或将结果缓存到自己的结果哈希表中），您可以获得与我认为您需要从懒惰向量获得的效果几乎相同的效果。

这显然只适用于有算法可以比直接通过所有前面的f（0）... f（n-1）计算f（n）更多的算法。如果不存在这样的算法，那么当每个元素的结果取决于每个前一个元素的结果时，在任何情况下都不可能比序列迭代器更好。

编辑

顺便说一句，如果你想要的是得到的结果是一个矢量，所以你可以快速查找之后，你不介意元素顺序创建的第一次，这是很简单。

下面是一个使用矢量斐波那契实现：

(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返回一个懒惰的序列），但结果被收集并返回在向量中。

该矢量根据需要增长，我们只添加到最后一个请求的元素，并且一旦计算出它是一个恒定的时间查找。

难道你有这样的想法？

来源

2010-06-21 10:40:57

感谢您的回复！是的，你的斐波纳契范例更类似于我所寻找的东西：惰性创建一个向量。 – ivar 2010-06-22 04:37:40

你也可以在懒惰的'fib'序列上使用'nnth' :)'（nth fib 10）' – NikoNyrh 2017-11-01 13:01:29

作为矢量的Clojure惰性序列

回答

相关问题