Performanz optimieren (for-Schleife + Liste sortieren)

[silentbreaker]

Hallo,

ich habe ein Problem mit der Performanz, wenn ich mittels einer for-Schleife eine Liste alphabetisch bzw. zufällig sortieren möchte. Die Schwierigkeit ist, dass immer 5 Elemente der Liste zusammengehören und dadurch auch zusammen verschoben werden müssen. Und eben das dauert ewig. Wie kann ich da die Geschwindigkeit erhöhen? Geht das evtl. mittels list comprehension oder map()? Hier mal der bisherige Code:

Code: Alles auswählen

for i in range(len(vokabeln)) : #Vokabeln in zufälliger Reihenfolge sortieren
    index = randint(0, (len(vokabeln)/5)-5)
    index = index*5
    vokabeln = vokabeln [ 0 : index] + vokabeln [ index+5 : ] + vokabeln [ index : index+5]
vokabeln_random = vokabeln[:]

vertauscht = 1 #Vokabeln in alphabetischer Reihenfolge - 1. Sprache sortieren
while vertauscht:
    vertauscht = 0
    for index in range(0,len(vokabeln)-6,5) :
        cmp_val = locale.strcoll(lower(vokabeln [index]),lower(vokabeln [index+5]))
        if cmp_val == 1:
            vokabeln = vokabeln [ 0 : index] + vokabeln [ index+5 : ] + vokabeln [ index : index+5]
            vertauscht = 1
vokabeln_sorted1 = vokabeln[:]

Schon mal vielen Dank im voraus.

[modelnine]

Deine Datenstruktur ist sehr suboptimal. Folgende Datenstruktur ist besser für Dein Problem geeignet:

Mach eine Liste von Tupeln mit dem Schlüssel (also zum Beispiel dem deutschen Wort) als das erste Element, und sortier die mittels der eingebauten .sort()-Funktion der Liste. Beispiel:

Code: Alles auswählen

words = [("hallo","hello","hoi"),("tag","day","dag"),("schleife","loop","sling")]
words.sort()
print words

[silentbreaker]

An Tupel hab ich auch schon gedacht, nur hab ich keine Idee wie ich aus der einfachen Liste eine Liste mit Tupeln und wieder zurück mache. Denn in anderen Funktionen müssen die Elmente der Liste einzeln bearbeitbar sein. Ich müsste die Liste also vorübergehend umwandeln. Wie geht das möglichst schnell?

[modelnine]

Dann schreib die anderen Funktionen um, so dass sie auch sowas akzeptieren. Du kannst ja in den Funktionen das Tupel neu aufbauen, das ist allemal besser als so eine Datenstruktur zu behalten.

Sprich:

Code: Alles auswählen

def workonfirst(lst,i):
    lst[i] = ("test",)+lst[i][1:]

lst = [("hallo","hello","hoi"),("tag","day","dag"),("schleife","loop","sling")]
print lst
workonfirst(lst,1)
print lst

Wenn's gar nicht anders geht, mußt Du eben eine Schleife machen die die Konversion jedes mal in die eine und die andere Richtung macht. Das ist aber grausam, da ineffizient, und die Datenstruktur sowieso nicht gut ist, da eine Liste nicht dazu da ist um Gruppen anders zu behandeln, das gruppieren mußt Du bitteschön mit einem Datentyp wie Tupeln machen.

[silentbreaker]

Ich wollte das umstellen auf Listen mit Tupel vermeiden, weil das ne ganze Menge Arbeit ist.

Werd mich dann mal dran machen.

Na ja, aber danke erstmal.

[digitus]

Schon mal dran gedacht die Wörter in einer Klasse zu verpacken? Die Realisierungen in den 3 Sprachen könntest du in self-Attributen speichern.

Die Instanzen der Klasse könntest du in ne Liste packen und die mit random.shuffle bequem mischen.

[Joghurt]

An Tupel hab ich auch schon gedacht, nur hab ich keine Idee wie ich aus der einfachen Liste eine Liste mit Tupeln und wieder zurück mache

Du kannst auch eine Liste von Listen machen:

Code: Alles auswählen

lst = [["hallo","hello","hoi"],["tag","day","dag"],["schleife","loop","sling"]]

[modelnine]

Du kannst auch eine Liste von Listen machen: ...

Ist aber beim sortieren etwas langsamer, nur glaub ich kaum dass es darauf hier ankommt. Also, sprich, wenn's um einfache Erweiter- und Änderbarkeit geht, ist Joghurt's Vorschlag meinem definitiv vorzuziehen.

[silentbreaker]

Ich habs jetzt mit einer Liste von Tupeln gemacht und alle anderen Programmteile auch umgestellt. Und ich bin beeindruckt um wie viel schneller sort ist. Das hätte ich nicht gedacht.
Inzwischen habe ich auch eine Lösung für die Umwandlung der Liste gefunden:

Code: Alles auswählen

vokabeln_order = [tuple(vokabeln [i : i+5]) for i in xrange(0, len(vokabeln), 5)]

Mein Problem hat sich also erledigt. Vielen Dank für die Hilfe!

PS.: Die Vokabeln in eine Klasse auszulagern ist in meinem Fall Quatsch, da ich die Vokabeln aus einer Datei einlese.

[modelnine]

... Und ich bin beeindruckt um wie viel schneller sort ist. ...

Sag ich doch!

Um das mal ein bissel auszuführen: Du benutzt zum Sortieren in der geposteten Variante eine Adaption von Bubblesort, die auf jeden Fall O(n^2) Laufzeit hat, zumal der Algorithmus vollständig in Python abläuft. Das eingebaute .sort() der Liste benutzt einen adaptierten Quick-/Merge-Sort, das hat Laufzeit O(n*logn), was schon mal massiv was ausmacht (bei großen Datenmengen), zumal der Algorithmus eben auch beim Tupelvergleich sehr viel in C selbst erledigen kann (da er für strings gewisse Shortcuts hat), da der Vergleich zweier Strings vollständig in C-Code erledigt werden kann und keinen Python-Aufruf nach sich zieht.

Alles in allem ist es also nicht verwunderlich dass die Performance mit einem .sort() massiv besser ist; deswegen wird in Python für das sortieren nach einem Schlüssel auch (fast) immer DSU (decorate-sort-undecorate) empfohlen, und nicht eine selbstgebaute Vergleichsfunktion, da letzteres eben auch ein dispatchen in Python-Code nach sich zieht, was das extrem schnelle Quick-Sort von .sort() ausbremst.