Clojure rseq в постоянное время?

Question

Я читал в «Практическом замыкании» (глава 5), что операция функции rseq выполняется за постоянное время.Мне кажется, что это должна быть линейная операция по времени.Кто-нибудь может пролить свет на это для меня?

Answer 1

Попробуйте:

(class [1 2 3 4])

Вы увидите:

clojure.lang.PersistentVector

Теперь попробуйте это:

(class (rseq [1 2 3 4]))

И реализация последовательности отличается:

clojure.lang.APersistentVector$RSeq

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

Вы можете увидеть класс RSeq, чтобы увидеть, как он реализован здесь: https://github.com/clojure/clojure/blob/b578c69d7480f621841ebcafdfa98e33fcb765f6/src/jvm/clojure/lang/APersistentVector.java

Answer 2

Я не знаю, как это реализовано, но я думаю, что он просто возвращает некоторый объект, который реализует интерфейс последовательности и знает, как пройти структуру (вектор или отсортированную карту) в обратном порядке. Последовательность результатов ленива, поэтому ей не нужно сразу пересекать всю структуру.

Answer 3

Возвращает новый интерфейс за постоянное время, как сказал Горан Йович, но распечатка происходит линейно. Таким образом, отображение в REPL является линейным, но задание в def является постоянным.