Cấu trúc dữ liệu đằng sau bộ của Clojure là gì?

Question

Gần đây tôi đã nghe Rich Hickey's interview on Software Engineering Radio. Trong cuộc phỏng vấn Rich đã đề cập rằng các bộ sưu tập của Clojure được thực hiện như cây cối. Tôi hy vọng sẽ triển khai các cấu trúc dữ liệu liên tục trong một ngôn ngữ khác và muốn hiểu cách các tập hợp và các cấu trúc dữ liệu liên tục của Clojure được thực hiện.

Cây trông giống như thế nào ở mỗi điểm trong kịch bản sau đây?

1. Tạo tập {1 2 3}

2. Tạo sự kết hợp của {1 2 3} và {4}

3. Tạo sự khác biệt của {1 2 3 4} và {1}

Tôi muốn hiểu như thế nào ba bộ được tạo ({1 2 3}, {1 2 3 4} và {2 3 4}) cấu trúc chia sẻ và cách "xóa" được xử lý.

Tôi cũng muốn biết số lượng chi nhánh tối đa mà nút có thể có. Giàu đề cập trong cuộc phỏng vấn rằng cây cối nông cạn, vì vậy có lẽ hệ số phân nhánh lớn hơn hai.

Answer 1

Có thể bạn cần đọc công việc của Phil Bagwell. Nghiên cứu của ông về cấu trúc dữ liệu là cơ sở của Clojure, Haskell và các cấu trúc dữ liệu liên tục của Scala.

có những lời nói này bởi Phil tại Clojure/conj: http://www.youtube.com/watch?v=K2NYwP90bNs

Ngoài ra còn có một số giấy tờ:

• Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays
• Ideal Hash Trees
• More from Phil here

Bạn cũng có thể đọc Purely Functional Data Structures bởi Chris Okasaki.Bài đăng trên blog này nói về cuốn sách: http://okasaki.blogspot.com.br/2008/02/ten-years-of-purely-functional-data.html

Answer 2

Dưới đây là một điểm khởi đầu: https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/PersistentHashSet.java

Bạn có thể thấy nó được thực hiện trong điều kiện của PersistentHashMap.

Answer 3

Bạn thực sự nên đọc Clojure Programming, nó bao gồm chi tiết này, bao gồm cả hình ảnh. Tóm lại, các bộ sưu tập là các tìm kiếm đầu tiên về chiều sâu thông qua các cây. Chúng tôi có thể hiển thị các ví dụ của bạn như sau:

(def x #{1 2 3}) 

x 
| 
| \ 
|\ 3 
1 \ 
    2 

(def y (conj x 4)) 

x y 
|/\ 
| \ 4 
|\ 3 
1 \ 
    2 

(def z (difference y #{1})) 

x y 
|/\ 
| \ 4 
|\ 3 
1/\ 
z- 2 

Lưu ý rằng đây chỉ là dấu hiệu, tôi không nói rằng đây chính xác là bố cục Clojure sử dụng nội bộ. Đó là ý chính.

Answer 4

Tôi thích bản vẽ và giải thích của SCdF, nhưng nếu bạn đang tìm kiếm chiều sâu hơn, bạn nên đọc loạt bài viết tuyệt vời về cấu trúc dữ liệu của Clojure tại Higher-Order. Nó giải thích chi tiết các bản đồ của Clojure hoạt động như thế nào, và các bộ của Clojure chỉ là một lớp mỏng trên bản đồ của nó: #{:a :b} được thực hiện như một gói xung quanh {:a :a, :b :b}.