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




performance algorithm (4)

_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://stackoverflow.com/questions/7111525/fastest-way-to-sort-integer-arrays-in-javascript एक गलत उत्तर अप-वोट किया गया था और सवाल बंद कर दिया गया था।
  • मैंने कई ब्राउज़र विंडो उदाहरणों को अस्थिर बहु-थ्रेडिंग के रूप में उपयोग करने का प्रयास किया है; यह बाहर नहीं था। मुझे समेकन के लिए कई खिड़कियों के बारे में उपयोगी जानकारी में दिलचस्पी होगी।

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

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






sorting