Seite 1 von 3
Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 19:25
von SebastianJu2
Was wäre denn der schnellste Weg eine Liste zufällig zu sortieren. Also keine wirkliche Sortierung sondern einfach alle Elemente zufällig anordnen.
Ich dachte daran die Länge der Liste herauszufinden und dann eine Schleife zu durchlaufen die so oft x durchzählt bis es bei 0 ist. Und in der Schleife dann mit selectitem() und random(x) ein element auswählen und in eine neue Liste speichern. Dann das alte Listenelement löschen.
Allerdings soll selectitem() recht langsam sein weil listen keinen index haben und stets von vorn nach hinten durchgehen müssen bis sie das richtige Element finden.
Wäre ein Array besser? Das hat ja einen Index und es dürfte schneller zu finden sein. Allerdings dürfte es schwierig sein da ein element rauszulöschen bzw es wäre vermutlich noch langsamer. Und die bereits entnommenen Elementeids zu speichern dürfte ebenso Ressourcen verbrauchen.
Gibt es einen effektiven Weg?
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 19:42
von NicTheQuick
Um ein Array zu mischen, würde ich folgendes vorschlagen.
Code: Alles auswählen
Define count.i = 10
Dim arr.i(count)
Define i.i, j.i
;Array füllen
For i = 0 To count - 1
arr(i) = i + 1
Next
;Array mischen
For i = count - 1 To 0 Step -1
j = Random(i)
Swap arr(i), arr(j)
Next
;Array ausgeben
For i = 0 To count - 1
Debug arr(i)
Next
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 19:48
von Christian H
NicTheQuick hat geschrieben:Um ein Array zu mischen, würde ich folgendes vorschlagen. ..
Du warst schneller. Aber erstaunlich wie sich dein und mein Vorschlag gleichen.
Code: Alles auswählen
#Max = 50
Define n
Dim Element(#Max)
For n = 0 To #max
Element(n) = n
Next
OpenConsole()
For n = 0 To #max
Swap Element(Random(#max)),Element(Random(#max))
Next
; ausgabe
For n = 0 To #max
PrintN( Str(Element(n)))
Next
PrintN("Press any key to exit"): Repeat: Until Inkey() <> ""
Gruß
Christian
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 20:13
von SebastianJu2
Swap... daran hatte ich nicht gedacht. Müsste theoretisch auch für Listen funktionieren solange man während des Listespeicherns gleichzeitig ein Pointerarray anlegt um jedes Listenelement anzusprechen. Ob das schneller wäre weiß ich nicht.
Einen kleinen Nachteil hat das Swap im gleichen Array oder Liste aber. Es kann sein dass Elemente doppelt bearbeitet werden. Nicht schlimm aber ein gewisser Prozentsatz an Mehrarbeit wäre es wohl für die CPU. 1/4-1/2 mehr? Aber wenn das schneller wäre als eine neue Liste dann wäre das wohl nicht schlimm.
Ist swap schneller als einen Wert von einem Array in ein anderes zu kopieren? Vermutlich ja oder? Weil nicht nur der Index getauscht werden muss. Vielleicht sollte ich das einfach mal testen...
(Hab ja jetzt einen Speedtest mit dem ich x Durchläufe laufen lassen kann und der Durchschnitt am Ende angezeigt wird...)
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 20:19
von NicTheQuick
@Christian H:
Bei mir wird aber sicher gestellt, dass jedes Element nur genau einmal angesprochen wird. Bei dir können zwei vertauscht und wieder zurück getauscht werden.
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 20:27
von Christian H
Was nach den regeln des Zufalls aber auch ok ist. Eine gemischte Liste kann ja auch durch Mischen den Ausgangszustand erreichen.
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 20:33
von SebastianJu2
Stimmt... bei Nic würde es auch Elemente geben die gar nicht getauscht würden weil sie nie durch Zufall gewählt wurden. Bei einer vorherigen Reihenfolge könnte man dann die alte Reihenfolge noch erahnen können vielleicht.
Bei dir Christian kann nicht zurückgetauscht werden wie ich vorher dachte. Allerdings zum Ende hin wird in einer immer kleineren Gruppe getauscht. Wenn es sich um Wörter handelt würden dann würde vermutlich am Anfang des Arrays sich die Wörter mit A häufen. Oder?
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 20:40
von NicTheQuick
@SebastianJu2:
Ich glaube du vertauschst gerade unsere Namen.
Ja, am Ende wird bei mir in einer immer kleinen Gruppe getauscht. Aber trotzdem ist die Wahrscheinlichkeit für jedes einzelne Element immer gleich. Es können ja auch am Anfang schon Elemente von vorne nach ganz hinten getauscht werden.
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 20:49
von SebastianJu2
Sorry...
Ja auch am Anfang können Elemente von vorn weggetauscht werden aber die Wahrscheinlichkeit dort etwas herauszupicken ist ja erst gering und wird dann größer. Das müsste eigentlich bedeuten dass eine Struktur zurückbleibt die A's am Anfang häuft und B's dahinter aber schon seltener vorkommend und dann die C's. Eigentlich schon oder?
Vielleicht wenn man die Liste dann noch mal von der anderen Seite durchswapt? Oder würde dann in der Mitte eine, wenn auch viel kleinere, Struktur zurückbleiben?
Ich weiß nicht... ich denke wirklich sicher könnte man nur sortieren wenn das in ein neues Array oder Liste geht. Das alte Array durchgehen und zufällig ins neue gleich große Array einbauen. Nur hat man dann das Problem dass man erst prüfen muss ob an der Stelle schon was steht.
Ist ja schwieriger als ich dachte...
Re: Schnellster Weg eine Liste zufällig zu sortieren?
Verfasst: 23.02.2011 20:57
von SebastianJu2
Oder andersherum. Per Zufall aus alter Liste auswählen und als 1. Element einer neuen Liste speichern. Altes element löschen. Aus alter Liste neues Element auswählen (länge-1) und als 2. Element in 2. Liste einfügen. Das löschen eines Elements in einer Liste soll ja schnell gehen. Nicht schnell gehen wird aber die Suche mit selectitem(). Beim array wird wieder das löschen des Elements zum geschwindigkeitsproblem...