Clojure Lazy Sequence, которые являются векторами - PullRequest
Новая
       6

Clojure Lazy Sequence, которые являются векторами

11 голосов
/ 21 июня 2010

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

19 голосов
/ 21 июня 2010

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

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

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

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

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

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

Это что-то подобное вы имели в виду?

...