रैडिक्स सॉर्ट (और पायथन) को अपनी सीमाओं में

Question

पुशिंग करना मैं वेब पर पाइथन रेडिक्स सॉर्ट करने के कई कार्यान्वयन के साथ बेहद निराश हूं।

वे लगातार 10 की रेडिक्स का उपयोग करते हैं और 10 की शक्ति से विभाजित करके या संख्या के लॉग 10 को ले कर संख्याओं के अंकों को प्राप्त करते हैं। यह अविश्वसनीय रूप से अक्षम है, क्योंकि लॉग 10 बिट स्थानांतरण के मुकाबले विशेष रूप से त्वरित ऑपरेशन नहीं है, जो लगभग 100 गुना तेज है!

एक और अधिक कुशल कार्यान्वयन 256 के रेडिक्स का उपयोग करता है और बाइट द्वारा संख्या बाइट टाइप करता है। यह हास्यास्पद त्वरित बिट ऑपरेटरों का उपयोग करके सभी 'बाइट हो रही' करने के लिए अनुमति देता है। दुर्भाग्यवश, ऐसा लगता है कि बिल्कुल बाहर कोई भी पाइथन में एक रेडिक्स प्रकार लागू नहीं किया है जो लॉगरिदम के बजाय बिट ऑपरेटर का उपयोग करता है।

तो, मैं अपने ही हाथों में मामलों ले लिया और इस जानवर है, जो के बारे में आधे छोटे सरणियों पर हल कर की गति से चलाता है और बड़ों पर के रूप में जल्दी लगभग चलाता है के साथ आया था (जैसे len 10000000 के आसपास):

import itertools 

def radix_sort(unsorted): 
    "Fast implementation of radix sort for any size num." 
    maximum, minimum = max(unsorted), min(unsorted) 

    max_bits = maximum.bit_length() 
    highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1 

    min_bits = minimum.bit_length() 
    lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1 

    sorted_list = unsorted 
    for offset in xrange(lowest_byte, highest_byte): 
     sorted_list = radix_sort_offset(sorted_list, offset) 

    return sorted_list 

def radix_sort_offset(unsorted, offset): 
    "Helper function for radix sort, sorts each offset." 
    byte_check = (0xFF << offset*8) 

    buckets = [[] for _ in xrange(256)] 

    for num in unsorted: 
     byte_at_offset = (num & byte_check) >> offset*8 
     buckets[byte_at_offset].append(num) 

    return list(itertools.chain.from_iterable(buckets)) 

रेडिक्स सॉर्ट का यह संस्करण यह पता लगाकर काम करता है कि किस बाइट को इसे क्रमबद्ध करना है (यदि आप इसे 256 से नीचे केवल पूर्णांक पास करते हैं, तो यह केवल एक बाइट इत्यादि को सॉर्ट करेगा) फिर एलएसबी से प्रत्येक बाइट को डंप करके सॉर्ट करना क्रम में बाल्टी में बस एक साथ बाल्टी चेन। इसे प्रत्येक बाइट के लिए दोहराएं जिसे सॉर्ट करने की आवश्यकता है और आपके पास ओ (एन) समय में आपका अच्छा क्रमबद्ध सरणी है।

हालांकि, यह जितना तेज़ नहीं हो सकता है, और मैं इसे अन्य सभी रेडिक्स प्रकारों की तुलना में बेहतर रेडिक्स प्रकार के रूप में लिखने से पहले इसे तेज़ी से बनाना चाहता हूं।

cProfile चल रहा है पर इस मुझसे कहता है कि बहुत समय सूचियों के लिए append विधि है, जो मुझे लगता है कि इस ब्लॉक कि बनाता है पर खर्च किया जा रहा है:

for num in unsorted: 
     byte_at_offset = (num & byte_check) >> offset*8 
     buckets[byte_at_offset].append(num) 

