Список или вектор быстрее для доступа к двум самым последним записям (в Clojure)?

Question

Это своего рода продолжение для этого вопроса.

Допустим, нам нужен доступ к двум самым последним вставленным элементам в коллекции.Список или вектор будут быстрее для этой операции?

Это самые быстрые варианты?

; for list
(def l '(3 2 1))
(peek l)
=> 3
(peek (pop l))
=> 2

; for vector
(def v [1 2 3])
(peek v)
=> 3
(peek (pop v))
=> 2

Или это будет быстрее сделать что-то вроде:

(v (- (count v) 1))
=> 3
(v (- (count v) 2))
=> 2

Я был бы очень признателен за объяснение того, как правильно проанализировать эту ситуацию.Это для моей первой игры и программы Clojure, поэтому я беспокоюсь о производительности.:) Причина, по которой я не объединяю эти два значения, состоит в том, чтобы не распаковывать / отображать их, так как вся коллекция также используется.

Спасибо!

Answer 1

Если бы мне пришлось использовать либо список, либо вектор, я бы использовал вектор, потому что subvec очень быстрый.

(let [a (vec (take 100000 (range)))]
    (time (subvec a (- (count a) 2))))
"Elapsed time: 0.045805 msecs"
=> [99998 99999]

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

Answer 2

Вектор Clojure использует оптимизацию хвоста вне дерева, что в основном означает, что пока он не заполнится, последний узел в структуре располагается в заголовке объекта, а не помещается в дерево. Таким образом, вы должны увидеть постоянное время поиска для n % 32 элементов с наибольшим индексом в дереве n элементов.

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