Clojure Lazy序列是向量

发布时间：2020-12-14 17:44:37 所属栏目：Java 来源：网络整理

导读：我已经注意到,Clojure中的懒惰序列似乎在内部被表示为链表(或至少它们被视为只能顺序访问元素的序列).即使在缓存到内存中之后,第n个的懒惰seq的访问时间是O(n),而不是与向量一样的时间. ;; ...created my-lazy-seq here and used the first 50,000 items(tim

我已经注意到,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]

这里我们使用一个懒惰的序列来推迟函数调用直到被请求(迭代返回一个惰性序列),但是结果被收集并返回到一个向量中.

矢量根据需要增长,我们只添加最后一个要素的元素,一旦计算出它是一个恒定的时间查找.

你是这样想的吗？

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!