Chèn nhanh vào đầu và cuối của seq clojure?

Question

Trong danh sách clojure phát triển từ bên trái và vectơ phát triển từ bên phải, như vậy:

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

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

phương pháp hiệu quả nhất để chèn giá trị cả vào mặt trước và mặt sau của một chuỗi là gì?

Answer 1

Bạn cần cấu trúc dữ liệu khác để hỗ trợ chèn nhanh ở cả đầu và cuối. Xem https://github.com/clojure/data.finger-tree

Answer 2

Như tôi đã hiểu, một chuỗi chỉ là cấu trúc dữ liệu chung nên nó phụ thuộc vào việc triển khai cụ thể mà bạn đang làm việc.

Đối với cấu trúc dữ liệu hỗ trợ truy cập ngẫu nhiên (ví dụ: vectơ), phải mất thời gian không đổi, O (1). Đối với một danh sách, tôi mong đợi chèn ở phía trước của danh sách với một hoạt động cons để có thời gian không đổi, nhưng chèn vào mặt sau của danh sách sẽ lấy O (n) vì bạn phải đi qua toàn bộ cấu trúc để đi đến cùng.

Có, tất nhiên, rất nhiều cấu trúc dữ liệu khác về mặt lý thuyết có thể là một chuỗi (ví dụ: cây) sẽ có các đặc tính O (n) của riêng chúng.