Clojure Lazy Последовательности, которые являются векторами

Question

Я заметил, что ленивые последовательности в 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" 

Как я получаю постоянная время Lookups или создать ленивый вектор приращения в Clojure?

Представьте, что во время генерации ленивого вектора каждый элемент является функцией всех предшествующих ему элементов, поэтому время, затрачиваемое на перемещение списка, становится значительным фактором.

Похожие вопросы только появился этот неполную Java фрагмент кода: Designing a lazy vector: problem with const

Answer 1

Да, последовательности в Clojure описываются как "logical lists" с тремя операциями (первый, следующий и минусы).

Последовательность - это, по существу, версия итератора Clojure (хотя clojure.org настаивает на том, что последовательности не являются итераторами, поскольку они не имеют состояния iternal), и могут перемещаться только через базовую коллекцию в линейном фронте -для моды.

Ленивые векторы не существуют, по крайней мере, не в Clojure.

Если вы хотите получать постоянный поиск по диапазону индексов, не вычисляя промежуточные элементы, которые вам не нужны, вы можете использовать функцию, которая рассчитывает результат на лету. В сочетании с memoization (или кэширование результатов в хеше с аргументом «результат-результат») вы получаете почти такой же эффект, как я предполагаю, что вы хотите от ленивого вектора.

Это, очевидно, работает только тогда, когда существуют алгоритмы, которые могут вычислять 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 возвращает ленивую последовательность), но результаты собраны и возвращены в векторе.

Вектор растет по мере необходимости, мы добавляем только элементы до последнего, который запрашивается, и после его вычисления он постоянно ищет время.

Было ли это таким, что вы имели в виду?