radix_sort_offset में बहुत समय खा रहा है। यह भी ब्लॉक है कि, यदि आप वास्तव में इसे देखते हैं, तो पूरे प्रकार के काम का 9 0% काम करता है। यह कोड ऐसा लगता है कि यह numpy -ized हो सकता है, जो मुझे लगता है कि परिणामस्वरूप काफी प्रदर्शन होगा। दुर्भाग्यवश, मैं numpy की अधिक जटिल विशेषताओं के साथ बहुत अच्छा नहीं हूं इसलिए इसे समझने में सक्षम नहीं है। मदद की बहुत सराहना की जाएगी।

मैं वर्तमान में itertools.chain.from_iterable का उपयोग buckets को फ़्लैट करने के लिए कर रहा हूं, लेकिन अगर किसी के पास तेज सुझाव है तो मुझे यकीन है कि इससे भी मदद मिलेगी।

मूल रूप से, मेरे पास get_byte फ़ंक्शन था जो n वें बाइट को वापस कर देता था, लेकिन कोड को रेखांकित करने से मुझे एक बड़ी गति वृद्धि मिली, इसलिए मैंने इसे किया।

कार्यान्वयन या अधिक प्रदर्शन को निचोड़ने के तरीकों पर कोई अन्य टिप्पणियां भी सराहना की जाती हैं। मैं कुछ और सब कुछ सुनना चाहता हूं।

Answer 1

आप पहले से ही महसूस किया कि

for num in unsorted: 
    byte_at_offset = (num & byte_check) >> offset*8 
    buckets[byte_at_offset].append(num) 

जहां ज्यादातर समय चला जाता है - दोनों चलती अपरिवर्तनशीलताओं साथ क्या करने वाले अच्छा ;-)

बात उस तरह तेजी के लिए दो मानक चालें कर रहे हैं, लूप से बाहर:

1. लूप के बाहर "ऑफसेट * 8" की गणना करें।इसे एक स्थानीय चर में स्टोर करें। प्रति पुनरावृत्ति प्रति गुणा बचाओ।
2. लूप के बाहर bucketappender = [bucket.append for bucket in buckets] जोड़ें। प्रति पुनरावृत्ति के लिए एक विधि लुकअप बचाता है।

उन्हें कम्बाइन, और पाश की तरह दिखता है:

for num in unsorted: 
    bucketappender[(num & byte_check) >> ofs8](num) 

यह एक बयान के गिर भी स्थानीय vrbl दुकान की एक जोड़ी की बचत होती है/यात्रा प्रति opcodes लाने।

लेकिन, उच्च स्तर पर, रेडिक्स प्रकार को गति देने का मानक तरीका एक बड़ा रेडिक्स का उपयोग करना है। 256 के बारे में जादुई क्या है? कुछ भी नहीं, इसके अलावा यह बिट-स्थानांतरण के लिए सुविधाजनक है। लेकिन 512, 1024, 2048 हैं ... यह एक शास्त्रीय समय/अंतरिक्ष व्यापार है।

पुनश्च: बहुत लंबे समय की संख्या के लिए,

(num >> offset*8) & 0xff 

तेजी से चलेंगे। ऐसा इसलिए है क्योंकि num & byte_checklog(num) पर आनुपातिक समय लेता है - इसे आमतौर पर num जितना बड़ा होना चाहिए।

Answer 2

आप बस usort से Boost.Sort से मौजूदा सी में से एक या सी ++ कार्यान्वयन, इस तरह के उदाहरण के रूप में, integer_sort या u4_sort इस्तेमाल कर सकते हैं। पाइथन से देशी सी या सी ++ कोड को कॉल करना आश्चर्यजनक रूप से आसान है, How to sort an array of integers faster than quicksort?

मुझे पूरी तरह से आपकी निराशा मिलती है। हालांकि यह 2 साल से अधिक रहा है, numpy still does not have radix sort। मैं NumPy डेवलपर्स को यह बता दूंगा कि वे केवल मौजूदा कार्यान्वयन में से एक को पकड़ सकते हैं; लाइसेंसिंग एक मुद्दा नहीं होना चाहिए।

Answer 3

