पायथन

Question

में सॉर्ट करने का सबसे तेज़ तरीका पाइथन में 0 से बड़ा और 100000 से कम पूरे पूर्णांक की सरणी को सॉर्ट करने का सबसे तेज़ तरीका क्या है? लेकिन क्रमबद्ध कार्यों में इस्तेमाल नहीं करते हैं।

मैं इनपुट आकार के आधार पर 2 खेल कार्यों को गठबंधन करने की संभावना को देख रहा हूं।

Answer 1

आप asymptotic समय में रुचि रखते हैं, तो गिनती तरह या मूलांक प्रकार अच्छा प्रदर्शन प्रदान करें।

हालांकि, अगर आप दीवार घड़ी समय में रुचि रखते हैं आप अपने विशेष डेटा सेटका उपयोग कर विभिन्न एल्गोरिदम के प्रदर्शन की तुलना, के रूप में अलग अलग एल्गोरिदम अलग डेटासेट के साथ अलग ढंग से प्रदर्शन की आवश्यकता होगी। उस मामले में, अपने हमेशा के लायक कोशिश कर quicksort:

def qsort(inlist): 
    if inlist == []: 
     return [] 
    else: 
     pivot = inlist[0] 
     lesser = qsort([x for x in inlist[1:] if x < pivot]) 
     greater = qsort([x for x in inlist[1:] if x >= pivot]) 
     return lesser + [pivot] + greater 

स्रोत: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python अजगर की

Answer 2

चूंकि आप संख्याओं की सीमा जानते हैं, तो आप Counting Sort का उपयोग कर सकते हैं जो समय पर रैखिक होगा।

Answer 3

कार्यों में बनाया गया सबसे अच्छा कर रहे हैं, लेकिन जब से तुम उपयोग नहीं कर सकते उन्हें इस पर एक नजर है:

http://en.wikipedia.org/wiki/Quicksort

Answer 4

प्रारंभिक संस्करणों का निर्माण के रूप में samplesort का एक संकर (बड़े आकार के नमूने के साथ quicksort का एक प्रकार) और बाइनरी प्रविष्टि तरह इस्तेमाल किया क्रमबद्ध एल्गोरिदम। यह कुछ हद तक अस्थिर साबित हुआ। S0, अजगर 2.3 से आगे adaptive mergesort एल्गोरिदम का उपयोग करता है।

विलय (औसत) = O(nlogn) का आदेश। विलय का आदेश (सबसे खराब) = O(nlogn)। लेकिन त्वरित तरह का आदेश (सबसे खराब) = n * 2

अगर आप list=[ .............. ]

list.sort() का उपयोग करता mergesort algorithm.

का उपयोग करता है एल्गोरिथ्म छँटाई के बीच तुलना के लिए आप wiki

विस्तार तुलना comp

के लिए पढ़ सकते हैं

Answer 5

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

यदि आप वास्तव में छोटे आकार के इनपुट के लिए भारी गति चाहते हैं, तो सी में गिनती प्रकार लागू करें और इसे पायथन से कॉल करें।

(एक बग फिक्स्ड जो हारून (+1) पकड़ में मदद की ...) अजगर केवल नीचे कार्यान्वयन तुलना 2 दृष्टिकोण ...

import random 
import time 

COUNT = 3000000 

array = [random.randint(1,100000) for i in range(COUNT)] 
random.shuffle(array) 

array1 = array[:] 

start = time.time() 
array1.sort() 
end = time.time() 
time1 = (end-start) 
print 'Time to sort = ', time1*1000, 'ms' 

array2 = array[:] 

start = time.time() 
ardict = {} 
for a in array2: 
    try: 
     ardict[a] += 1 
    except: 
     ardict[a] = 1 

indx = 0 
for a in sorted(ardict.keys()): 
    b = ardict[a] 
    array2[indx:indx+b] = [a for i in xrange(b)] 
    indx += b 

end = time.time() 
time2 = (end-start) 
print 'Time to count sort = ', time2*1000, 'ms' 

print 'Ratio =', time2/time1 

Answer 6

मूलांक तरह सैद्धांतिक रूप से रैखिक समय में चलाता है (तरह समय लगभग सरणी आकार के प्रत्यक्ष अनुपात में बढ़ता है), लेकिन अभ्यास में क्विक्सोर्ट शायद अधिक उपयुक्त है, जब तक कि आप बिल्कुल बड़े पैमाने पर सरणी को सॉर्ट नहीं कर रहे हों।

आप थोड़ा तेजी से quicksort बनाना चाहते हैं, तो आप प्रविष्टि प्रकार] जब सरणी आकार छोटा हो जाता है का उपयोग कर सकते हैं।

यह शायद बहुत एल्गोरिथम जटिलता और बड़े-ओ अंकन की अवधारणाओं को समझने के लिए उपयोगी होगा।

Answer 7

def sort(l): 
    p = 0 
    while(p<len(l)-1): 
     if(l[p]>l[p+1]): 
      l[p],l[p+1] = l[p+1],l[p] 
      if(not(p==0)): 
       p = p-1 
     else: 
      p += 1 
    return l 

यह एक एल्गोरिदम है जिसे मैंने बनाया लेकिन वास्तव में तेज़ है। बस क्रमबद्ध करें (एल) एल सूची है जिसे आप सॉर्ट करना चाहते हैं।

Answer 8

@fmark एक अजगर मर्ज-तरह कार्यान्वयन मैं http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python से और शीर्ष जवाब से अजगर quicksorts के खिलाफ लिखा में से कुछ बेंच मार्किंग। अप्रासंगिक सूची में सूची और संख्या के आकार

मर्ज तरह जीत के

1. आकार, लेकिन यह फर्श पर निर्मित पूर्णांक()

   import numpy as np 
   x = list(np.random.rand(100)) 
   
   
   # TEST 1, merge_sort 
   def merge(l, p, q, r): 
       n1 = q - p + 1 
       n2 = r - q 
       left = l[p : p + n1] 
       right = l[q + 1 : q + 1 + n2] 
   
       i = 0 
       j = 0 
       k = p 
       while k < r + 1: 
        if i == n1: 
         l[k] = right[j] 
         j += 1 
        elif j == n2: 
         l[k] = left[i] 
         i += 1 
        elif left[i] <= right[j]: 
         l[k] = left[i] 
         i += 1 
        else: 
         l[k] = right[j] 
         j += 1 
        k += 1 
   
   def _merge_sort(l, p, r): 
       if p < r: 
        q = int((p + r)/2) 
        _merge_sort(l, p, q) 
        _merge_sort(l, q+1, r) 
        merge(l, p, q, r) 
   
   def merge_sort(l): 
       _merge_sort(l, 0, len(l)-1) 
   
   # TEST 2 
   def quicksort(array): 
       _quicksort(array, 0, len(array) - 1) 
   
   def _quicksort(array, start, stop): 
       if stop - start > 0: 
        pivot, left, right = array[start], start, stop 
        while left <= right: 
         while array[left] < pivot: 
          left += 1 
         while array[right] > pivot: 
          right -= 1 
         if left <= right: 
          array[left], array[right] = array[right], array[left] 
          left += 1 
          right -= 1 
        _quicksort(array, start, right) 
        _quicksort(array, left, stop) 
   
   # TEST 3 
   def qsort(inlist): 
       if inlist == []: 
        return [] 
       else: 
        pivot = inlist[0] 
        lesser = qsort([x for x in inlist[1:] if x < pivot]) 
        greater = qsort([x for x in inlist[1:] if x >= pivot]) 
        return lesser + [pivot] + greater 
   
   def test1(): 
       merge_sort(x) 
   
   def test2(): 
       quicksort(x) 
   
   def test3(): 
       qsort(x) 
   
   if __name__ == '__main__': 
       import timeit 
       print('merge_sort:', timeit.timeit("test1()", setup="from __main__ import test1, x;", number=10000)) 
       print('quicksort:', timeit.timeit("test2()", setup="from __main__ import test2, x;", number=10000)) 
       print('qsort:', timeit.timeit("test3()", setup="from __main__ import test3, x;", number=10000)) 
   

Answer 9

मैं करने के लिए देर से एक छोटे से हो सकता है का उपयोग करता है शो, लेकिन एक दिलचस्प लेख है जो विभिन्न प्रकारों की तुलना करता है https://www.linkedin.com/pulse/sorting-efficiently-python-lakshmi-prakash

मुख्य टेकवे में से एक यह है कि डिफ़ॉल्ट सॉर्ट करते समय बहुत अच्छा हम Quicksort के एक संकलित संस्करण के साथ थोड़ा बेहतर कर सकते हैं। इसके लिए नुम्बा पैकेज की आवश्यकता है। https://github.com/lprakash/Sorting-Algorithms/blob/master/sorts.ipynb