FQ की Seq.sort क्यों LINQ के IENumerable <T> की तुलना में बहुत धीमी है। ऑर्डर द्वारा विस्तार विधि?

Question

मैंने हाल ही में फ़ाइल से कुछ डेटा पढ़ने के लिए कोड का एक टुकड़ा लिखा है, इसे एक टुपल में स्टोर करें और सभी एकत्रित डेटा को टुपल के पहले तत्व से सॉर्ट करें। कुछ परीक्षणों के बाद मैंने देखा है कि Seq.sortBy (और Array.sortBy) का उपयोग करके IENumerable.OrderBy का उपयोग करने से बहुत धीमा है। नीचे जो व्यवहार के बारे में मैं बात कर रहा हूँ दिखाना चाहिए कोड के दो स्निपेट हैं:

(filename 
|> File.ReadAllLines 
|> Array.Parallel.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries) 
           |> Array.map(double) 
           |> Array.sort in arr.[0], arr.[1]) 
).OrderBy(new Func(fun (a,b) -> a)) 

और

filename 
|> File.ReadAllLines 
|> Array.Parallel.map(fun ln -> let arr = ln.Split([|' '|], StringSplitOptions.RemoveEmptyEntries) |> Array.map(double) |> Array.sort in arr.[0], arr.[1]) 
|> Seq.sortBy(fun (a,_) -> a) 

100000 दो युगल से बना लाइनों वाली फ़ाइल पर, मेरे कंप्यूटर बाद के संस्करण पर पहले के रूप में दो गुना अधिक लेता है (Array.sortBy का उपयोग करते हुए कोई सुधार प्राप्त नहीं होता है)। विचार?

Answer 1

एफ # कार्यान्वयन परिणामी कुंजी की संरचनात्मक तुलना का उपयोग करता है।

let sortBy keyf seq = 
    let comparer = ComparisonIdentity.Structural 
    mkDelayedSeq (fun() -> 
     (seq 
     |> to_list 
     |> List.sortWith (fun x y -> comparer.Compare(keyf x,keyf y)) 
     |> to_array) :> seq<_>) 

(भी तरह)

let sort seq = 
    mkDelayedSeq (fun() -> 
     (seq 
     |> to_list 
     |> List.sortWith Operators.compare 
     |> to_array) :> seq<_>) 

दोनों Operators.compare और ComparisonIdentity.Structural.Compare बन (अंततः)

let inline GenericComparisonFast<'T> (x:'T) (y:'T) : int = 
    GenericComparisonIntrinsic x y 
     // lots of other types elided 
     when 'T : float = if (# "clt" x y : bool #) 
          then (-1) 
          else (# "cgt" x y : int #) 

लेकिन ऑपरेटर के लिए यह करने के लिए मार्ग पूरी तरह से है इनलाइन, इस प्रकार जेआईटी कंपाइलर किसी भी अतिरिक्त विधि आमंत्रण ओवरहेड के साथ प्रत्यक्ष डबल तुलना निर्देश डालने को समाप्त कर देगा (इसके अलावा दोनों मामलों में आवश्यक) को छोड़कर व्यवसाय।

सॉर्टबी एक तुलनाकर्ता का उपयोग करता है, इसलिए अतिरिक्त वर्चुअल विधि कॉल के माध्यम से जाएगा, लेकिन मूल रूप से इसके बारे में है।

तुलनात्मक रूप से ऑर्डरबी फ़ंक्शन को समानता के लिए वर्चुअल विधि कॉल (EqualityComparer<T>.Default का उपयोग करके) के माध्यम से जाना चाहिए, लेकिन महत्वपूर्ण अंतर यह है कि यह जगह में है और परिणामस्वरूप इसके लिए बनाए गए बफर का उपयोग करता है। तुलनात्मक रूप से यदि आप इस प्रकार एक नज़र डालेंगे तो आप देखेंगे कि यह सूची टाइप करता है (जगह में नहीं, यह StableSortImplementation का उपयोग करता है जो विलय सॉर्ट प्रतीत होता है) और उसके बाद एक नई सरणी के रूप में इसकी एक प्रति बनाता है। यह अतिरिक्त प्रतिलिपि (आपके इनपुट डेटा के आकार को देखते हुए) धीमी गति का सिद्धांत कारण है, हालांकि अलग-अलग प्रकार के कार्यान्वयन का प्रभाव भी हो सकता है।

यह कहा गया कि यह अनुमान है। यदि यह क्षेत्र प्रदर्शन शर्तों में आपके लिए चिंता का विषय है तो समय निकालने के लिए आपको प्रोफ़ाइल प्रोफ़ाइल चाहिए।

आप को देखने के लिए क्या प्रभाव छंटाई/नकल परिवर्तन इस वैकल्पिक होता चाहते हैं:

// these are taken from the f# source so as to be consistent 
// beware doing this, the compiler may know about such methods 
open System.Collections.Generic 
let mkSeq f = 
    { new IEnumerable<'b> with 
     member x.GetEnumerator() = f() 
     interface System.Collections.IEnumerable with 
     member x.GetEnumerator() = (f() :> System.Collections.IEnumerator) } 

let mkDelayedSeq (f: unit -> IEnumerable<'T>) = 
    mkSeq (fun() -> f().GetEnumerator()) 

// the function 
let sortByFaster keyf seq = 
    let comparer = ComparisonIdentity.Structural 
    mkDelayedSeq (fun() -> 
     let buffer = Seq.to_array seq 
     Array.sortInPlaceBy (fun x y -> comparer.Compare(keyf x,keyf y)) buffer 
     buffer :> seq<_>) 

मैं बहुत बड़ी (> मिलियन) इनपुट दृश्यों लेकिन ऐसा कुछ नहीं के साथ repl के भीतर कुछ उचित प्रतिशत speedups मिल महत्ता का क्रम। आपका लाभ, हमेशा के रूप में, भिन्न हो सकता है।

Answer 2

एक्स (एन.एल.एल. (एन)) के प्रकार x2 का एक अंतर अधिक नहीं है।

डेटा संरचनाओं में छोटे अंतर (उदाहरण के लिए ICollection<T> इनपुट के लिए अनुकूलन) इस पैमाने का अंतर बना सकता है।

और एफ # वर्तमान में बीटा, प्लस एफ # कार्यों (आंशिक आवेदन आदि समर्थन) की व्यापकता (नहीं अनुकूलन बनाम भाषा और सही पुस्तकालयों हो रही पर इतना फोकस) एक मामूली हो सकती गति बुला में धीमा है: अलग के लिए खाते के लिए पर्याप्त से अधिक।