javascript - जावास्क्रिप्ट में 32 बिट हस्ताक्षरित पूर्णांक सरणी को सॉर्ट करने का सबसे तेज़ तरीका?



performance algorithm optimization sorting (5)

_radixSort_0 = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
            0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0];
/*
RADIX SORT
Use 256 bins
Use shadow array
- Get counts
- Transform counts to pointers
- Sort from LSB - MSB
*/
function radixSort(intArr) {
    var cpy = new Int32Array(intArr.length);
    var c4 = [].concat(_radixSort_0); 
    var c3 = [].concat(_radixSort_0); 
    var c2 = [].concat(_radixSort_0);
    var c1 = [].concat(_radixSort_0); 
    var o4 = 0; var t4;
    var o3 = 0; var t3;
    var o2 = 0; var t2;
    var o1 = 0; var t1;
    var x;
    for(x=0; x<intArr.length; x++) {
        t4 = intArr[x] & 0xFF;
        t3 = (intArr[x] >> 8) & 0xFF;
        t2 = (intArr[x] >> 16) & 0xFF;
        t1 = (intArr[x] >> 24) & 0xFF ^ 0x80;
        c4[t4]++;
        c3[t3]++;
        c2[t2]++;
        c1[t1]++;
    }
    for (x=0; x<256; x++) {
        t4 = o4 + c4[x];
        t3 = o3 + c3[x];
        t2 = o2 + c2[x];
        t1 = o1 + c1[x];
        c4[x] = o4;
        c3[x] = o3;
        c2[x] = o2;
        c1[x] = o1;
        o4 = t4;
        o3 = t3;
        o2 = t2;
        o1 = t1;
    }
    for(x=0; x<intArr.length; x++) {
        t4 = intArr[x] & 0xFF;
        cpy[c4[t4]] = intArr[x];
        c4[t4]++;
    }
    for(x=0; x<intArr.length; x++) {
        t3 = (cpy[x] >> 8) & 0xFF;
        intArr[c3[t3]] = cpy[x];
        c3[t3]++;
    }
    for(x=0; x<intArr.length; x++) {
        t2 = (intArr[x] >> 16) & 0xFF;
        cpy[c2[t2]] = intArr[x];
        c2[t2]++;
    }
    for(x=0; x<intArr.length; x++) {
        t1 = (cpy[x] >> 24) & 0xFF ^ 0x80;
        intArr[c1[t1]] = cpy[x];
        c1[t1]++;
    }
    return intArr;
}

संपादित करें:

अब तक, सबसे अच्छा / केवल प्रमुख अनुकूलन प्रकाश में लाया गया है जेएस टाइप किए गए सरणी है। सामान्य रेडिक्स सॉर्ट की छाया सरणी के लिए टाइप किए गए सरणी का उपयोग करके सर्वोत्तम परिणाम प्राप्त हुए हैं। मैं स्टैक पुश / पॉप में निर्मित जेएस का उपयोग कर जगह में त्वरित जगह से थोड़ा अतिरिक्त निचोड़ने में भी सक्षम था।

नवीनतम jsfiddle बेंचमार्क

Intel i7 870, 4GB, FireFox 8.0
2mil
radixSort(intArr): 172 ms
radixSortIP(intArr): 1738 ms
quickSortIP(arr): 661 ms
200k
radixSort(intArr): 18 ms
radixSortIP(intArr): 26 ms
quickSortIP(arr): 58 ms

ऐसा लगता है कि इस वर्ड-फ्लो के लिए मानक रेडिक्स सॉर्ट वास्तव में राजा है। अगर किसी के पास लूप-अनोलिंग या इसके लिए अन्य संशोधनों के साथ प्रयोग करने का समय है तो मैं इसकी सराहना करता हूं।

मेरे पास एक विशिष्ट उपयोग केस है जहां मैं जावास्क्रिप्ट में सबसे तेज़ संभव सॉर्टिंग कार्यान्वयन चाहता हूं। बड़ी (50,000 - 2 मिली), अपरिवर्तित (अनिवार्य रूप से यादृच्छिक), पूर्णांक (32 बिट हस्ताक्षरित) सरणी होगी जो क्लाइंट स्क्रिप्ट तक पहुंच जाएगी, फिर उसे इस डेटा को क्रमबद्ध और प्रस्तुत करने की आवश्यकता है।

मैंने जगह रेडिक्स सॉर्ट में काफी तेजी से कार्यान्वित किया है और जगह में त्वरित प्रकार jsfiddle बेंचमार्क है लेकिन मेरे ऊपरी बाउंड सरणी लंबाई के लिए वे अभी भी काफी धीमी हैं। त्वरित क्रम मेरे ऊपरी बाउंड सरणी आकार पर बेहतर प्रदर्शन करता है जबकि रेडिक्स सॉर्ट मेरे निचले बाउंड पर बेहतर प्रदर्शन करता है।

defaultSort is the built-in JavaScript array.sort with an integer compare function

