Swap Sort
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
Humm, stimmt.
Ja das ist mir so weit auch klar.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²).
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
@Nocta: Schau Dir einfach mal die Zeiten an. Der Algorithmus braucht deutlich weniger Zeit bei schon sortierten Listen.
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).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.
Das macht sich aber dann nur bei sehr großen Listen bemerkbar weil die sum() Variante mehr Arbeit pro Schritt machen muss.
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.BlackJack hat geschrieben:@Nocta: Schau Dir einfach mal die Zeiten an. Der Algorithmus braucht deutlich weniger Zeit bei schon sortierten Listen.