Sortieren von Kleinbuchstaben in Python

Ich versuche mich davon zu überzeugen, dass eine zählende Sortierung schneller als die sortierte Methode in Python ausführt. Das Aufrufen des sortierten Bausteins scheint jedoch selbst für große Eingaben wie 10 Millionen Elemente schneller zu sein. Was kann ich tun, um das Zählen schneller zu machen?Sortieren von Kleinbuchstaben in Python

erzeugen ich eine Liste von Kleinbuchstaben um das Beispiel zu 26 eindeutige Werte zu vereinfachen:

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

ich tun, dann wird die folgende Variante Countingsort:

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

Auch auf 10.000.000 Elemente der Anruf zu sorted(letters) ist ~ 4x schneller. Wie kann ich die Geschwindigkeit meiner Sorte verbessern?

Quelle

2017-10-18 eLymar

Do Hast du das ganze Timeit-Skript? –

Außerdem vergleichen Sie einfachen Python-Code mit optimiertem C-Code. 4x langsamer ist wirklich nicht schlecht und könnte als "schneller" angesehen werden. –

Fragen Sie nach (theoretischen) algorithmischen Verbesserungen? In der Praxis macht es wenig Sinn, die Performance von Algorithmen in reinem Python zu messen. Wie @EricDuminil erwähnt, ist der Vergleich mit [built-in sort] (https://github.com/python/cpython/blob/2ebc5ce42a8a9e047e790aefbf9a94811569b2b6/Objects/listobject.c#L1978) (was eine Vergleichssortierung in C geschrieben ist) ungültig. Für reale Anwendungsfälle verwenden Sie eine native Sprache (möglicherweise eine C++ Erweiterung für Python), gehen parallel, versuchen GPUs, finden Struktur in Ihren Eingabedaten, die eine schnellere Edge-Case-Behandlung ermöglichen usw. – Drop

Anstelle einer While-Schleife im Inneren des Forloops am Ende. Sie könnten einfache Bedienung

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

Quelle

2017-10-18 10:47:31

Sie sind willkommen :) –

Hatte es zu ändern, aber eine große Beule in Geschwindigkeit bekommen: out = [] für i in Reichweite (len (counts)): out + = Liste (counts [i] * chr (i + 97)) – eLymar

yeah ich habe gerade den Überblick darüber gegeben, wie man es macht, früher hatte es etwa O (n^2) Komplexität, während das Zählen eigentlich O (n + k) hat, weshalb seine Geschwindigkeit reduziert wurde deutlich –

Hier ist eine modifizierte Funktion, die als die vorgeschlagene eines 3-mal schneller ist und doppelt so schnell wie 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))

Es gibt:

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

Quelle

2017-10-18 12:43:45

Sortieren von Kleinbuchstaben in Python

Antwort

Verwandte Themen