Swap Sort

Code-Stücke können hier veröffentlicht werden.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Ich hab mir auf Wikipedia den Swap Sort Algorithmus angeguckt und habe ihn dort in den Sprachen Java, Ada und Haskell vorgefunden.
Mein erster Gedanke war: Aber jetzt auch mal in Python ;)
Man muss seine Lieblingssprache ja irgendwie verbreiten.

Fragen:
1.

Code: Alles auswählen

def swap_sort(sortme):
    index = 0
    while index < len(sortme) - 1:
        new_index = sum(1 for x in sortme if x < sortme[index])
        if index == new_index:
            index += 1
        else:
            sortme[index], sortme[new_index] = sortme[new_index], sortme[index]
    return sortme
Der Code ist so doch okay, oder?

2. Die Quelltexte der anderen Sprachen sind nur in <code>-Tags, also farblos, ich würde den Python-Code aber gerne in Farbe haben. Wär's irgendwie asozial, wenn ich da jetzt <source lang="python"> benutzen würde? Oder wär das in Ordnung, wenn ich die anderen dafür auch farbig mache? :p

3. Wär's sehr asozial, wenn ich Python an den Anfang statt an's Ende bringen würde? :p


Ich hab bisher noch nie was auf Wikipedia geändert und kenne deshalb auch keine Vorschriften oder so. Ich will nur nicht direkt irgendwie gelöscht werden oder sonstwas.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Nocta hat geschrieben:2. Die Quelltexte der anderen Sprachen sind nur in <code>-Tags, also farblos, ich würde den Python-Code aber gerne in Farbe haben. Wär's irgendwie asozial, wenn ich da jetzt <source lang="python"> benutzen würde? Oder wär das in Ordnung, wenn ich die anderen dafür auch farbig mache? :p
Ja, Syntax-Highlighting ist eigentlich immer gut, finde ich.
Nocta hat geschrieben:3. Wär's sehr asozial, wenn ich Python an den Anfang statt an's Ende bringen würde? :p
Die sind alphabetisch und wenn es keinen Grund gibt das zu ändern würde ich dabei bleiben.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Benutzeravatar
hendrikS
User
Beiträge: 420
Registriert: Mittwoch 24. Dezember 2008, 22:44
Wohnort: Leipzig

Von einem Projekt sind die 9 Zeilen jedoch weit entfernt. Ich finde es schade, wenn der Showcase mit Codesnippets überladen wird.

Edit (Leonidas): Ack, verschoben.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

@hendrikS sorry, darüber hatte ich gar nicht nachgedacht, das ist natürlich nur ein Codesnippet was man mal nebenbei in 5 Minuten schreibt.

Da Leonidas nicht auf 1) geantwortet hat, gehe ich mal davon aus, dass man den Code so stehen lassen kann und poste das jetzt mal in Wikipedia.

Edit: Vielleicht ist new_index nicht ganz so gut gewählt?
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Hallo,

ich würde das nicht in einer while-Schleife machen, sondern iterativ:

Code: Alles auswählen

#!/usr/bin/env python
"""
    An implementation of the swap sort algorithm[1] in Python.

    [1] http://de.wikipedia.org/wiki/Swap-Sort
"""
def swapitems(array, old, new):
    old_item = array[old]
    array[old] = array[new]
    array[new] = old_item
    return array

def swapsort(array):
    for i, elem in enumerate(array):
       array = swapitems(array, i, len([e for e in array if e < elem]))
    return array

if __name__ == '__main__':
    print swapsort([7, 8, 5, 2, 4, 9, 3, 1])
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Dauerbaustelle hat geschrieben:ich würde das nicht in einer while-Schleife machen, sondern iterativ:
Iterativ = Schrittweise = In Schleifen = Auch while ;)
Du kommst bestimmt wegen "iterieren" darauf, oder?

Warum machst du swapitems()? Ich fand gerade hier konnte man im Gegensatz zu den anderen 3 Sprachen eine Stärke von Python zeigen: a, b = b, a

Über for oder while kann man sich sich eventuell streiten, ich fand aber 1. die while-Schleife verständlicher und 2. ist diese näher an der Beschreibung des Algorithmus am Anfang der Wikipediaseite. Ich wüsste intuitiv/ohne Nachzudenken gar nicht, wie ich das mit einer for-Schleife lösen soll. Du anscheinend auch nicht, denn dein Algorithmus ist falsch bzw. zumindest nicht der Swap Sort Algorithmus ;)
print swapsort([7, 8, 5, 236, 123, 2, 4, 9, 3, 1, 34, 234])
=> [1, 4, 3, 234, 5, 7, 8, 9, 34, 2, 123, 236]
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Okay, dann so:

Code: Alles auswählen

def swapsort(array):
    for i, elem in enumerate(array):
        newindex = len([e for e in array if e < elem])
        if newindex != i:
            array[i], array[newindex] = array[newindex], array[i]
    return array
