मैं सोच रहा हूँ ImmutableSortedSet और देशी FSharp सेट के बीच अंतर क्या?
वे आम तौर पर बहुत समान होते हैं। मुख्य अंतर यह है कि एफ # Set फास्ट सेट सैद्धांतिक संचालन (संघ, चौराहे और अंतर) का समर्थन करता है।
यहाँ एक सरल एफ # प्रोग्राम है जो कुछ सामान्य संचालन के प्रदर्शन का आकलन करता है:
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
मेरी मशीन पर, मैं मिलता है:
BCL ImmutableSortedSet F# Set
add 2.6s 3.0s
contains 2.1s 1.9s
union 1.1s 0.00004s
तो एफ # Set निर्माण करने के लिए थोड़ा धीमे और है खोज करने के लिए थोड़ा तेज़ लेकिन सेट सैद्धांतिक संघ संचालन के लिए तीव्रता के आदेश तेजी से।
fsharp मानचित्र का आंतरिक कार्यान्वयन क्या है? क्या लाल ब्लैक ट्री यहां दावा किया गया है या यहां एवीएल पेड़ जैसा पाया गया है?
आपके दोनों लिंक स्टेटस के रूप में, एफ # एवीएल पेड़ों का उपयोग करता है।
यह वास्तव में उपरोक्त प्रदर्शन आंकड़ों के संदर्भ में प्रासंगिक है। एवीएल पेड़ों में प्रत्येक शाखा में एक उपट्री की अधिकतम ऊंचाई होती है, इसलिए, पूरे उप-परीक्षण की जांच किए बिना सबट्री को पुन: संतुलित करने की अनुमति मिलती है। इसके विपरीत, लाल-काले पेड़ों में प्रत्येक शाखा में एक छोटा सा डेटा होता है, इसलिए पुनर्विक्रय करने वाले उपट्री के लिए पूरे पेड़ों को पार करने की आवश्यकता होती है जो असम्बद्ध रूप से धीमी होती है। आम आदमी के शब्दों में, दो समान आकार के गैर-ओवरलैपिंग सेटों के संघ में दो मौजूदा पेड़ों वाली एक नई शाखा बनाने से थोड़ा अधिक शामिल होता है। ध्यान दें कि बीसीएल एपीआई में Union यह भी व्यक्त नहीं कर सकता है: यह एक ठोस सेट के बजाय एक सार IEnumerable संभालता है।
इसके अतिरिक्त, एमएसडीएन दस्तावेज़ क्यों स्पष्ट नहीं करते हैं कि लाइब्रेरी संग्रह के लिए वास्तविक डेटा संरचना क्या है? मुझे पता है कि ये कार्यान्वयन विवरण हैं और बदलने जा रहे हैं। मेरा मुद्दा यह है कि यदि वे लाइब्रेरी डेटा प्रकार को किसी निश्चित प्रकार की अच्छी तरह से ज्ञात डेटा संरचना में बाध्य नहीं करना चाहते हैं, तो कम से कम जटिलता के संदर्भ में उन्हें कम से कम सभी विधियों के प्रदर्शन हस्ताक्षरों का सारांश देना चाहिए?
मैं मानता हूं कि दस्तावेज़ों में जटिलताएं अच्छी होंगी।
"मुझे कल्पना है कि यही कारण है कि एफ # मानचित्र और सेट कार्यान्वयन के लिए एवीएल पेड़ चुने गए थे।" मैंने सोचा था कि उसी कारण बीसीएल में अपरिवर्तनीय संग्रह पर भी लागू होना चाहिए। – colinfang