tôi tự hỏi sự khác biệt giữa ImmutableSortedSet và mẹ đẻ FSharp Set là gì?
Chúng thường rất giống nhau. Sự khác biệt chính là F # Set hỗ trợ các hoạt động lý thuyết nhanh chóng thiết lập (công đoàn, giao lộ và sự khác biệt).
Đây là một F # chương trình đơn giản để đo lường hiệu quả hoạt động của một số hoạt động chung:
open System.Collections.Immutable
while true do
do
let timer = System.Diagnostics.Stopwatch.StartNew()
let cmp = LanguagePrimitives.FastGenericComparer<int>
let mutable s1 = ImmutableSortedSet.Create<int>(cmp)
let mutable s2 = ImmutableSortedSet.Create<int>(cmp)
for i in 1..1000000 do
s1 <- s1.Add i
for i in 1000000..2000000 do
s2 <- s2.Add i
printfn "BCL ImmutableSortedSet: add in %fs" timer.Elapsed.TotalSeconds
timer.Restart()
for _ in 1..10 do
for i in 1..1000000 do
ignore(s1.Contains i)
printfn "BCL ImmutableSortedSet: contains in %fs" timer.Elapsed.TotalSeconds
timer.Restart()
let s = s1.Union s2
printfn "BCL ImmutableSortedSet: union in %fs" timer.Elapsed.TotalSeconds
do
let timer = System.Diagnostics.Stopwatch.StartNew()
let mutable s1 = Set.empty
let mutable s2 = Set.empty
for i in 1..1000000 do
s1 <- s1.Add i
for i in 1000000..2000000 do
s2 <- s2.Add i
printfn "F# Set: %fs" timer.Elapsed.TotalSeconds
timer.Restart()
for _ in 1..10 do
for i in 1..1000000 do
ignore(s1.Contains i)
printfn "F# Set: contains in %fs" timer.Elapsed.TotalSeconds
timer.Restart()
let s = Set.union s1 s2
printfn "F# Set: union in %fs" timer.Elapsed.TotalSeconds
Trên máy tính của tôi, tôi nhận được:
BCL ImmutableSortedSet F# Set
add 2.6s 3.0s
contains 2.1s 1.9s
union 1.1s 0.00004s
Vì vậy, F # Set là hơi chậm để xây dựng và tìm kiếm nhanh hơn một chút nhưng các đơn đặt hàng có cường độ nhanh hơn cho hoạt động liên kết lý thuyết được đặt.
Triển khai nội bộ bản đồ fsharp là gì? Là Black Black Tree như được yêu cầu ở đây hoặc cây AVL như được tìm thấy ở đây?
Vì cả hai trạng thái liên kết của bạn, F # đều sử dụng cây AVL.
Điều này thực sự có liên quan trong ngữ cảnh của các con số hiệu suất ở trên. Cây AVL chứa chiều cao tối đa của cây con trong mỗi nhánh cây và, do đó, cho phép các subtrees được cân bằng lại mà không kiểm tra toàn bộ cây con. Ngược lại, các cây đỏ-đen chứa một bit dữ liệu duy nhất trong mỗi nhánh nên việc cân bằng lại các subtrees đòi hỏi toàn bộ cây phải di chuyển chậm hơn. Theo các thuật ngữ của giáo dân, sự kết hợp của hai tập hợp không trùng lặp có kích thước tương tự đòi hỏi ít hơn việc tạo ra một nhánh mới chứa hai cây hiện có. Lưu ý rằng Union trong BCL API thậm chí không thể diễn đạt điều này: nó xử lý một trừu tượng IEnumerable thay vì một tập hợp cụ thể.
Ngoài ra, tại sao tài liệu MSDN không nêu rõ cấu trúc dữ liệu thực tế dành cho việc thu thập thư viện là gì? Tôi biết đây là những chi tiết triển khai và sắp thay đổi. Quan điểm của tôi là nếu họ không muốn ràng buộc kiểu dữ liệu thư viện với một kiểu cấu trúc dữ liệu nổi tiếng nào đó, thì ít nhất họ nên cung cấp một bản tóm tắt tất cả các chữ ký hiệu năng của phương thức về mặt phức tạp?
Tôi đồng ý rằng sự phức tạp trong tài liệu sẽ tốt.
"Tôi tưởng tượng đó là lý do tại sao cây AVL được chọn cho F # Bản đồ và Đặt triển khai". Tôi đã nghĩ rằng lý do tương tự cũng nên áp dụng cho Bộ sưu tập bất biến tại BCL. – colinfang