Swap Sort

[Nocta]

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

[Trundle]

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.

[Nocta]

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]

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²).

[Dauerbaustelle]

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?!

[Trundle]

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.

[Dauerbaustelle]

Humm, stimmt.

[Nocta]

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]

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

[audax]

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]

@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.