Intel C2Q 9650, 4GB, FireFox 3.6
2mil
radixSortIP(intArr): 5554 ms
quickSortIP(arr): 1796 ms
200k
radixSortIP(intArr): 139 ms
quickSortIP(arr): 190 ms
defaultSort(intArr): 354 ms

Intel i7 870, 4GB, FireFox 8.0
2mil
radixSortIP(intArr): 990 ms
quickSortIP(arr): 882 ms
defaultSort(intArr): 3632 ms
200k
radixSortIP(intArr): 28 ms
quickSortIP(arr): 68 ms
defaultSort(intArr): 306 ms

प्रशन

  • क्या किसी भी सॉर्टिंग एल्गोरिदम का बेहतर कार्यान्वयन है जो मेरे उपयोग के मामले / आवश्यकताओं को पूरा करेगा?
  • क्या प्रदर्शन में सुधार के लिए मेरे अनुकूल स्थान रेडिक्स / त्वरित सॉर्ट कार्यान्वयन के लिए कोई अनुकूलन किया जा सकता है?
    • क्या मेरे स्थान को रेडिक्स सॉर्ट को पुनरावर्तक से पुनरावृत्त करने के लिए एक प्रभावी तरीका है? मेमोरी और निष्पादन की गति।

लक्ष्य

  • मुझे आशा है कि ये उत्तर मुझे मेरे बेंचमार्क परीक्षण में ~ 20-30% प्रदर्शन सुधार प्राप्त करने में मदद करेंगे।

स्पष्टीकरण / नोट्स

  • "डेफिन फास्ट" मैं एक सामान्य मामला पसंद करूंगा जहां यह सभी आधुनिक ब्राउज़रों पर अच्छा प्रदर्शन करता है, लेकिन यदि ब्राउज़र विशिष्ट अनुकूलन है जो एक महत्वपूर्ण सुधार करता है जो स्वीकार्य हो सकता है।
  • सॉर्टिंग को सर्वर की तरफ किया जा सकता है, लेकिन मैं इससे बचना पसंद करूंगा क्योंकि जेएस ऐप एक स्टैंडअलोन बन सकता है (शेल्फ प्रोप्रायटरी ऐप से कुछ के साथ जोड़ा गया है जो फाइल को सेंसर डेटा स्ट्रीम करेगा)।
  • जावास्क्रिप्ट इसके लिए सबसे अच्छी भाषा नहीं हो सकता है लेकिन यह एक आवश्यकता है।
  • मैंने पहले से ही इस सवाल से पूछा है https://.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript एक गलत उत्तर अप-वोट किया गया था और सवाल बंद कर दिया गया था।
  • मैंने कई ब्राउज़र विंडो उदाहरणों को अस्थिर बहु-थ्रेडिंग के रूप में उपयोग करने का प्रयास किया है; यह बाहर नहीं था। मुझे समेकन के लिए कई खिड़कियों के बारे में उपयोगी जानकारी में दिलचस्पी होगी।

Answers

मैंने टाइप किए गए सरणी का परीक्षण किया है, क्यूएसआईपी संस्करण आधुनिक ब्राउज़रों में अच्छा प्रतीत होता है:

2 000 000 तत्व

          QSIP_TYPED | RDXIP_TYPED |  QSIP_STD | RDXIP_STD
----------------------------------------------------------
Chrome  |    300          1000          600        1300
Firefox |    550          1500          800        1600    

http://jsfiddle.net/u8t2a/35/

