robv
New Member
Posts: 10
|
Post by robv on Jul 3, 2024 20:12:52 GMT
p = 15
dim k$(p)
for a = 1 to p
k$(a) = str$(a)
next a
for a = 1 to (p * p)
i = int(rnd(1) * p) + 1
temp$ = k$(i)
j = int(rnd(1) * p) + 1
k$(i) = k$(j)
k$(j) = temp$
next a
for a = 1 to p
print k$(a)
next a
wait
|
|
|
|
Post by Marco Kurvers on Jul 3, 2024 22:03:22 GMT
Bedankt Rob. Dit is inderdaad het trucje van Gordon.
Als ik het goed begrijp, hoef ik eigenlijk niet te controleren of de twee waarden ongelijk zijn en zal er met gelijke waarden gewoon niets gebeuren.
|
|
keesb
New Member
Posts: 22
|
Post by keesb on Jul 5, 2024 22:05:36 GMT
Inderdaad Marco, ik realiseerde me later pas dat iedere keer in de for-loop checken of de indexen i en j ongelijk zijn meer tijd kost dan af en toe een onnodige swap maken als i en j gelijk zijn. In het voorbeeld van Gordon is die kans 1 op p^2 en ik wou wel eens weten hoeveel dat nu eigenlijk scheelt, zie de file in de bijlage waarin overigens 200x200 maal geswapt wordt. Niet checken levert dus tussen de 11 en 24 % snelheidswinst op, afhankelijk van een aantal voor de hand liggende factoren. Of je integers, doubles of strings van verschillende lengte swapt maakt relatief weinig uit. Overigens is de nauwkeurigheid van de gebruikte tijdmetingen in milliseconden waarschijnlijk ook niet erg hoog, maar het geeft zo toch wel een aardig beeld.
|
|
keesb
New Member
Posts: 22
|
Post by keesb on Jul 5, 2024 22:34:45 GMT
Blijft over de vraag hoe vaak je nu eigenlijk moet swappen om de boel weer redelijk random te maken. Daar zijn verschillende test voor in omloop (zie bijvoorbeeld en.wikipedia.org/wiki/Randomness_test) maar die zijn niet echt simpel. Het programma in de bijlage is vrij simpel van opzet en lijkt te suggereren dat 4 x MaxGetal een goede keuze is ("cls" uitvinken en een aantal malen op "New" drukken).
|
|
|
|
Post by frizhd on Jul 6, 2024 15:33:02 GMT
' Genereren van 15 verschillende worpen
W=15 'aantal worpen, pas W naar believen aan
DIM W(W)
FOR N= 1 to W : W(N)=N : NEXT N '
'Knuthshuffle, zie Internet en uitleg filmpjes
FOR X = W TO 2 STEP -1
J = INT ( RND (1) * X + 1)
T = W(X) :W(X) = W(J) : W(J) = T 'swap
NEXT X
' de array W(X) is nu door elkaar geschud, gehutseld
FOR N= 1 to W : PRINT N, W(N) : NEXT N ' de geschudde waarden
SORT W(), 1, W
PRINT "weer keurig op volgorde"
FOR N= 1 to W : PRINT N, W(N) : NEXT N 'weer keurig op een rijtje
END
|
|
keesb
New Member
Posts: 22
|
Post by keesb on Jul 7, 2024 21:57:56 GMT
Mi scusi Friz, je hebt helemaal gelijk, Knuth is de absolute winnaar in de swap contest. Ik was zo gefixeerd op de code in "het trucje van Gordon" en de andere zaken in bovenstaande posts dat ik de "Knuth shuffle" bijna vergeten was. Als boetedoening nu ook Knuth in het laatste programma meegenomen, je ziet dan 4 verschillende uitkomsten van het algoritme volgens Knuth (eigenlijk Richard Durstenfeld), zie bijlage. Bill Gates schijnt over Donald Knuth het volgende gezegd te hebben : "If you think you’re a really good programmer, read The Art of Computer Programming. You should definitely send me a résumé if you can read the whole thing." Een andere beroemde uitspraak van een wiskundige is: "Random Number Generation is too important to be Left to Chance" - Robert R. Coveyou
|
|
|
|
Post by frizhd on Jul 8, 2024 9:53:15 GMT
Dat laatste geldt ook voor een eerlijk potje BackGamon. Daarvoor heb je zuivere dobbelstenen nodig. Wat dat zijn?
Huisvlijt volgt separaat. Vertrouwen op een geschudde, gehuffelde array is niet voldoende voor het genereren van de waarden.
Grazie Kees
|
|
|
|
Post by Marco Kurvers on Jul 9, 2024 20:03:58 GMT
Hoi Friz,
Weet jij waarom Knuth een lus laat lopen van W tot 2, maar niet tot 1?
Alsof er iets is met 1?
Ook verwonderlijk dat je maar één RND(1) nodig hebt.
|
|
|
|
Post by frizhd on Jul 10, 2024 8:45:05 GMT
Iets met zichzelf verwisselen, heeft dat zin?
RND(1)
Zie handleiding LB: Deze functie retourneert een willekeurig getal tussen 0 en 1. De getal parameter wordt meestal ingesteld op 1, maar de waarde is onbelangrijk omdat deze niet daadwerkelijk door de functie wordt gebruikt. De functie retourneert altijd een willekeurig getal tussen 0 en 1.
|
|
|
|
Post by frizhd on Jul 10, 2024 8:52:38 GMT
attentie : ook dit keer maakt de editor een wijziging
nulpuntgetal is niet het woord dat ik heb geschreven. Wel willekeurig getal. W i l l e k e u r i g.
Of doe ik iets fout? Iets met de taal instelling?
Het is waar : ik hou van gewoon Nederlands.
|
|
|
|
Post by Marco Kurvers on Jul 19, 2024 13:38:44 GMT
Ja Friz, Nederlands is beter.
Het is vreemd dat het bij jou steeds anders uitkomt. Ik heb er geen last van.
Probeer ook code apart van de tekst hier te plakken of te typen, zoals:
PRINT "Hallo allemaal!"
In plaats van:
PRINT "Hallo allemaal!"
Grazie!
|
|
