👸🏾 👊🏼 🚧 मर्ज सॉर्ट और AS3। मूल वेक्टर से बाहर निकलकर ।ort (Array.NUMERIC) 👁️ 👨🏻‍🏫 👨🏾‍⚖️

बायाँ - मर्जसॉर्ट, दायाँ - देशी छँटाई। पेपरफ्लैश और 75 मिलियन आइटम।

इस प्रकार को समझने के लिए, आपको तीन सिद्धांतों को समझने की आवश्यकता है:

आपको केवल ऑर्डर किए गए सरणियों को मर्ज करने की आवश्यकता है।
एक तत्व की एक सरणी को आदेशित माना जाता है।
मर्ज का परिणाम एक क्रमबद्ध सरणी है।

मर्ज प्रक्रिया दो इनपुट सरणियों के पहले तत्वों में से सबसे छोटे को काटती है और परिणामी सरणी के अंत में सम्मिलित करती है जब तक कि इनपुट सरणियों में से एक खाली नहीं हो जाती। उसके बाद, एक गैर-खाली सरणी के अवशेषों को परिणामी सरणी के अंत में कॉपी किया जाता है।

एल्गोरिथ्म को अच्छी तरह से समझने के लिए, आपको इसे लागू करने की आवश्यकता है।
यह इस तरह निकला:

function mergeSort(array:Array):Array { var chunkSize:int = array.length / 2; if(chunkSize >= 1){ var left:Array = mergeSort(array.slice(0, chunkSize)); var right:Array = mergeSort(array.slice(chunkSize)); var result:Array = []; while(left.length && right.length){ if(left[0] < right[0]){ result.push(left.shift()); } else{ result.push(right.shift()); } } return result.concat(left, right); } return array; }

वास्तव में, यहां तक कि इस तरह का कार्यान्वयन कुछ से भी तेज है जो मुझे सभी प्रकार के ब्लॉगों में मिला है।

पुनरावर्ती, पहले तत्वों को पहले सॉर्ट किया जाता है। यही है, 0 और 1, फिर 2 और 3, फिर 0..1 और 2..3 एक सरणी 0..3 में विलय, और केवल 4 और 5 के बाद।
(उद्घाटन ब्रैकेट से पहले की संख्या प्राथमिकता है)

  6 {
     _3_ [
         1 (1, 2),
         2 (3, 4)
     ]
     5 [
         _4_ (5, 6)
     ]
 }

लेकिन आप सभी तत्वों को एक तत्व से सॉर्ट कर सकते हैं, और फिर उन्हें 4 तत्वों की उप-श्रेणियों में विलय कर सकते हैं।

  6 {
     _4_ [
         1 (1, 2),
         2 (3, 4)
     ]
     5 [
         _3_ (5, 6)
     ]
 }

इससे पुनरावृत्ति दूर होती है।

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

क्योंकि आकार के मर्ज का परिणाम दो इनपुट सबरेज़ के आकारों का योग है; आप पहले सरणी के पहले तत्व के सूचकांक के साथ शुरू करते हुए बफर को परिणाम लिख सकते हैं। यह आपको केवल एक बफर, मूल सरणी के आकार का चयन करने की अनुमति देगा, और मूल सरणी के लिए हर बार मर्ज के परिणाम की प्रतिलिपि न करने के लिए।

संक्षेप में, एक उल्लू आकर्षित करें:

