Schnellster Weg eine Liste zufällig zu sortieren?

[Christian H]

Über wie viel Millionen Einträge reden wir eigentlich?

Gruß Christian

[Drago]

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(n),Element(Random(#Max))
Next

; ausgabe
For n = 0 To #Max
  PrintN( Str(Element(n)))
Next



PrintN("Press any key to exit"): Repeat: Until Inkey() <> ""

PS: Das einzige was hier vorkommen kann, das n = Random(#Max) ist. Dieses müsste man dann etwas anders machen....

[SebastianJu2]

@Christian

Es sollen Textdateien sein fürs Erste. Zeilenweise sortiert bzw randomisiert in dem Fall. Das sollen später auch mal sehr viele Zeilen sein können bzw möchte Purebasics Schnelligkeit an dem Punkt ausnutzen.

@Drago

Im Prinzip ist das die selbe Funktion wie Nic geschrieben hat. Nur hat er das Random schon vorher abgefragt.
Und bei der Lösung glaube ich dass es nicht ganz zufällig ist weil zum Ende hin sich die dort vorher befindlichen Zahlen oder Buchstaben häufen sollten.

Ist vielleicht albern sich daran zu stören aber...

[NicTheQuick]

Da ich keine Lust habe meine Theorie zu beweisen, habe ich das mal mit einem simplen Test gemacht.
Es wird eine Matrix erstellt, die angibt, wie häufig der Wert i an Position j nach dem Randomisieren vorkommt.
Das sieht bei meiner Variante recht gleichmäßig aus, muss ich sagen.

Code: Alles auswählen

Define count.i = 20
Dim arr.i(count)

Define i.i, j.i, k.i

;Wie oft steht an Position i die Zahl j
Dim h.i(count, count)

For k = 1 To 100000

	;Array füllen
	For i = 0 To count - 1
		arr(i) = i
	Next
	
; 	;Array mischen
 	For i = count - 1 To 0 Step -1
 		Swap arr(i), arr(Random(i))
 	Next

; 	For i = 0 To count - 1
;  		Swap arr(Random(count - 1)), arr(Random(count - 1))
;  	Next
	
	;Array ausgeben
	For i = 0 To count - 1
		;Debug arr(i)
		h(i, arr(i)) + 1
	Next

Next

For i = 0 To count - 1
	s.s = ""
	For j = 0 To count - 1
		s + RSet(Str(h(i, j)), 5, "0") + " | "
	Next
	Debug s
Next

[SebastianJu2]

Also... ich habe jetzt mal beide Wege probiert.

Normal werden immer Listen genutzt um die Zeilen im Programm zu speichern.
Bei 10 Durchläufen mit einer Textdatei von 213.141 Zeilen (URLs) dauert es durchschnittlich...

Wenn die Reihenfolge nicht verändert wird:

Speedtest-Result (10 Loops):
Read: 299 ms on average
Sort: 0 ms on average
Write: 115 ms on average
All done in: 423 ms on average

Wenn aufsteigend oder absteigend sortiert wird:

Speedtest-Result (10 Loops):
Read: 336 ms on average
Sort: 212 ms on average
Write: 162 ms on average
All done in: 717 ms on average

Wenn man aus einer Liste zufällig Werte entnimmt und in eine neue Liste einfügt und dann den alten Listeneintrag löscht:

Diese Version ist bei großen Dateien sehr langsam stelle ich gerade fest. Das liegt meiner Meinung nach an SelectElement() dass ja immer die gesamte Liste durchgehen muss bis es das entsprechende Teil gefunden hat. Ich könnte noch mal testen ob es schneller geht wenn die Listenelemente in einem Pointerarray vorliegen...

Hier erstmal das Ergebnis (Randomize):

Speedtest-Result (10 Loops):
Read: 319 ms on average
Sort: 16693 ms on average
Write: 154 ms on average
All done in: 17170 ms on average

Also vermutlich wirklich zufällig ohne Muster aber auf die Art langsam. Mein Code:

Code: Alles auswählen

          If SortStyle = 3
            NewList ListCopy$()
            CopyList(SourceFileContentList$(),ListCopy$())
            ClearList(SourceFileContentList$())
            For x.l = ListSize(ListCopy$())-1 To 0 Step -1
              AddElement(SourceFileContentList$())
              SelectElement(ListCopy$(),Random(x))
              SourceFileContentList$() = ListCopy$()
              DeleteElement(ListCopy$())
            Next
          EndIf

Und dann die Version von Nic und Drago (Shuffling). Hier wurde ein Array genutzt, keine Liste.:

Speedtest-Result (10 Loops):
Read: 418 ms on average
Sort: 35 ms on average
Write: 154 ms on average
All done in: 611 ms on average

Also sehr viel schneller. Sogar schneller als das SortList(). Liegt vermutlich daran dass hier keine Strings verglichen werden müssen im Vergleich zu SortList(). Allerdings ist es beim Read langsam da ich erstmal nur für jede neue Zeile ein Redim gemacht habe. Ich werde das redim nur für alle 1000 Zeilen versuchen und es wird vielleicht schneller gehen.

Code: Alles auswählen

          If SortStyle = 2
            SizeSourceFileContentList = ArraySize(SourceFileContentArray$())
            For x.l = 0 To SizeSourceFileContentList-1
              rand.l = Random(SizeSourceFileContentList-1)
              Swap SourceFileContentArray$(x),SourceFileContentArray$(rand)
            Next
          EndIf

Frage: Wie leere ich am Besten eine Variable die vom Typ Struktur ist? Ich habe es jetzt so gemacht:

Code: Alles auswählen

AllStat.TimerLog = empty.TimerLog

Wobei empty einfach keinen Wert hat bzw nicht benutzt wird. Ist das der beste Weg?

Ich habe jetzt noch für das Shuffling ein Ergebnis wenn ich das Redim nur alle 1000 Zeilen anwende. Kein großer Unterschied aber ein kleiner:

Speedtest-Result (10 Loops):
Read: 390 ms on average
Sort: 34 ms on average
Write: 155 ms on average
All done in: 583 ms on average

Ich frage mich ob ich nicht doch zu Christians Version wechseln sollte weil das eher einem Mischen entspricht. Es besteht zwar die Chance dass einzelne Elemente gar nicht verschoben werden aber theoretisch könnte man auch einige Loops machen und hätte den ganzen Bereich mehrmals abgedeckt. Oder auch noch zusätzlich die Methode von Nic und Drago um sicherzustellen dass jeder Punkt mindestens einmal verschoben wurde.

Ansonsten... das mit dem Pointerarray dass jeweils auf die Listenelemente zeigt und wegen seinem Index schneller angesprochen werden könnte wird wohl doch nicht funktionieren da man ja nur aus Listen einzelne Bestandteile herauslöschen kann in PB. Damit fällt mir nicht ein wie ich einen Geschwindigkeitsvorteil erreichen könnte.

@Nic

Ich glaube dein Beispiel verstehe ich heute nicht mehr...

[freak]

> Da ich keine Lust habe meine Theorie zu beweisen, habe ich das mal mit einem simplen Test gemacht.

Man bist du faul! Dabei ist der Beweis doch kürzer als der Code:

In der Schleife gilt:
- Alle Elemente > i sind bereits in zufälliger Reihenfolge (Am Anfang ist das klar, weil 0 Elemente auch "zufällig angeordnet" sind)
- Dann wird ein zufälliges der noch ungenutzten Elemente <= i an Stelle i gesetzt
- Damit hat man alle Elemente >= i in zufälliger Reihenfolge

Bei i=0 ist dann alles zufällig.

Was das Thema Listen angeht:
Wenn man eine zufällige Komponente haben will ist rein sequentieller Zugriff nicht mehr möglich, weil man ja das zufällig gewählte Element irgendwie erreichen muss. Also kommt man um ein SelectElement() (oder äquivalenten Code) auch nicht herrum.

@SebastianJu2:
Deine Variante mit 2 Listen ist nicht besonders effizient: Jedes Element wird 2x kopiert, und 2x gelöscht (je einmal bei alt->neu und bei neu->alt). Wenn deine Strings lang sind ist auch das ein ziemlicher Zeitfaktor. Besser ist es einen Code wie den von Nic auf Listen anzuwenden mit SwapElements() zum Vertauschen. Damit werden nur Pointer geändert und nichts wird kopiert.

Sowas zum Beispiel:

Code: Alles auswählen

Define count = 10
NewList a()

For i = 0 To count-1
  AddElement(a())
  a() = i+1
Next i

If FirstElement(a())
  While NextElement(a()) ; Schleife geht mit 2. Element los
    *a = @a()
    SelectElement(a(), Random(ListIndex(a())))
    *b = @a()
    
    If *a <> *b
      SwapElements(a(), *a, *b)
      ChangeCurrentElement(a(), *b) ; neues Ende des bearbeiteten Teils
    EndIf
  Wend
EndIf


ForEach a()
  Debug a()
Next a()

Gleiches Prinzip wie bei Nic, nur andersrum: Es wird jeweils das nächste Element zufällig in den Bereich der schon randomisierten Elemente eingefügt.

[SebastianJu2]

@Nic

Ich glaub heute kann ich verstehen was du gebaut hast. Du zählst die Häufigkeit der Zahlen von 0 bis 19 (rechts nach links) an der Arrayposition 0-19 (vertikal).
Sieht ziemlich gleichmäßig aus.
Ich hab dann noch mal deinen Code etwas umgebaut weil ich ja glaube dass, wenn man von hinten nach vorn das Array swaped, am Anfang des Arrays wo die kleinen Zahlen gespeichert waren am Ende sich die kleinen Zahlen immer noch häufen sollten. Eigentlich dürfte dein Code aber auch genau das selbe ausdrücken.
Ich hab einfach die Zahlen im Array summiert. Ergebnis ist das selbe wie bei dir.

Code: Alles auswählen

Define count.i = 20
Dim arr.i(count)

Define i.i, j.i, k.i

; Summiert die Zahlen verschiedener Versuche einfach in dieses Array
Dim h.i(count)

For k = 1 To 100000

   ;Array füllen
   For i = 0 To count - 1
      arr(i) = i
   Next
   
;    ;Array mischen
   For i = count - 1 To 0 Step -1
      Swap arr(i), arr(Random(i))
   Next

   For i = 0 To count - 1
      ;Debug arr(i)
      h(i) + arr(i)
   Next
Next

   ;Array ausgeben
For i = 0 To count - 1
   s.s = ""
   s + RSet(Str(h(i)), 10, "0") + " | "
   Debug s
Next

Sieht gleichmäßig aus. Keine Häufung von gleichen Zahlen wie ich dachte.

@freak

Mein Gedanke war dass, wenn man ein Array hat mit den Zahlen 0-19 in Reihenfolge und dieses dann von hinten nach vorn durchswaped, dass die kleineren Zahlen am Anfang auch weiterhin kleine Zahlen bleiben.
Denn wenn man hinten anfängt zu tauschen ist die Tauschmasse mit der man tauscht 19 Elemente groß. Die Chance dass ein Element, also zB die 5 gewählt wird ist gering. Wenn das weiter voran geht dann sind nur noch 5 Elemente zum Tausch da. Die Chance steigt zB die 3 zu tauschen.
Zu dem Zeitpunkt sind natürlich auch schon dort eingetauschte Elemente vorhanden. Nur dachte ich dass es tendenziell kleinere Zahlen sein müssten da am Anfang des swappens aufgrund der größeren Anzahl Tauschobjekte weniger Tausche mit den vorderen elementen stattfinden als wenn das swappen schon fortgeschritten ist. Das heißt am Anfang des Arrays müssten erstmal mehr kleine Zahlen sein. Wenn man dann aber schon bei Position 5 angekommen ist im Array tauscht man nur noch die Zahlen die dort sind und das wären tendenziell kleine Zahlen. Theoretisch müssten am Ende des Arrays auch mehr größere Zahlen sein da man beim Tauschen nach vorn ins Array eine größere Chance hat mit einer großen Zahl zu tauschen wie wenn man zB schon bei der 5 im Array angekommen ist.
So dachte ich. Scheint ja irgendein Denkfehler drin zu sein.

Möglicherweise ist der Denkfehler dass die Zahlen die von hinten im array nach vorn vertauscht werden ja beim Durchgang durch das Array noch einmal getauscht werden. Und je weiter es nach vorn geht umso größer wird die Chance für die nun kleinere Anzahl vorderer Zahlen getauscht zu werden.
Ach ich weiß auch nicht... vielleicht gibt es ein Muster aber es dürfte zumindest geringer sein als ich angenommen habe wenn es existiert.

Bei dem Code von dir wird einmal ein SelectElement() benutzt pro Tausch. Ist das nicht ein Nachteil gegenüber Arrays die einen Index haben? Ich glaube die Funktion ist mit ein Grund wieso meine Random-Funktion so langsam war da sie laut Hilfe durch alle Elemente durchlaufen muss um das entsprechende zu finden. Könnte man das dadurch umgehen indem man, während man das Array von 0 bis 9 füllt gleichzeitig ein Pointerarray füllt welches auf die jeweiligen Listenelemente verweist?
...
Ich hab es gleich mal probiert und ich denke es geht und funktioniert. Bei count = 100.000 und mit auskommentierter Debug-Schleife braucht der jetzige Code 50124ms. (Musste 100.000 sein damit der 2. Code überhaupt eine Zeit anzeigt... ) Der Code mit Pointerarray braucht 78ms. Vermutlich könnte man noch ein wenig schneller sein wenn man redim nur alle 1000 Einträge oder so ausführt. Und ich glaube die Reihenfolge der Elemente müsste auch korrekt gemischt sein oder hab ich irgendwas übersehen? Hier der Code:

Code: Alles auswählen

Define count = 100000
NewList a()

StartTime.l = ElapsedMilliseconds()
Dim *pointerarray(0)
For i = 0 To count-1
  ReDim *pointerarray(i)
  *pointerarray(i) = AddElement(a())
  a() = i+1
Next i

For x.l = count - 1 To 1 Step -1
  SwapElements(a(), *pointerarray(x), *pointerarray(Random(x-1)))
Next

; ForEach a()
;   Debug a()
; Next a()
Debug Str(ElapsedMilliseconds() - StartTime) + "ms"

PS: Wie setzt man denn jetzt eine Variable die eine Struktur mit Daten enthält am Besten zurück? Ich habe es mit einer Phantasievariablen vom selben Typ gemacht die dann natürlich auch keine Inhalte hat aber ist das der beste Weg? Die muss ja auch erstmal angelegt werden. Gibt es nicht sowas wie unset() oder so?

EDIT: Pointerzuweisung an addelement gehängt.

[freak]

Denn wenn man hinten anfängt zu tauschen ist die Tauschmasse mit der man tauscht 19 Elemente groß. Die Chance dass ein Element, also zB die 5 gewählt wird ist gering. Wenn das weiter voran geht dann sind nur noch 5 Elemente zum Tausch da. Die Chance steigt zB die 3 zu tauschen.

Da liegt der Denkfehler. Egal wie viele Elemente noch da sind, die Wahrscheinlichkeit ein spezielles davon zu nehmen ist für alle noch vorhandenen Elemente gleich. Die Chance steigt zwar die 3 zu tauschen (wenn sie noch nicht gewählt wurde), aber genauso steigt auch die Chance für die 19 falls sie noch vorhanden ist.

Das ist das gleiche Prinzip wie wenn du alles in einen Topf tust und nach und nach die Elemente blind herrausziehst. Die Tatsache, das Elemente die noch nicht ausgewählt wurden evtl. ein paar mal umher geswapped werden ist analog dazu das du den Topf zwischendrin nochmal schüttelst. Das ändert an der Verteilung nichts.

Falls es eine art Struktur gibt dann liegt das daran, das Random() nur ein Pseudozufallszahlengenerator ist der Zahlen mit einem Algorithmus berechnet und nicht wirklich "würfelt".

[SebastianJu2]

@freak

Da liegt der Denkfehler. Egal wie viele Elemente noch da sind, die Wahrscheinlichkeit ein spezielles davon zu nehmen ist für alle noch vorhandenen Elemente gleich. Die Chance steigt zwar die 3 zu tauschen (wenn sie noch nicht gewählt wurde), aber genauso steigt auch die Chance für die 19 falls sie noch vorhanden ist.

Aber das mit der gleichen Chance würde das nicht nur gelten wenn man das Array durchgeht und dabei das jeweilige Element mit allen anderen Arrayelementen tauschen könnte? Also nach nach hinten? Ansonsten... wenn man zB von Position 19 zu 0 vorgeht und das jeweilige Element immer nur nach unten tauschen läßt, also an Position 12 kann die Position 12 nur mit Position 0-11 getauscht werden dann sollte das Topf-Prinzip doch nicht mehr gelten oder?

Im Moment glaube ich dass die Methode bei der man das Array durchgeht und dann das jeweilige Element nach vorn und nach hinten im Array tauschen kann die schnellste und zufälligste Methode sein sollte bzw auch absolut dem Topfprinzip entsprechen sollte und außerdem jedes Element mindestens einmal irgendwo auf der gesamten Skala verschoben wird.

Ich glaube mittlerweile dass ich einfach falsch vermutet habe. Offenbar sortieren diese Vorgehensweisen wirklich zufällig. Andernfalls hätte es sich ja beim Testen zeigen müssen dass es anders ist. Na was solls...

Hier noch mal eine Frage: Wie setzt man denn jetzt eine Variable die eine Struktur mit Daten enthält am Besten zurück? Ich habe es mit einer Phantasievariablen vom selben Typ gemacht die dann natürlich auch keine Inhalte hat und dieser der alten Variable zugewiesen aber ist das der beste Weg? Die muss ja auch erstmal angelegt werden. Gibt es nicht sowas wie unset() oder so?

[freak]

> wenn man zB von Position 19 zu 0 vorgeht und das jeweilige Element immer nur nach unten tauschen läßt, also an Position 12 kann die Position 12 nur mit Position 0-11 getauscht werden dann sollte das Topf-Prinzip doch nicht mehr gelten oder?

Die Position 12 ist ja auch Kandidat als Tauschpartner wenn die 19 getauscht wird. Sie kann also genauso gut auch nach oben wandern.

Zu deiner 2. Frage: schau dir ClearStructure() an.