यह एक पुराना धागा है, लेकिन जब मैं रेडिक्स को सकारात्मक पूर्णांक की सरणी क्रमबद्ध करता हूं तो मैं इस पर आया। मैं यह देखने की कोशिश कर रहा था कि क्या मैं पहले से ही बुरी तरह से तेज समय के साथ बेहतर प्रदर्शन कर सकता हूं (टॉम पीटर्स को फिर से टकराने वाला) जो पाइथन के बिल्टिन सॉर्ट और सॉर्ट करता है! या तो मैं उपरोक्त कोड के कुछ पहलुओं को समझ नहीं पा रहा हूं, या यदि मैं करता हूं, तो ऊपर प्रस्तुत कोड में आईएमएचओ की कुछ समस्याएं हैं।

1. यह केवल छोटी से छोटी वस्तु के उच्चतम बाइट के साथ शुरू और सबसे बड़ी आइटम के उच्चतम बाइट के साथ समाप्त बाइट्स क्रमबद्ध करता है। यह विशेष डेटा के कुछ मामलों में ठीक हो सकता है। लेकिन आम तौर पर दृष्टिकोण कम बिट्स के कारण अलग-अलग वस्तुओं को अलग करने में विफल रहता है। उदाहरण के लिए:

   arr=[65535,65534] 
   radix_sort(arr) 
   

   गलत उत्पादन का उत्पादन:

   [65535, 65534] 
   

2. रेंज सहायक समारोह की पाश करने के लिए इस्तेमाल सही नहीं है। मेरा मतलब यह है कि यदि निम्नतम_बाइट और उच्चतम_बाइट समान हैं, तो सहायक कार्य का निष्पादन पूरी तरह से छोड़ दिया जाता है। बीटीडब्ल्यू मुझे 2 स्थानों में एक्सेंज को रेंज में बदलना पड़ा।

3. उपर्युक्त 2 बिंदुओं को संबोधित करने के लिए संशोधनों के साथ, मुझे यह काम करने के लिए मिला। लेकिन यह पाइथन के बिल्टिन सॉर्ट या सॉर्ट के समय में 10-20 गुना ले रहा है! मुझे पता है कि timsort बहुत कुशल है और डेटा में पहले से क्रमबद्ध रन का लाभ उठाता है। लेकिन मैं यह देखने की कोशिश कर रहा था कि क्या मैं पूर्व ज्ञान का उपयोग कर सकता हूं कि मेरा डेटा मेरे सॉर्टिंग में कुछ फायदे के लिए सभी सकारात्मक पूर्णांक है। रेडिक्स सॉर्ट टाइम्सॉर्ट की तुलना में इतनी बुरी तरह क्यों कर रहा है? मैं जिस सरणी आकार का उपयोग कर रहा था वह 80 के आइटम के क्रम में है।क्या ऐसा इसलिए है क्योंकि इसके एल्गोरिदमिक दक्षता के अलावा टाइम्सॉर्ट कार्यान्वयन में निम्न स्तर की पुस्तकालयों के संभावित उपयोग से उत्पन्न होने वाली अन्य क्षमताएं भी हैं? या क्या मैं पूरी तरह से कुछ याद कर रहा हूँ? संशोधित कोड मैं का इस्तेमाल किया नीचे है:

   import itertools 
   
   def radix_sort(unsorted): 
       "Fast implementation of radix sort for any size num." 
       maximum, minimum = max(unsorted), min(unsorted) 
   
       max_bits = maximum.bit_length() 
       highest_byte = max_bits // 8 if max_bits % 8 == 0 else (max_bits // 8) + 1 
   
   # min_bits = minimum.bit_length() 
   # lowest_byte = min_bits // 8 if min_bits % 8 == 0 else (min_bits // 8) + 1 
   
       sorted_list = unsorted 
   # xrange changed to range, lowest_byte deleted from the arguments 
       for offset in range(highest_byte): 
        sorted_list = radix_sort_offset(sorted_list, offset) 
   
       return sorted_list 
   
   def radix_sort_offset(unsorted, offset): 
       "Helper function for radix sort, sorts each offset." 
       byte_check = (0xFF << offset*8) 
   
   # xrange changed to range 
       buckets = [[] for _ in range(256)] 
   
       for num in unsorted: 
        byte_at_offset = (num & byte_check) >> offset*8 
        buckets[byte_at_offset].append(num) 
   
       return list(itertools.chain.from_iterable(buckets))