Clojure trên Fennel Phần một: Cấu trúc dữ liệu bền vững

Đâu đó vào năm 2019, tôi đã bắt đầu một dự án nhằm đưa một số tính năng của Clojure vào thời gian chạy Lua - fennel-cljlib. Đó là một thư viện dành cho Fennel đã triển khai một tập hợp con cơ bản của clojure.core hàm và macro không gian tên. Mục tiêu của tôi rất đơn giản - tôi thích làm việc với Clojure, nhưng tôi không sử dụng nó cho các dự án theo sở thích, vì vậy tôi muốn Fennel có cảm giác giống Clojure hơn, bên cạnh những gì nó đã cung cấp vì điều đó.

Thư viện này phát triển qua nhiều năm, tôi đã triển khai trình tự lười biếng, thêm tính bất biến, tạo thư viện thử nghiệm, lấy cảm hứng từ clojure.test và kaocha, thậm chí còn tạo ra một cổng của clojure.core.async. Đó là một dự án đam mê, tôi gần như chưa bao giờ sử dụng nó để viết phần mềm thực tế. Một ngoại lệ đáng chú ý là fenneldoc - một công cụ tạo tài liệu cho thư viện Fennel. Và tôi chưa thấy ai khác sử dụng nó cho một dự án nghiêm túc.

Lý do rất đơn giản - đó là một thử nghiệm. Các góc đã bị cắt, và Fennel, vốn là một kẻ nói ngọng lấy cảm hứng từ Clojure, không liên quan đến lập trình chức năng giống như cách của Clojure. Trên thực tế, tôi không khuyên bạn nên sử dụng thư viện này cho bất kỳ việc gì nghiêm trọng… chưa.

Tuy nhiên, gần đây, tôi đã bắt đầu một dự án mới: ClojureFnl. Đây là trình biên dịch Clojure-to-Fennel sử dụng fennel-cljlib làm nền tảng. Nó vẫn đang trong những ngày đầu phát triển, nhưng tôi đã làm việc riêng với nó trong vài tháng cho đến khi tìm ra cách phù hợp để mọi thứ hoạt động vào tháng 3. Tính đến thời điểm này, nó có khả năng biên dịch hầu hết các tệp .cljc mà tôi đã ném vào nó, nhưng đang chạy mã được biên dịch là một vấn đề khác. Ý tôi là, nó hoạt động ở một mức độ nào đó, nhưng việc hỗ trợ cho thư viện tiêu chuẩn còn lâu mới hoàn thành.

;; Chào mừng bạn đến với ClojureFnl REPL
;; ClojureFnl v0.0.1
;; Fennel 1.6.1 trên PUC Lua 5,5
user=> (defn prime? [n]
 (không (một số số 0? (bản đồ #(rem n %) (phạm vi 2 n)))))
#<function: 0x89ba7c550>
user=> (cho [x (phạm vi 3 33 2)
 :khi (số nguyên tố? x)]
 x)
(3 5 7 11 13 17 19 23 29 31)
user=>

Tuy nhiên, đã xảy ra sự cố.

Việc triển khai ban đầu của tôi về tính bất biến cấu trúc dữ liệu trong thư viện itable có một lỗ hổng nghiêm trọng. Toàn bộ thư viện là một bản hack đơn giản dựa trên phương pháp sao chép khi ghi và một loạt các siêu dữ liệu Lua để thực thi tính bất biến. Kết quả là mọi hoạt động diễn ra cực kỳ chậm chạp. Nó chỉ là một thử nghiệm thôi, nhưng nếu tôi muốn tiến xa hơn với ClojureFnl, tôi phải thay thế nó. Vấn đề tương tự đã xảy ra với immutableredblacktree.lua, việc triển khai một cây đỏ-đen sao chép khi ghi mà tôi đã tạo cho các bản đồ được sắp xếp. Nó tạo một bản sao đầy đủ của cây mỗi lần sửa đổi.

Đối với các bảng kết hợp, đó không phải là vấn đề lớn - bản đồ thường chứa một lượng nhỏ khóa và itable chỉ sao chép các cấp độ cần thay đổi. Vì vậy, nếu bạn có một bản đồ có mười phím và mỗi phím đó chứa một bản đồ khác có mười phím, việc thêm, xóa hoặc cập nhật một khóa trong bản đồ bên ngoài chỉ có nghĩa là sao chép mười khóa này - không phải toàn bộ bản đồ lồng nhau. Tôi có thể làm điều đó một cách đáng tin cậy vì bản đồ bên trong cũng không thể thay đổi được.

Nhưng đối với mảng thì câu chuyện thường khá khác. Mảng thường lưu trữ rất nhiều chỉ mục và hiếm khi được lồng vào nhau (hoặc ít nhất là không thường xuyên như bản đồ). Và việc sao chép mảng trên mỗi thay đổi nhanh chóng trở nên tốn kém. Tôi đã giảm thiểu một số vấn đề về hiệu suất bằng cách triển khai phiên bản tuy nhiên, điểm hay của cấu trúc dữ liệu của Clojure là chúng khá nhanh ngay cả khi không có sự tối ưu hóa này.

Cấu trúc dữ liệu liên tục phù hợp

Clojure sử dụng HAMT liên tục làm cơ sở cho các tập hợp và bản đồ băm của nó cũng như một bộ ba được phân vùng theo bit cho vectơ. Đối với các bản đồ và bộ được sắp xếp, Clojure sử dụng cách triển khai cây đỏ đen bất biến, nhưng theo tôi biết thì nó không tạo một bản sao đầy đủ của cây, và nó cũng có thuộc tính chia sẻ cấu trúc.

Tôi bắt đầu xem xét các triển khai HAMT hiện có cho Lua:

1. hamt.lua (dựa trên mattbierner/hamt)
   • dường như chưa hoàn thiện
2. ltrie
   • không có chuyển tiếp
   • không tập băm
   • không có bản đồ theo thứ tự (có thể dự kiến, thuật toán khác)
   • không có vectơ ghép/băm
3. Ý chính của Michael-Keith Bernard
   • không có hàm băm tùy chỉnh

Tôi có thể sử dụng một trong những thứ đó, đặc biệt là ltrie có vẻ là thứ phù hợp nhất nhưng vì tôi đang làm việc trên một thư viện thì là mà sau này tôi muốn nhúng vào trình biên dịch Clojure của mình. Tôi cần một thư viện được triển khai trong Fennel.

Vì vậy, tôi đã tạo thư viện của riêng mình: immutable.fnl. Thư viện này có các bản đồ, bộ hàm băm và vectơ HAMT, cũng như triển khai tốt hơn cây đỏ đen liên tục và danh sách liên kết lười.

Bản đồ băm liên tục

Tôi đã bắt đầu triển khai với một HAMT liên tục với hàm băm Lua gốc. Bản thân cấu trúc dữ liệu là Hash Array Mapped Trie (HAMT) với phân nhánh 16 yếu tố. Do đó, tất cả các thao tác đều là O(Log16 N), thực tế là O(1) đối với số lượng khóa thực tế.

Theo những gì tôi biết, Clojure sử dụng hệ số phân nhánh là 32, nhưng đối với thời gian chạy Lua, điều này có nghĩa là số lượng quần thể sẽ đắt hơn và mặc dù có cây nông hơn, mỗi đột biến sẽ cần sao chép một mảng thưa thớt lớn hơn. Với hệ số phân nhánh là 16, bản đồ có 50K mục nhập có độ sâu ~ 4 cấp, sẽ là ~ 3 với hệ số phân nhánh 32. Vì vậy, logic của tôi là nó sẽ là một sự thỏa hiệp, đặc biệt vì Lua không phải là JVM khi nói đến hiệu suất.

Tất nhiên, nó không nhanh bằng bảng Lua thuần túy như mong đợi. Các bảng Lua được triển khai bằng C, sử dụng hàm băm hiệu quả và được phân bổ lại động dựa trên số lượng khóa. Vì vậy đối với Việc triển khai của tôi hầu hết các thao tác đều chậm hơn rất nhiều nhưng tổng thời gian cho một thao tác vẫn có thể sử dụng được.

Dưới đây là một số điểm chuẩn:

Thời gian trung bình trong 7 hiệp (loại bỏ 1 lần khởi động), N = 50000 phần tử. GC dừng lại trong quá trình đo. Đồng hồ: os.clock (CPU). Thời gian chạy: Fennel 1.7.0-dev trên PUC Lua 5.5

Các hoạt động thông thường chậm hơn đáng kể so với Lua:

Đối với các trạng thái tạm thời, tình hình sẽ tốt hơn một chút nhưng không nhiều:

Các số trên LuaJIT có vẻ tệ hơn nhưng chi phí cho mỗi thao tác thấp hơn nhiều, chỉ là các thao tác trên bảng gốc nhanh hơn rất nhiều:

Thời gian trung bình trên 7 hiệp (loại bỏ 1 lần khởi động), N = 50000 phần tử. GC dừng lại trong quá trình đo. Đồng hồ: os.clock (CPU). Thời gian chạy: Fennel 1.7.0-dev trên LuaJIT 2.1.1774896198 macOS/arm64

Với hệ số phân nhánh là 32, tình hình trở nên tồi tệ hơn trên PUC Lua nhưng lại tốt hơn một chút trên LuaJIT. Vì vậy, vẫn còn chỗ để tinh chỉnh.

Để băm chuỗi và đối tượng, tôi quyết định sử dụng thuật toán djb2. Tôi gần bằng tuổi hàm băm này nên có vẻ như rất phù hợp. JK. Lý do chính để sử dụng nó là nó có thể được thực hiện ngay cả khi chúng tôi không có bất kỳ toán tử bit-wise nào và Lua không có chúng trong tất cả các phiên bản. Nó chỉ sử dụng các toán tử số học +, * và % nên có thể thực hiện được trên mọi phiên bản Lua. Nó dễ xảy ra xung đột và tôi cố gắng giảm thiểu điều đó bằng cách ngẫu nhiên hóa nó khi thư viện được tải.

Tuy nhiên, xung đột vẫn xảy ra nhưng lõi HAMT đảm bảo rằng chúng vẫn sẽ giải quyết chính xác bằng cách triển khai chức năng bình đẳng sâu cho hầu hết các đối tượng.

Tuy nhiên, khi lần đầu tiên làm việc này, tôi nhận thấy điều này:

>> (cục bộ bản đồ băm (yêu cầu :io.gitlab.andreyorst.immutable.PersistentHashMap))
nil
>> (địa phương {: băm} (yêu cầu :io.gitlab.andreyorst.immutable.impl.hash))
nil
>> (hash (hash-map :foo 1 :bar 2))
161272824
>> (băm {:foo 1 :bar 2})
161272824
>> (hash-map (hash-map :foo 1 :bar 2) 1 {:foo 1 :bar 2} 2)
{{:foo 1 :bar 2} 2}

Đây là một lỗ hổng thú vị. Đối tượng nào cuối cùng xuất hiện trong bản đồ băm của chúng ta dưới dạng khóa - bản đồ cố định hay bảng Lua đơn giản? Chà, điều đó phụ thuộc vào thứ tự chèn:

>> (mỗi [_ k (cặp (hash-map (hash-map :foo 1 :bar 2) 1 {:foo 1 :bar 2} 2))]
 (print (getmetatable k)))
IPersistentHashMap: 0x824d9b570
nil
>> (mỗi [_ k (cặp (hash-map {:foo 1 :bar 2} 2 (bản đồ băm :foo 1 :bar 2) 1))]
 (print (getmetatable k)))
nil
nil

Để nhắc lại, tôi tạo một bản đồ băm, với một khóa được đặt thành một bản đồ băm liên tục khác, sau đó chèn một bảng Lua đơn giản có cùng nội dung. Bảng Lua băm chính xác theo cùng một hàm băm và đi vào cùng một nhóm nhưng không có xung đột vì các đối tượng bằng nhau về giá trị. Nhưng sự bình đẳng của các bộ sưu tập có thể thay đổi được xác định rất lỏng lẻo - nó có thể bằng nhau ngay bây giờ, nhưng lần sau bạn nhìn vào nó, nó sẽ khác. Vì vậy, một phép băm khác là cần thiết cho các bộ sưu tập liên tục, để tránh những loại xung đột này. Tôi đã kết thúc việc thêm muối vào các bộ sưu tập liên tục bằng địa chỉ nguyên mẫu của chúng trong bộ nhớ.

Ngoài ra, việc triển khai HAMT được thực hiện theo sách và phần còn lại là giao diện để tương tác với bản đồ.

Hoạt động chính:

• mới - tạo bản đồ mới về giá trị khóa cặp
• assoc - liên kết khóa với một giá trị
• dissoc - xóa khóa khỏi bản đồ
• conj - phương pháp liên kết phổ biến, giống như trong Clojure
• chứa - kiểm tra xem khóa có trong bản đồ hay không
• count - kích thước bản đồ, không đổi thời gian
• nhận - nhận giá trị khóa từ bản đồ
• phím - tải xuống danh sách các khóa
• vals - lấy danh sách giá trị từng phần
• tạm thời - chuyển đổi bản đồ thành tạm thời

Cưỡng chế/chuyển đổi:

• từ - tạo bản đồ từ một đối tượng khác
• to-table - chuyển đổi bản đồ thành bảng Lua
• iterator - lấy một iterator để sử dụng trong vòng lặp Lua

Hoạt động nhất thời:

• assoc! - có thể thay đổi assoc
• dissoc! - có thể thay đổi dissoc
• persistent - chuyển đổi về biến thể cố định và đánh dấu tạm thời là đã hoàn thành

Điều này đáp ứng hầu hết các nhu cầu trong thư viện fennel-cljlib của tôi, vì bất cứ điều gì ngoài nó tôi có thể tự triển khai hoặc chỉ điều chỉnh các triển khai hiện có.

Bộ băm liên tục cũng có sẵn dưới dạng một lớp bao bọc mỏng xung quanh PersistentHashMap với một vài thay đổi về phương thức.

Ghi chú về PersistentArrayMap.

Trong Clojure có một loại bản đồ thứ hai được sắp xếp theo thứ tự, không được sắp xếp, được gọi là Bản đồ mảng liên tục. Chúng được sử dụng theo mặc định khi xác định bản đồ có 8 phím trở xuống, như {:foo 1 :bar 2. Ý tưởng rất đơn giản - đối với một bản đồ nhỏ như vậy, tìm kiếm tuyến tính thông qua tất cả các phím nhanh hơn so với bản đồ dựa trên HAMT.

Tuy nhiên, trong thử nghiệm của tôi về thời gian chạy Lua, loại cấu trúc dữ liệu này không có lợi ích gì, ngoài việc nó là một biến thể có thứ tự. Việc tra cứu chậm hơn do hàm bình đẳng tùy chỉnh thực hiện so sánh sâu.

Vectơ liên tục

Vectơ liên tục xuất hiện tiếp theo và mặc dù cấu trúc trie tương tự như hàm băm bản đồ, vectơ sử dụng điều hướng trực tiếp dựa trên chỉ mục thay vì băm, với hệ số phân nhánh là 32. Không giống như bản đồ, mảng vectơ trong HAMT được đóng gói dày đặc hơn và do đó hệ số phân nhánh cao hơn sẽ mang lại hiệu suất tốt hơn. Vì vậy, tra cứu, cập nhật và bật lên là O(log32 N), phần bổ sung có thể được coi là O(1) được khấu hao.

Tuy nhiên, so với các bảng tuần tự Lua đơn giản thì hiệu suất vẫn chưa bằng tốt:

Thời gian trung bình trong 7 hiệp (loại bỏ 1 lần khởi động), N = 50000 phần tử. GC dừng lại trong quá trình đo. Đồng hồ: os.clock (CPU). Thời gian chạy: Fennel 1.7.0-dev trên PUC Lua 5.5

Trên LuaJIT:

Thời gian trung bình trên 7 hiệp (loại bỏ 1 lần khởi động), N = 50000 phần tử. GC dừng lại trong quá trình đo. Đồng hồ: os.clock (CPU). Thời gian chạy: Fennel 1.7.0-dev trên LuaJIT 2.1.1774896198 macOS/arm64

Tôi nghĩ đây vẫn là một màn trình diễn ổn. Các vectơ không sử dụng hàm băm, thay vào đó, nó truyền tải chỉ mục trực tiếp thông qua dịch chuyển bit, do đó không có hàm băm, chỉ có phép toán chỉ mục.

Các phép toán trên vectơ bao gồm:

• mới - hàm tạo
• conj - nối vào đuôi
• assoc - thay đổi giá trị tại chỉ mục đã cho
• count - số phần tử (thời gian không đổi)
• nhận - nhận giá trị tại chỉ mục đã cho
• pop - xóa cuối cùng
• tạm thời - chuyển đổi thành tạm thời
• subvec - tạo một lát vectơ trong thời gian không đổi

Hoạt động nhất thời:

• assoc! - có thể thay đổi assoc
• conj! - có thể thay đổi conj
• pop! - có thể thay đổi pop
• persistent - chuyển đổi về dạng Persistent và hoàn thiện

Tương tác:

• from - tạo một vectơ từ bất kỳ bộ sưu tập nào khác
• iterator - trả về một trình vòng lặp để sử dụng trong vòng lặp Lua
• to-table - chuyển đổi thành bảng Lua tuần tự

Một điểm khác biệt đáng chú ý trong cả vectơ và bản đồ băm là nó cho phép sử dụng nil làm giá trị (và làm khóa, trong trường hợp bản đồ băm). Các vectơ không gặp vấn đề tương tự như các bảng tuần tự Lua, trong đó độ dài không được xác định rõ nếu bảng có lỗ hổng trong nó.

Sẽ còn tranh luận vào lúc khác, liệu việc cho phép nil làm giá trị (và đặc biệt là khóa) có phải là một quyết định đúng đắn hay không, nhưng Clojure đã đưa ra quyết định đó cho tôi. Vì vậy, tôi quyết định hỗ trợ dự án này.

Cây có màu đỏ đen bền bỉ

Đối với các bản đồ và tập hợp đã sắp xếp, tôi đã chọn thuật toán chèn của Okasaki và thuật toán xóa của Germane & Might. Hầu hết các kiến thức tôi thu được từ bài đăng trên blog tuyệt vời này của Matt Might.

Tôi tin rằng các phép toán là O(Log N), giống như bất kỳ cây nhị phân nào, nhưng do thuật toán xóa phức tạp nên tôi không chắc chắn lắm:

Thời gian trung bình trong 7 hiệp (loại bỏ 1 lần khởi động), N = 50000 phần tử. GC dừng lại trong quá trình đo. Đồng hồ: os.clock (CPU). Thời gian chạy: Fennel 1.7.0-dev trên PUC Lua 5.5

Trên LuaJIT:

Thời gian trung bình trong 7 hiệp (loại bỏ 1 lần khởi động), N = 50000 phần tử. GC dừng lại trong quá trình đo. Đồng hồ: os.clock (CPU). Thời gian chạy: Fennel 1.7.0-dev trên LuaJIT 2.1.1774896198 macOS/arm64

API dành cho các bộ và bản đồ được sắp xếp giống như các bản sao băm của chúng với một sự khác biệt nhỏ - không có sự chuyển tiếp. Clojure không làm những việc đó và tôi cũng không làm.

Đó là tất cả về điểm chuẩn. Tôi biết rằng có nhiều vấn đề với loại điểm chuẩn này, vì vậy hãy xem xét nó một cách cẩn thận. muối. Tuy nhiên, kết quả vẫn tốt hơn rất nhiều so với những gì tôi có với itable.

Nhưng còn hai cấu trúc dữ liệu nữa cần nói đến.

Danh sách cố định

Như tôi đã đề cập, trước đây tôi đã thực hiện lười biếng triển khai danh sách liên tục nhưng nó có vấn đề và tôi không thể tích hợp đủ tốt thư viện đó với thư viện hiện tại.

Vấn đề chính là thư viện này sử dụng một siêu dữ liệu được chia sẻ duy nhất cho mỗi cấu trúc dữ liệu và cách triển khai danh sách lười cũ thì không. Sự khác biệt này khiến cho việc kiểm tra xem đối tượng có phải là bảng, bản đồ băm, danh sách, vectơ, tập hợp, v.v. trở nên khó khăn hay không. Vì vậy tôi đã triển khai lại chúng.

Lý do khiến cách triển khai cũ sử dụng các siêu dữ liệu khác nhau là do tôi đã quyết định thử phương pháp được mô tả trong Đảo ngược cuộc phỏng vấn kỹ thuật bài đăng của Kyle Kingsbury (Aphyr). Tôi biết bài đăng này giống một trò đùa vui hơn nhưng thực sự rất hợp lý khi xác định các danh sách liên kết như thế trong Lua.

Thấy chưa, bảng có thể thay đổi và bạn không thể làm gì nhiều với điều đó. Mặt khác, việc đóng cửa khó thay đổi hơn nhiều - bạn vẫn có thể thực hiện việc đó thông qua mô-đun debug, nhưng việc này khó và không phải lúc nào cũng có. Vì vậy, việc lưu trữ đầu và tail trong việc đóng hàm là một lựa chọn có chủ ý.

Tuy nhiên, điều đó có nghĩa là tôi cần phải đính kèm siêu dữ liệu vào hàm bằng cách nào đó để làm cho nó hoạt động giống như một cấu trúc dữ liệu và bạn không thể chỉ sử dụng setmetatable trên một hàm. Một lần nữa, bạn có thể thực hiện debug.setmetatable nhưng tất cả các đối tượng hàm đều có chung một bảng siêu dữ liệu. Vì vậy, trong khi bạn có thể làm những việc ưa thích như cái này:

>> (fn comp [f g] (fn [...] (f (g ...))))
#<chức năng: 0x7bdb320a0>
>> (debug.setmetatable (fn []) {:__add comp})
#<chức năng: 0x7bd17f040>
>> ((+ string.reverse string.upper) "foo")
"OOF"

Bạn cũng có thể nhận thấy rằng tình trạng quá tải + của chúng tôi đã áp dụng cho các hàm trong mô-đun chuỗi.

Vì vậy, thay vào đó, chúng tôi sử dụng một bảng và gói nó bằng một siêu dữ liệu có siêu phương thức __call, về cơ bản là tạo ra bảng hoạt động như một hàm. Ngược lại, điều này có nghĩa là chúng ta phải tạo hai bảng cho mỗi nút danh sách - một bảng để cung cấp cho người dùng, bảng còn lại để đặt __cuộc gọi và sử dụng nó làm bảng meta.

Tôi biết, rất phức tạp. Tất cả đã là quá khứ - cách triển khai hiện tại chỉ là một bảng {:head 42 :tail {...} đơn giản. Không chắc điều gì tệ hơn.

Nhưng điều đó có nghĩa là tôi phải làm lại cách danh sách lười biếng đã hoạt động vì trước đây nó chỉ là một sự hoán đổi có thể thay đổi được. Bây giờ, danh sách lưu trữ một "thunk", khi được gọi sẽ thay thế chính nó trong nút bằng các phím :head và :tail. Tất nhiên, trừ khi đó là một danh sách trống - trong trường hợp đó, chúng tôi hoán đổi siêu dữ liệu thành một danh sách trống.

Vậy Danh sách có ba siêu dữ liệu bây giờ:

• IPersistentList
• IPersistentList$Empty
• IPersistentList$Lazy

Thay vì có Chúa mới biết có bao nhiêu trong cách triển khai cũ.

Giao diện danh sách giờ đây cũng tốt hơn. Trước đây người ta đã mã hóa cứng cách xây dựng danh sách từ dữ liệu kết cấu. Việc triển khai hiện tại cũng mã hóa cứng danh sách đó nhưng cũng cho phép tạo danh sách một cách lười biếng từ trình vòng lặp.

Điều này tốt hơn vì giờ đây cấu trúc dữ liệu tùy chỉnh có lược đồ lặp kỳ lạ (như bản đồ và tập hợp trong thư viện này), chúng tôi vẫn có thể chuyển đổi cấu trúc đó thành danh sách. Trường hợp chung chỉ là:

(PersistentList.from-iterator #(cặp dữ liệu) (fn [_ v] v))

Có nghĩa là chúng ta truyền một hàm sẽ tạo ra trình vòng lặp và một hàm để thu thập các giá trị từ trình vòng lặp đó. Theo một cách nào đó, tôi nhớ đến bộ chuyển đổi clojure.

Liên tục Hàng đợi

Và cấu trúc dữ liệu cuối cùng - hàng đợi liên tục. Nối nhanh vào cuối và cũng xóa nhanh ở phía trước.

Việc này được thực hiện bằng cách giữ hai bộ sưu tập - một danh sách được liên kết ở phía trước và một vectơ cố định ở phía sau. Vì vậy, loại bỏ khỏi danh sách là O(1) và việc thêm vào vectơ cũng khá nhiều O(1).

Những điều thú vị bắt đầu xảy ra khi chúng tôi sử dụng hết phần danh sách - chúng ta cần di chuyển nội dung của vector vào danh sách. Việc này được thực hiện bằng cách gọi PersistentList.from ở phía sau. Và việc xây dựng một danh sách từ một vectơ ổn định cũng là một thao tác O(1)! Chà, vì không có gì xảy ra nên chúng ta chỉ cần tạo một trình vòng lặp và xây dựng danh sách một cách lười biếng. Nhưng vì việc lập chỉ mục cho vectơ về cơ bản là ~O(1), nên chúng tôi có thể nói rằng chúng tôi vẫn giữ lại thuộc tính này.

Hoặc ít nhất đó là cách tôi đã lý luận về điều này - Tôi không giỏi về những vấn đề phức tạp về thời gian.

ClojureFnl

Điều đó kết thúc phần một về ClojureFnl.

Tôi biết rằng bài đăng này hoàn toàn không phải về ClojureFnl nhưng trước tiên tôi phải sửa cách triển khai cơ bản của mình. Bây giờ, tôi có cấu trúc dữ liệu tốt hơn để xây dựng, tôi có thể quay lại làm việc với chính trình biên dịch. Vì vậy, bài viết tiếp theo hy vọng sẽ nói về chính trình biên dịch.

Trừ khi tôi lại bị phân tâm.