Das ist aber auch nicht richtig, seltsam... ich verstehe nicht, was ich da falsch gemacht habe?
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Ich hab mir das jetzt nicht genau angeguckt aber ich denke wegen dem Teil:

Code: Alles auswählen

if index == new_index:
            index += 1
Der Index geht nicht bei jedem Schritt eins hoch ;)
Deshalb finde ich da eine for-Schleife auch nicht so vorteilhaft.
Schau dir mal das Beispiel bei Wikipedia an.
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Oh, klar! Dann kann man das natürlich nicht mit einer for-Schleife machen.

Würde aber das nicht mit sum(...) sondern mit len(...) machen. Sieht toller aus ^^
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Mhm und dann schmink ich die Funktion noch n bisschen oder wie? :p
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Rüschen!
BlackJack

Bei `len()` muss man aber dauernd temporär Listen erstellen, nur um dann deren Länge zu ermitteln. Da ist die `sum()`-Variante effizienter.
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Ich wusste doch dass ich Recht habe. BlackJack, man siehe und staune:

Mit sum(...):
time python swapsort.py
real 0m0.252s
user 0m0.220s
sys 0m0.020s

time python swapsort.py
real 0m0.254s
user 0m0.232s
sys 0m0.012s

time python swapsort.py
real 0m0.266s
user 0m0.248s
sys 0m0.000s

time python swapsort.py
real 0m0.254s
user 0m0.240s
sys 0m0.008s

Ergibt Ø 0,256s
Mit len(...):
time python swapsort.py
real 0m0.247s
user 0m0.224s
sys 0m0.004s

time python swapsort.py
real 0m0.245s
user 0m0.228s
sys 0m0.004s

time python swapsort.py
real 0m0.236s
user 0m0.212s
sys 0m0.016s

time python swapsort.py
real 0m0.236s
user 0m0.216s
sys 0m0.008s

Ergibt Ø 0,241s
Code war dieser: http://paste.pocoo.org/show/108090/

Hihi :D
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Und was soll das beweisen? 4 Durchläufe jeweils, das ist keine aussagekräftige Sample-Größe.

Ich finde übrigens auch das ``sum()`` rein muss, schon allein deswegen weil es das in anderen Sprachen oft nicht gibt :twisted:
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
BlackJack

Deine Aussage war `len()` sieht toller aus. Das finde ich nicht. Das lässt sich auch mit einem Benchmark nicht ändern. Ich frage mich hier eher warum `sum()` langsamer ist, und wage mal zu behaupten, das ist kein Unterschied auf den man sich verlassen sollte.

Der Test hat übrigens noch den Schönheitsfehler, dass er einmal die Listen sortiert und dann neunmal auf bereits sortierten Listen operiert.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Und ich hab mal grad den Gegentest gemacht.
Der ist zwar genauso wenig aussagekräftig wie dein Test aber guckst du:

Code: Alles auswählen

x = range(1, 999)
random.shuffle(x)

timex = time.time()
for i in range(99):
    swap_sort(x)
print time.time() - timex
Dabei kamen bei swap_sort (sum) bei 3 Ausführungen diese Werte raus: 8.33400011063, 8.74899983406, 8.74899983406
Und bei swapsort (das ist die mit len): 9.23500013351, 9.3820002079, 9.89599990845
Benutzeravatar
Trundle
User
Beiträge: 591
Registriert: Dienstag 3. Juli 2007, 16:45

Der Test hat genau dasselbe Problem, dass die Liste nach dem ersten Durchlauf dann sortiert vorliegt.

Ich habe mal nur ``sum(1 for x in xrange(100000))`` gegen ``len([x for x in xrange(100000)])`` getestet (1000 Durchläufe), die Variante mit `len()` ist tatsächlich schneller. Wobei das natürlich stark vom verfügbaren Speicher abhängt.
"Der Dumme erwartet viel. Der Denkende sagt wenig." ("Herr Keuner" -- Bertolt Brecht)
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Ups, stimmt.
Habe jetzt nach dem Aufruf der SwapSort-Funktion einfach ein shuffle in die Schleife eingefügt und da liegt len() mit 16 Sekunden eine Sekunde vor sum().
Aber ist ja auch egal, ich find sum() immer noch cooler :p

Edit: Macht das überhaupt einen Unterschied, ob man jetzt eine sortierte Liste oder eine geshuffelte Liste nimmt? Es geht doch nur um das sum bzw len. Aber anscheinend verhalten die sich anders bei sortierten und unsortierten Listen, sonst wär len ja nicht einmal langsamer und dann plötzlich schneller.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sortierverhalten haben oftmals ganz verschiedene Komplexitätsstufen. Es gibt Algorithmen bei denen das sortieren einer bereits sortierten Liste O(n) ist im Regelfall jedoch O(n²).
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Was ist nicht verstehe ist die Annahme, dass bei meinem Test die Liste beim zweiten mal bereits sortiert sei... Wenn ich zehn mal aus einem Tuple ein Array raushole und dieses sortiere, ändert dies doch nichts am Original-Tuple?!
Antworten