कोड

 function mergeSort(array:Vector.<int>):Vector.<int> { var length:uint = array.length; var buffer:Vector.<int> = new Vector.<int>(length, true); for (var leftChunkSize:uint = 1; leftChunkSize < length; leftChunkSize *= 2) { // low var bufferPointer:uint = 0; var leftChunkStart:uint = 0; for (; leftChunkStart < length; leftChunkStart += leftChunkSize * 2) { // mid var rightChunkStart:uint = Math.min(leftChunkStart + leftChunkSize, length); var rightChunkEnd:uint = Math.min(rightChunkStart + leftChunkSize, length); var leftChunkEnd:uint = rightChunkStart; var leftPointer:uint = leftChunkStart; var rightPointer:uint = rightChunkStart; while (leftPointer < leftChunkEnd && rightPointer < rightChunkEnd) { // hard if (array[leftPointer] < array[rightPointer]) { buffer[bufferPointer++] = array[leftPointer++]; }else { buffer[bufferPointer++] = array[rightPointer++]; } } while (leftPointer < leftChunkEnd) { // hard buffer[bufferPointer++] = array[leftPointer++]; } while (rightPointer < rightChunkEnd) { // hard buffer[bufferPointer++] = array[rightPointer++]; } } var temp:Vector.<int> = array; array = buffer; buffer = temp; } if (result !== array) { for (var i:uint = 0; i < length; i++ ) { result[i] = array[i]; } } return result; }

टिप्पणियाँ अड़चनों का संकेत देती हैं।

पीसी कॉन्फ़िगरेशन: DDR3-1066 2GB, P6200 (2x2.13GHz)।
("एफपी" के रूप में पढ़ा "FlashPlayerDebugger 11.9.900.170", रिलीज़)

काम की गति

	एफपी	PepperFlash
200,000 आइटम
mergeSort	160ms	81ms
देशी छँटाई	81ms	90ms
2,000,000 आइटम
mergeSort	1800ms	921ms
देशी छँटाई	1378ms	1425ms
20,000,000 आइटम
mergeSort	21374ms	10267ms
देशी छँटाई	20404ms	21175ms

अब बाधाओं को थोड़ा अनुकूलित करें:

Math.min सरल परिस्थितियों की तुलना में बहुत धीमा है।
बिट शिफ्ट 2 से गुणा और विभाजन से तेज है।
आप अभी भी याद रख सकते हैं कि && वास्तव में क्या करता है, और इससे छुटकारा पा सकते हैं।

हमें मिलता है:

कोड

 function mergeSort(array:Vector.<int>, buffer:Vector.<int> = null):Vector.<int> { var length:uint = array.length; var result:Vector.<int> = array; buffer = buffer ? buffer : new Vector.<int>(length, true); for (var chunkSize:uint = 1; chunkSize < length; chunkSize <<= 1) { var bufferPointer:uint = 0; var leftChunkStart:uint = 0; for (; leftChunkStart < length; leftChunkStart += chunkSize << 1) { var rightChunkStart:uint = leftChunkStart + chunkSize; var rightChunkEnd:uint = rightChunkStart + chunkSize; if (length < rightChunkEnd) { rightChunkEnd = length; if (length < rightChunkStart) { rightChunkStart = length; } } var leftChunkEnd:uint = rightChunkStart; var leftPointer:uint = leftChunkStart; var rightPointer:uint = rightChunkStart; while (leftPointer - leftChunkEnd & rightPointer - rightChunkEnd) { if (array[leftPointer] < array[rightPointer]) { buffer[bufferPointer++] = array[leftPointer++]; }else { buffer[bufferPointer++] = array[rightPointer++]; } } while (leftPointer < leftChunkEnd) { buffer[bufferPointer++] = array[leftPointer++]; } while (rightPointer < rightChunkEnd) { buffer[bufferPointer++] = array[rightPointer++]; } } var temp:Vector.<int> = array; array = buffer; buffer = temp; } if (result !== array) { for (var i:uint = 0; i < length; i++ ) { result[i] = array[i]; } } return result; }

10 ^ 8 तत्व मुझ पर इस तरह के कार्यान्वयन 47 सेकंड PepperFlash में सॉर्ट करते हैं।

काम की गति

	एफपी	PepperFlash
200,000 आइटम
mergeSort	130ms	64ms
देशी छँटाई	81ms	90ms
2,000,000 आइटम
mergeSort	1462ms	730ms
देशी छँटाई	1378ms	1425ms
20,000,000 आइटम
mergeSort	16937ms	8435ms
देशी छँटाई	20404ms	21175ms
200 तत्व और 1000 छँटाई
mergeSort	88ms	38ms
देशी छँटाई	70 एमएस आपातकालीन	48ms
ऐरे सृजन यादृच्छिक तत्वों के साथ	36ms	10ms
2000 तत्व और 10,000 प्रकार
mergeSort	10077ms	4809ms
देशी छँटाई	6885ms	5912ms
ऐरे सृजन यादृच्छिक तत्वों के साथ	2178ms	760ms

पूरी तरह से सॉर्ट किए गए सरणियों के मामले में, दोनों प्रकार तेज हैं (उदाहरण के लिए, 2,000,000 तत्वों के साथ लगभग 30% तेज, दोनों)।
मूल छंटाई के लिए लगभग n * 1.5 अतिरिक्त मेमोरी, मर्जस्टॉर्ट - बिल्कुल n की आवश्यकता होती है।

नतीजतन, एफपी में इन आंदोलनों से लाभ पर्याप्त नहीं है। लेकिन PepperFlash में आप संख्या को लगभग दो कम देख सकते हैं।

मर्ज सॉर्ट और AS3। मूल वेक्टर से बाहर निकलकर ।ort (Array.NUMERIC)

More articles: