Ленивые Последовательности Clojure, которые являются Векторами
Я заметил, что ленивые последовательности в Clojure, кажется, представлены внутренне как связанные списки (Или по крайней мере их рассматривают как последовательность только с последовательным доступом к элементам). Даже кэшируясь в память, время доступа по ленивому-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: Разработка ленивого вектора: проблема с константой
1 ответ
Да, последовательности в Clojure описываются как "логические списки" с тремя операциями (first, next и cons).
Последовательность - это, по сути, Clojure-версия итератора (хотя clojure.org настаивает на том, что последовательности не являются итераторами, поскольку они не хранят итеративное состояние), и могут перемещаться по коллекции подкреплений только линейно от начала к концу.
Ленивых векторов не существует, по крайней мере, в Clojure.
Если вам нужно постоянное время поиска по диапазону индексов, без вычисления промежуточных элементов, которые вам не нужны, вы можете использовать функцию, которая вычисляет результат на лету. В сочетании с мемоизацией (или самостоятельным кэшированием результатов в хэше arg-to-result) вы получите практически тот же эффект, который, как я предполагаю, вы хотите получить от ленивого вектора.
Очевидно, это работает только тогда, когда существуют алгоритмы, которые могут вычислить f(n) более непосредственно, чем перебор всех предшествующих f(0)...f(n-1). Если такого алгоритма нет, когда результат для каждого элемента зависит от результата для каждого предыдущего элемента, вы в любом случае не сможете сделать лучше, чем итератор последовательности.
Edit
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]
Здесь мы используем ленивую последовательность, чтобы отложить вызовы функций до тех пор, пока их не попросят (iterate возвращает ленивую последовательность), но результаты собираются и возвращаются в векторе.
Вектор растет по мере необходимости, мы добавляем только элементы до последнего запрашиваемого, а после вычисления поиск выполняется за постоянное время.
Вы имели в виду что-то подобное?