Быстрая вставка в начало и конец закрывающей последовательности

Question

В clojure списки растут слева, а векторы растут справа, поэтому:

user> (conj '(1 2 3) 4)
(4 1 2 3)

user> (conj [1 2 3] 4)
[1 2 3 4]

Какой самый эффективный метод вставки значений в начало и конец последовательности?

Answer 1

Вам нужна другая структура данных для поддержки быстрой вставки как в начале, так и в конце.Смотри https://github.com/clojure/data.finger-tree

Answer 2

Насколько я понимаю, последовательность - это просто общая структура данных, поэтому она зависит от конкретной реализации, с которой вы работаете.

Для структуры данных, которая поддерживает произвольный доступ (например, вектор), это должно занять постоянное время, O (1).

Для списка я бы ожидал, что вставка в начало списка с операцией cons займет постоянное время, но вставка в конец списка потребует O (n), так как вы должны пройти всю структуру добраться до конца.

Конечно, существует множество других структур данных, которые теоретически могут быть последовательностями (например, деревьями), которые будут иметь свои собственные характеристики O (n).