В clojure списки растут слева, а векторы растут справа, поэтому:
user> (conj '(1 2 3) 4)
(4 1 2 3)
user> (conj [1 2 3] 4)
[1 2 3 4]
Какой наиболее эффективный способ вставки значений как в переднюю, так и в обратную сторону последовательности?
Быстрая вставка в начало и конец clojure seq?
Ответ 1
Вам нужна другая структура данных для быстрой установки в начале и конце. См. https://github.com/clojure/data.finger-tree
Ответ 2
Как я понимаю, последовательность - это всего лишь общая структура данных, поэтому она зависит от конкретной реализации, с которой вы работаете.
Для структуры данных, которая поддерживает произвольный доступ (например, вектор), она должна занимать постоянное время, O (1).
Для списка я ожидаю, что вставка в начале списка с операцией cons займет постоянное время, но вставка в конец списка займет O (n), поскольку вам нужно пройти всю структуру чтобы добраться до конца.
Существует, конечно, множество других структур данных, которые теоретически могут быть последовательностью (например, деревьями), которые будут иметь свои собственные характеристики O (n).