Swap Sort

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

Beitragvon Nocta » Sonntag 15. März 2009, 23:18

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

Beitragvon Trundle » Sonntag 15. März 2009, 23:36

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

Beitragvon Nocta » Sonntag 15. März 2009, 23:45

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.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Montag 16. März 2009, 11:42

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 Modvoice
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Beitragvon Dauerbaustelle » Montag 16. März 2009, 13:37

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?!
Benutzeravatar
Trundle
User
Beiträge: 591
Registriert: Dienstag 3. Juli 2007, 16:45

Beitragvon Trundle » Montag 16. März 2009, 13:53

Meinst du mit Array eine Liste? Und du veränderst ja nicht das Tupel, das ja eh unveränderbar wäre, sondern die Liste, also ein Element des Tupels. Und Listen sind nun einmal veränderbar. Du änderst also die Liste, und holst beim nächsten Durchlauf das Element zwar neu aus dem Tupel heraus, aber letztlich ist es dasselbe Element, die veränderte Liste.
"Der Dumme erwartet viel. Der Denkende sagt wenig." ("Herr Keuner" -- Bertolt Brecht)
Dauerbaustelle
User
Beiträge: 996
Registriert: Mittwoch 9. Januar 2008, 13:48

Beitragvon Dauerbaustelle » Montag 16. März 2009, 13:56

Humm, stimmt.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Beitragvon Nocta » Montag 16. März 2009, 14:13

Leonidas hat geschrieben: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²).

Ja das ist mir so weit auch klar.
Aber der Algorithmus ist ja der selbe, also sollte es doch egal sein, WAS die beiden Listen da sortieren, sondern nur WIE (sum oder len). Und da spielt's doch theoretisch keine Rolle, ob man jetzt sortierte oder unsortierte Listen hat, oder?
BlackJack

Beitragvon BlackJack » Dienstag 17. März 2009, 07:44

@Nocta: Schau Dir einfach mal die Zeiten an. Der Algorithmus braucht deutlich weniger Zeit bei schon sortierten Listen.
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Dienstag 17. März 2009, 08:46

Trundle hat geschrieben: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.


Die len() Variante hat nen Speicherverbrauch von O(n) und ne Laufzeit von O(n) für den Aufbau der Liste und O(1) für das eigentliche len(), die sum() Variante hingegen nen Speicherverbauch von O(1) und ne Laufzeit von O(n).
Das macht sich aber dann nur bei sehr großen Listen bemerkbar weil die sum() Variante mehr Arbeit pro Schritt machen muss.
Nocta
User
Beiträge: 290
Registriert: Freitag 22. Juni 2007, 14:13

Beitragvon Nocta » Donnerstag 19. März 2009, 13:26

BlackJack hat geschrieben:@Nocta: Schau Dir einfach mal die Zeiten an. Der Algorithmus braucht deutlich weniger Zeit bei schon sortierten Listen.

Was ich meinte war, dass der Algorithmus doch der Selbe ist, sich also nur in len oder sum unterscheidet. Deshalb dachte ich, es ist im Prinzip ohnehin egal, weil wir im Endeffekt nicht den Algorithmus sondern len() oder sum() vergleichen wollten. Im Prinzip hätte es gereicht, einfach len und sum ohne den Swap Sort Algorithmus zu testen.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder