Tri des minuscules en python

J'essaie de me convaincre qu'un tri par comptage est plus rapide que la méthode triée en Python. Cependant appeler l'intégré trié semble être plus rapide même pour les grandes entrées comme 10 millions d'éléments. Que puis-je faire pour que le comptage soit plus rapide?Tri des minuscules en python

Je générons une liste de lettres minuscules pour simplifier l'exemple 26 valeurs uniques:

letters = [random.choice(string.ascii_lowercase) for i in range(10000000)]

je puis faire la variation suivante sur tri par comptage:

def sorted_count(letters): 
counts = [0] * 26 
for letter in letters: 
    counts[ord(letter) - 97] += 1 
out = [None] * len(letters) 
j = 0 
for i in range(len(counts)): 
    while counts[i] > 0: 
     out[j] = chr(i + 97) 
     counts[i] -= 1 
     j += 1 
return out

Même sur 10.000.000 éléments l'appel à sorted(letters) est ~ 4x plus rapide. Comment puis-je améliorer la vitesse de mon tri? Au lieu d'utiliser une boucle while à l'intérieur du forloop à la fin.

Source

2017-10-18 eLymar

Do vous avez tout le script timeit? –

En outre, vous comparez du code Python brut avec du code C optimisé. 4x plus lent n'est vraiment pas mauvais, et pourrait être considéré comme "plus rapide". –

Vous posez des questions sur les améliorations algorithmiques (théoriques)? En pratique, mesurer la performance des algorithmes en python pur n'a pas beaucoup de sens. Comme @EricDuminil l'a mentionné, la comparaison avec [tri intégré] (https://github.com/python/cpython/blob/2ebc5ce42a8a9e047e790aefbf9a94811569b2b6/Objects/listobject.c#L1978) (qui est une sorte de comparaison écrite en C) est invalide. Pour les cas d'utilisation réels, utilisez un langage natif (éventuellement une extension C++ pour python), allez en parallèle, essayez les GPUs, trouvez la structure dans vos données d'entrée qui permet une gestion plus rapide des carrefours etc. – Drop

vous pourriez simplement utiliser

for i in range(len(counts)): 
if counts[i]>0: 
    out[j] =counts[i]*chr(i + 97) 
j+=1 
return out

Source

2017-10-18 10:47:31

're bienvenue :) –

a dû changer à cela, mais a réussi à avoir une grosse bosse de vitesse: out = [] pour i dans la gamme (LEN (chiffres)): out + = liste (compte [i] * chr (i + 97)) – eLymar

ouais je viens de donner le contour sur la façon de le faire, plus tôt il avait sur O (n^2) la complexité tandis que le comptage a en fait O (n + k) qui explique pourquoi sa vitesse a été réduite significativement –

est ici une fonction modifiée, ce qui est 3 fois plus rapide que celui qui est proposé et deux fois plus vite que sorted:

import random 
import string 
import timeit 
N = 1000000 
letters = [random.choice(string.ascii_lowercase) for i in range(N)] 


def original_sorted_count(letters): 
    counts = [0] * 26 
    for letter in letters: 
     counts[ord(letter) - 97] += 1 
    out = [None] * len(letters) 
    j = 0 
    for i in range(len(counts)): 
     while counts[i] > 0: 
      out[j] = chr(i + 97) 
      counts[i] -= 1 
      j += 1 
    return out 

def eric(letters): 
    counts = [0] * 26 
    for letter in letters: 
     counts[ord(letter) - 97] += 1 
    out = [] 
    for i in range(len(counts)): 
     out += [chr(i+97)] * counts[i] 
    return out 

print('Original : %.3fs' %timeit.timeit(lambda: original_sorted_count(letters), number=20)) 
print('Sorted : %.3fs' %timeit.timeit(lambda: sorted(letters), number=20)) 
print('Eric  : %.3fs' %timeit.timeit(lambda: eric(letters), number=20)) 

print(eric(letters) == sorted(letters))

Il produit:

Original : 9.616s 
Sorted : 6.367s 
Eric  : 3.604s 
True

Source

2017-10-18 12:43:45

Tri des minuscules en python

Répondre

Questions connexes