クロージャーの開始点と終了点に迅速に挿入しますか？そう、Clojureのリストで

Question

は左から成長し、ベクトルは右から成長：

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）特性を持つシーケンス（例えば木）であることができる他の多くのデータ構造があることは言うまでもない。