समर्थन ( स्रोत: http://caniuse.com/typedarrays ):

 IE 10+   |   FF 4+  |  Chrome 7+  |  Safari 5.1+  |  Opera 11.6+   

क्या आपने कैश उपयोग को अधिकतम करने के लिए एल्गोरिदम का संयोजन माना है? मैंने बेंचमार्क में देखा कि जब आप छोटे हो जाते हैं तो आप सम्मिलन प्रकार पर स्विच कर रहे हैं। एक दिलचस्प दृष्टिकोण है कि इसके बजाय हेपसोर्ट पर स्विच करें। Quicksort के साथ संयोजन के रूप में प्रयोग किया जाता है, यह O (n ^ 2) के बजाय सबसे खराब मामला ओ (nlog (n)) को नीचे ला सकता है। Introsort पर एक नज़र Introsort


मैंने आपके बेंचमार्क के साथ झुकाया और अपना खुद का सॉर्ट फ़ंक्शन जोड़ा। यह रेडिक्सॉर्ट के समान ही करता है, लेकिन इसका विचार (और कार्यान्वयन) सरल है, यह रेडिक्सॉर्ट की तरह है, लेकिन बाइनरी में, इसलिए आपके पास केवल दो बाल्टी हैं और यह जगह में कर सकती है। http://jsfiddle.net/KaRV9/7/

मैंने अपना कोड "जगह में क्विक्सोर्ट" के स्थान पर रखा है (क्योंकि यह क्विकॉर्ट के समान ही है, केवल पिवट को अन्य तरीके से चुना जाता है)। उन्हें अपने क्रोम 15 में कुछ बार चलाएं, वे इतने करीब प्रदर्शन करते हैं कि यह उन्हें अलग करने में असमर्थ है।


संपादित करें: मुझे लगता है कि आप पहले से ही छोटे subarrays के लिए सम्मिलन प्रकार का उपयोग कर रहे हैं। मैंने यह खो दिया।

क्विकसॉर्ट के साथ अच्छा असली दुनिया दृष्टिकोण सबएरे के आकार की जांच करना है, और यदि यह पर्याप्त कम ओवरहेड सॉर्ट का उपयोग करता है जो बड़े सरणी के लिए बहुत धीमा है, जैसे सम्मिलन प्रकार।

छद्म कोड कुछ के साथ कुछ है:

quicksort(array, start, end):
  if ( (end-start) < THRESHOLD ) {
    insertion_sort(array, start, end);
    return;
  }
  // regular quicksort here
  // ...

THRESHOLD निर्धारित करने के लिए, आपको अपने प्लेटफ़ॉर्म पर अपने समय के बारे में समय-समय पर अलग-अलग ब्राउज़रों की आवश्यकता होती है। एक करीबी से इष्टतम खोजने के लिए अलग-अलग थ्रेसहोल्ड के साथ यादृच्छिक सरणी के लिए समय का आकलन करें। यदि आप महत्वपूर्ण अंतर पाते हैं तो आप विभिन्न ब्राउज़रों के लिए अलग-अलग थ्रेसहोल्ड भी चुन सकते हैं।

अब यदि आपके इनपुट वास्तव में यादृच्छिक नहीं हैं (जो कि बहुत आम है) तो आप देख सकते हैं कि बेहतर पिवट चयन प्रदर्शन में सुधार करता है या नहीं। एक आम विधि तीन का औसत है


यहां बहुत अच्छे उत्तर दिए गए हैं, लेकिन मैं यह इंगित करना चाहता हूं कि उन्हें बहुत अधिक जटिल सॉर्टिंग प्राप्त करने के लिए बहुत आसानी से बढ़ाया जा सकता है। केवल एक चीज जो आपको करना है वह इस तरह श्रृंखला तुलना कार्यों के लिए OR ऑपरेटर का उपयोग करना है:

objs.sort((a,b)=> fn1(a,b) || fn2(a,b) || fn3(a,b) )

जहां fn1 , fn2 , ... क्रमबद्ध फ़ंक्शन हैं जो [-1,0,1] लौटते हैं। इसके परिणामस्वरूप "एफएन 1 द्वारा सॉर्टिंग", "एफएन 2 द्वारा सॉर्टिंग" जो एसक्यूएल में ऑर्डर के बराबर है।

यह समाधान || के व्यवहार पर आधारित है ऑपरेटर जो पहली मूल्यांकन अभिव्यक्ति का मूल्यांकन करता है जिसे सत्य में परिवर्तित किया जा सकता है

सबसे सरल रूप में इस तरह के केवल एक रेखांकित कार्य है:

// ORDER BY last_nom
objs.sort((a,b)=> a.last_nom.localeCompare(b.last_nom) )

last_nom साथ दो चरणों के साथ, first_nom सॉर्ट ऑर्डर इस तरह दिखेगा:

// ORDER_BY last_nom, first_nom
objs.sort((a,b)=> a.last_nom.localeCompare(b.last_nom) || 
                  a.first_nom.localeCompare(b.first_nom)  )

एक सामान्य तुलना समारोह ऐसा कुछ हो सकता है:

// ORDER BY <n>
let cmp = (a,b,n)=>a[n].localeCompare(b[n])

इस समारोह को संख्यात्मक क्षेत्रों, केस संवेदनशीलता, आर्बिटरी डेटाटाइप इत्यादि का समर्थन करने के लिए बढ़ाया जा सकता है।

आप उन्हें प्राथमिकता के अनुसार उन्हें चेन करने के साथ उपयोग कर सकते हैं:

// ORDER_BY last_nom, first_nom
objs.sort((a,b)=> cmp(a,b, "last_nom") || cmp(a,b, "first_nom") )
// ORDER_BY last_nom, first_nom DESC
objs.sort((a,b)=> cmp(a,b, "last_nom") || -cmp(a,b, "first_nom") )
// ORDER_BY last_nom DESC, first_nom DESC
objs.sort((a,b)=> -cmp(a,b, "last_nom") || -cmp(a,b, "first_nom") )

यहां बिंदु यह है कि कार्यात्मक दृष्टिकोण के साथ शुद्ध जावास्क्रिप्ट आपको बाहरी पुस्तकालयों या जटिल कोड के बिना लंबा रास्ता ले सकता है। यह भी बहुत प्रभावी है, क्योंकि कोई स्ट्रिंग पार्सिंग नहीं की जानी चाहिए





javascript performance algorithm optimization sorting