Подтвердить что ты не робот

Clojure Ленивые последовательности, являющиеся векторами

Я заметил, что ленивые последовательности в 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: Проектирование ленивого вектора: проблема с константой

Ответ 1

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

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

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

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

Это, очевидно, работает только тогда, когда существуют алгоритмы, которые могут вычислять f (n) более непосредственно, чем через все предыдущие f (0)... f (n-1). Если такого алгоритма нет, когда результат для каждого элемента зависит от результата для каждого предыдущего элемента, вы не сможете сделать лучше, чем итератор последовательности в любом случае.

Edit

BTW, если все, что вам нужно, - это результат, чтобы вектор был таким, чтобы впоследствии получать быстрый поиск, и вы не возражаете, что элементы создаются последовательно в первый раз, что достаточно просто.

Вот реализация Fibonacci с использованием вектора:

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

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

Это что-то вроде этого вы имели в виду?