12

私は、Clojure の遅延シーケンスが内部的にリンクされたリストとして表されているように見えることに気付きました (または、少なくとも要素への順次アクセスのみを持つシーケンスとして扱われています)。メモリにキャッシュされた後でも、lazy-seq のアクセス時間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 スニペットのみを示しました: Designing a lazy vector: problem with const

4

1 に答える 1

20

はい、Clojure のシーケンスは、3 つの操作 (first、next、および cons) を持つ「論理リスト」として記述されます。

シーケンスは本質的にイテレーターの Clojure バージョンであり (ただし、clojure.org は、シーケンスは反復状態を保持しないため、イテレーターではないと主張しています)、バッキング コレクション内を線形のフロント ツー エンド方式でのみ移動できます。

遅延ベクトルは、少なくとも Clojure には存在しません。

必要のない中間要素を計算せずに、インデックスの範囲で一定時間のルックアップが必要な場合は、その場で結果を計算する関数を使用できます。メモ化 (または結果を arg-to-result ハッシュに独自にキャッシュすること) と組み合わせることで、遅延ベクトルから求められると想定するのとほぼ同じ効果が得られます。

これは明らかに、先行するすべての 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-21T10:40:57.003 に答える