Hiệu quả của việc thêm vào vectơ

Question

Việc thêm phần tử lên một triệu phần tử ArrayList có chi phí đặt một tham chiếu ngay bây giờ và sao chép một tham chiếu trong tương lai khi số ArrayList phải được thay đổi kích thước.

Như tôi đã hiểu, việc thêm một phần tử lên một triệu phần tử PersistenVector phải tạo một đường dẫn mới, bao gồm 4 mảng kích thước 32. Điều này có nghĩa là cần phải chạm đến hơn 120 tham chiếu.

Clojure quản lý để giữ cho chi phí véc tơ "tồi tệ hơn gấp 2,5 lần" hoặc "4 lần tệ hơn" (trái ngược với "tồi tệ hơn 60 lần"), đã được xác nhận trong một số video Clojure mà tôi đã xem gần đây? Có một cái gì đó để làm với bộ nhớ đệm hoặc địa phương của tài liệu tham khảo hoặc một cái gì đó tôi không nhận thức được?

Hoặc là bằng cách nào đó có thể xây dựng một vector nội bộ với đột biến và sau đó biến nó bất biến trước khi tiết lộ nó với thế giới bên ngoài?

Tôi đã gắn thẻ câu hỏi scala là tốt, vì scala.collection.immutable.vector về cơ bản là giống nhau, phải không?

Answer 1

PersistentVector của Clojure có bộ đệm đuôi đặc biệt để cho phép hoạt động hiệu quả ở cuối vectơ. Chỉ sau khi mảng 32 phần tử này được lấp đầy thì nó được thêm vào phần còn lại của cây. Điều này giúp cho chi phí khấu hao thấp. Here là một bài viết về việc triển khai. Các source cũng đáng đọc.

Về ", bằng cách nào đó có thể xây dựng một vector nội bộ với đột biến và sau đó biến nó bất biến trước khi tiết lộ nó với thế giới bên ngoài?", Vâng! Chúng được gọi là transients trong Clojure và được sử dụng để thay đổi hàng loạt hiệu quả.

Answer 2

Không thể nói về Clojure, nhưng tôi có thể đưa ra một số nhận xét về Scala Vectors.

vectơ Scala liên tục (scala.collection.immutable.Vector s) là nhiều hơn chậm hơn so với bộ đệm mảng khi nói đến phụ thêm. Trên thực tế, chúng chậm hơn 10 lần so với hoạt động chuẩn bị trước List. Chúng chậm hơn gấp 2 lần so với Conc-tree, chúng ta sử dụng trong Parallel Collections.

Nhưng, Scala cũng có mutable vectơ - chúng ẩn trong lớp VectorBuilder. Việc thêm vào các vectơ có thể thay đổi không bảo tồn được phiên bản trước của vectơ, nhưng biến đổi nó thành vị trí bằng cách giữ con trỏ tới lá tận cùng bên phải trong vectơ. Vì vậy, có - giữ vectơ có thể thay đổi nội bộ, và hơn là trả lại một tham chiếu bất biến là chính xác những gì được thực hiện trong bộ sưu tập Scala.

VectorBuilder là hơi nhanh hơn ArrayBuffer, bởi vì nó chỉ cần phân bổ mảng của nó một lần, trong khi ArrayBuffer cần phải làm trung bình hai lần (vì ngày càng tăng). Conc.Buffer s, mà chúng tôi sử dụng làm bộ kết hợp mảng song song, nhanh gấp hai lần so với VectorBuilder s.

Điểm chuẩn có tại đây. Không ai trong số các tiêu chuẩn liên quan đến bất kỳ quyền anh, họ làm việc với các đối tượng tham khảo để tránh bất kỳ sai lệch:

• comparison of Scala List, Vector and Conc
• comparison of Scala ArrayBuffer, VectorBuilder and Conc.Buffer

Nhiều bộ sưu tập benchmarks here.

Các thử nghiệm này được thực hiện bằng cách sử dụng ScalaMeter.