Random getallen (integers) uit rij kiezen

[Digibyte]

Hoe kan ik het best het volgende programmeren:
Ik moet een willekeurig aantal getallen kiezen (vb. 10) uit een rij getallen
die optelt van 0 tot x. (vb. 0, 1, 2, 3, 4, 5, 6, ..., 99)

Ik heb dit al gevonden om 1 getal eruit te halen:
Randomize
randomValue = Int(100 * Rnd)

Maar nu weet ik niet hoe ik het tweede getal er moet uithalen. Mag dus niet
hetzelfde zijn als het vorige getrokken getal. En de kans om ieder getal te
nemen moet even groot zijn. Ik kan dus niet zeggen dat als het getal al
getrokken is, plus 1 te doen.

Kan iemand me tips geven of me verder helpen? Alvast bedankt!

Greetz ;)
Digibyte

[shortway]

Post by Digibyte
Ik moet een willekeurig aantal getallen kiezen (vb. 10) uit een rij getallen
die optelt van 0 tot x. (vb. 0, 1, 2, 3, 4, 5, 6, ..., 99)
Randomize
randomValue = Int(100 * Rnd)
Maar nu weet ik niet hoe ik het tweede getal er moet uithalen. Mag dus niet
hetzelfde zijn als het vorige getrokken getal. En de kans om ieder getal te
nemen moet even groot zijn. Ik kan dus niet zeggen dat als het getal al
getrokken is, plus 1 te doen.
Kan iemand me tips geven of me verder helpen? Alvast bedankt!
Greetz ;)
Digibyte

De 'gekozen' waarde testen?

óf bijvoorbeeld:

Het laatste getal in de reeks, het 'opengevallen' gaatje gaatje laten in
vullen en dan dezelfde functie voor de overgebleven reeks gebruiken maar nu
tot n en niet tot en met....

Grtz,
Chris

[Digibyte]

Post by Digibyte

Post by Digibyte
Ik moet een willekeurig aantal getallen kiezen (vb. 10) uit een rij

getallen

Post by Digibyte
die optelt van 0 tot x. (vb. 0, 1, 2, 3, 4, 5, 6, ..., 99)
Randomize
randomValue = Int(100 * Rnd)
Maar nu weet ik niet hoe ik het tweede getal er moet uithalen. Mag dus

niet

Post by Digibyte
hetzelfde zijn als het vorige getrokken getal. En de kans om ieder

getal

Post by Digibyte
te

Post by Digibyte
nemen moet even groot zijn. Ik kan dus niet zeggen dat als het getal al
getrokken is, plus 1 te doen.
Kan iemand me tips geven of me verder helpen? Alvast bedankt!
Greetz ;)
Digibyte

De 'gekozen' waarde testen?
Het laatste getal in de reeks, het 'opengevallen' gaatje gaatje laten in
vullen en dan dezelfde functie voor de overgebleven reeks gebruiken maar nu
tot n en niet tot en met....
Grtz,
Chris

Maar ik kan met mijn eerder opgegeven code enkel random getallen kiezen uit
rijen waar geen 'gaten' in zitten.
Wat ik wel zou kunnen doen (om het tweede getal te 'trekken') is het
volgende:
randomValue = Int(99 * Rnd)
If randomValue <= getalgaatje Then randomValue = randomValue + 1

Maar ik zie niet in hoe ik dit simpel kan programmeren voor met bv. 10
gaatjes te doen.

[Ewoud Dronkert]

Post by Digibyte
Maar nu weet ik niet hoe ik het tweede getal er moet uithalen.
Mag dus niet hetzelfde zijn als het vorige getrokken getal.

Maak een array a van lengte M met alle getallen waar je uit kiest.
Genereer een willekeurige index j in het bereik 0 t/m M-1. Doe iets
met het getal a[j], bijv. bewaren in array b. Vervang a[j] door het
getal uit a met de hoogste index van het bereik, dus door a[M-1].
Verklein nu het bereik met 1 (kies uit index 0 t/m M-2) en herhaal.


#include <stdlib.h>

#define N 10
#define M 100

int a[M], b[N];

int main( void )
{
int i, j, k;

randomize();
for ( i = 0; i < M; ++i ) a[i] = i;

k = M;
for ( i = 0; i < N; ++i )
{
j = rand() % k;
b[i] = a[j];
a[j] = a[k - 1];
--k;
}
return 0;
}

[Ewoud Dronkert]

Post by Ewoud Dronkert
a[j] = a[k - 1];
--k;

Of iets sneller :)

--k;
a[j] = a[k];

Of wat compacter:

a[j] = a[--k];

[Oelewapperke]

Post by Digibyte
Maar nu weet ik niet hoe ik het tweede getal er moet uithalen. Mag dus niet
hetzelfde zijn als het vorige getrokken getal. En de kans om ieder getal te
nemen moet even groot zijn. Ik kan dus niet zeggen dat als het getal al
getrokken is, plus 1 te doen.
Kan iemand me tips geven of me verder helpen? Alvast bedankt!

Algebra tip : dit kan zonder dat je een geschiedenis bijhoud (alle je kan
dat beperken tot 1 getal)

lx = de vorige waarde
neem seed >> max (voor effect ;-p)
( >> = veel groter)

int rand(lx, max, seed) {
neem y priem > max;
int hulp;

while (hulp > max) {
lx = hulp;
hulp = (lx+seed) % y;
}
return hulp;
}

omdat je hier rekent in een eenhedengroep ga je enkel hetzelfde getal
terugkrijgen nadat je alle andere gehad hebben.

Oelewapperke

[Ewoud Dronkert]

Post by Oelewapperke
Algebra tip : dit kan zonder dat je een geschiedenis bijhoud (alle je
kan dat beperken tot 1 getal)

Aja, interessante oefening, maar

Post by Oelewapperke
neem y priem > max;

is veel "duurder" dan een rijtje getallen opslaan :)

[Marcus]

Post by Digibyte
Ik moet een willekeurig aantal getallen kiezen (vb. 10) uit een rij getallen
die optelt van 0 tot x. (vb. 0, 1, 2, 3, 4, 5, 6, ..., 99)
Randomize
randomValue = Int(100 * Rnd)
Maar nu weet ik niet hoe ik het tweede getal er moet uithalen. Mag dus niet
hetzelfde zijn als het vorige getrokken getal. En de kans om ieder getal te
nemen moet even groot zijn. Ik kan dus niet zeggen dat als het getal al
getrokken is, plus 1 te doen.

Je kan een array aanmaken met reeds getrokken nummers. Dan bij elk getal
kijken of het al in dit array staat. Bij een gesorteerd array levert dit
een complexiteit van n*log(m) op waarbij n de x uit jouw voorbeeld is,
en de m het aantal getallen wat je eruit haalt. Alternatief is een array
van booleans bijhouden met gekozen getallen (dus stel je kiest 20 dan
zet je bool[20] op true). Zo kan je veel sneller checken of je een getal
al gehad hebt. De complexiteit is nu n+m.

Mark

[Ewoud Dronkert]

Post by Marcus
Je kan een array aanmaken met reeds getrokken nummers. Dan bij elk getal
kijken of het al in dit array staat. Bij een gesorteerd array levert dit
een complexiteit van n*log(m) op waarbij n de x uit jouw voorbeeld is,
en de m het aantal getallen wat je eruit haalt. Alternatief is een array
van booleans bijhouden met gekozen getallen (dus stel je kiest 20 dan
zet je bool[20] op true). Zo kan je veel sneller checken of je een getal
al gehad hebt. De complexiteit is nu n+m.

Vergeet de orde-berekeningen. Als je toch al een array bijhoudt, dan
hoef je die niet te sorteren en er niet in te zoeken, en hem slechts
eenmaal te doorlopen. Zie de allereerste reply van 'shortway' en mijn
reply met code.

Probeer dit in Visual Basic, standaard exe, in de form code:


Option Explicit
Private c As Long

Private Sub Form_Click()

Dim m As Integer
Dim x As Long, n As Long, i As Long, j As Long, k As Long
Dim a() As Long

m = MousePointer
MousePointer = vbHourglass

x = ScaleWidth
n = x * ScaleHeight
ReDim a(n)
For i = 0 To n - 1
a(i) = i
Next
If c = vbWhite Then c = vbBlack Else c = vbWhite

k = n
For i = 0 To n - 1
j = Int(Rnd * k)
PSet (a(j) Mod x, a(j) \ x), c
k = k - 1
a(j) = a(k)
Next

MousePointer = m

End Sub

Private Sub Form_Load()

Randomize
c = vbWhite

DrawMode = vbCopyPen
DrawStyle = vbSolid
DrawWidth = 1
ScaleMode = vbPixels

End Sub

[P. Puk]

Post by Digibyte
Ik moet een willekeurig aantal getallen kiezen (vb. 10) uit een rij getallen
die optelt van 0 tot x. (vb. 0, 1, 2, 3, 4, 5, 6, ..., 99)
Randomize
randomValue = Int(100 * Rnd)
Maar nu weet ik niet hoe ik het tweede getal er moet uithalen. Mag dus niet
hetzelfde zijn als het vorige getrokken getal. En de kans om ieder getal te
nemen moet even groot zijn. Ik kan dus niet zeggen dat als het getal al
getrokken is, plus 1 te doen.
Kan iemand me tips geven of me verder helpen? Alvast bedankt!
Greetz ;)
Digibyte

In een van mijn programma's heb ik ooit deze randomgenerator gebruikt.
In dit voorbeeld worden 6 willekeurige getallen gekozen tussen 1 en 12. De
getallen komen in de array 'volgorde(x) te staan.


Public Sub RandomGenerator()

Dim x As Long, y As Long, z As Long, tempnum As Long
Dim flag As Integer
Dim i As Integer
Dim zoekstring As String
Dim start As Integer

x = 1 'begingetal
y = 12 'max te kiezen getal
z = 6 'aantal te kiezen getallen

Randomize
Num_list = " " & Int((y - x + 1) * Rnd + x) & ", "

For i = 2 To z
Do
flag = False
Randomize
tempnum = Int((y - x + 1) * Rnd + x)
zoekstring = " " & tempnum & ","
If (InStr(Num_list, zoekstring)) Then
flag = True
End If
Loop Until Not flag
Num_list = Num_list & tempnum & ", "
Next

start = 0
For x = 1 To Len(Num_list)
If Mid$(Num_list, x, 1) = " " Then
Volgorde(start) = Mid$(Num_list, x + 1, 2)
If Right$(Volgorde(start), 1) = "," Then
Volgorde(start) = Mid$(Num_list, x + 1, 1)
End If
start = start + 1
End If
Next x

[Rene]

Post by P. Puk
In een van mijn programma's heb ik ooit deze randomgenerator gebruikt.
In dit voorbeeld worden 6 willekeurige getallen gekozen tussen 1 en 12. De
getallen komen in de array 'volgorde(x) te staan.

Door gebruik te maken van een collection hoef je niet bij te houden wel
nummer getrokken is, code kun je plakken op een nieuwe form met een button
om het te activeren (en heb je gelijk leesbare code):

Option Explicit

Private Sub Command1_Click()
Dim col As New Collection
Dim Results() As Integer
Dim i As Integer

' Initialiseer nummers van 1 t/m 12
InitCollection col, 1, 12

' Trek 6 getallen uit de lijst
Results = GetRandomNumbers(col, 6)

' Toon de 6 getallen
For i = 1 To 6
Debug.Print Results(i) ' Print alle nummer
Next

' Opruimen
Set col = Nothing

End Sub

Private Function GetRandomNumbers(pCollection As Collection, NumbersWanted
As Integer) As Integer()
Dim Results() As Integer
Dim i As Integer
Dim idx As Integer

' Ruimte reserveren voor resultaat
ReDim Results(NumbersWanted)

' Initialiseren van de randomizer
Randomize

For i = 1 To NumbersWanted
idx = (Rnd() * (pCollection.Count - 1)) + 1
Results(i) = pCollection(idx)
pCollection.Remove idx
Next

GetRandomNumbers = Results
Erase Results

End Function

Private Sub InitCollection(pCollection As Collection, LowestNumber As
Integer, HighestNumber As Integer)
Dim i As Integer

Set pCollection = New Collection

For i = LowestNumber To HighestNumber
pCollection.Add i
Next

End Sub

Post by P. Puk
Public Sub RandomGenerator()
Dim x As Long, y As Long, z As Long, tempnum As Long
Dim flag As Integer
Dim i As Integer
Dim zoekstring As String
Dim start As Integer
x = 1 'begingetal
y = 12 'max te kiezen getal
z = 6 'aantal te kiezen getallen
Randomize
Num_list = " " & Int((y - x + 1) * Rnd + x) & ", "
For i = 2 To z
Do
flag = False
Randomize
tempnum = Int((y - x + 1) * Rnd + x)
zoekstring = " " & tempnum & ","
If (InStr(Num_list, zoekstring)) Then
flag = True
End If
Loop Until Not flag
Num_list = Num_list & tempnum & ", "
Next
start = 0
For x = 1 To Len(Num_list)
If Mid$(Num_list, x, 1) = " " Then
Volgorde(start) = Mid$(Num_list, x + 1, 2)
If Right$(Volgorde(start), 1) = "," Then
Volgorde(start) = Mid$(Num_list, x + 1, 1)
End If
start = start + 1
End If
Next x

[Mathijs]

Post by Rene
Door gebruik te maken van een collection hoef je niet bij te houden
wel nummer getrokken is, code kun je plakken op een nieuwe form met

Precies wat ik dacht. Post toch maar mijn Delphi 'oplossing', omdat ik 'm
nu toch al heb :-/

//globals
const MINGETAL=25;
MAXGETAL=40;
var GetallenSet: array of integer;

//initialiseren
procedure Init;
var i: Integer;
begin
Randomize;
SetLength(GetallenSet,MAXGETAL-MINGETAL);
for i:=0 to (MAXGETAL-MINGETAL) do
GetallenSet[i]:=MINGETAL+i;
end;

function UniekRandomGetal: Integer;
var inx: Integer;
begin
inx := Random(Length(GetallenSet)-1);
Result := GetallenSet[inx];
GetallenSet[inx]:=GetallenSet[Length(GetallenSet)-1];
SetLength(GetallenSet,Length(GetallenSet)-1);
end;

//gebruik van functie
procedure TForm1.Button1Click(Sender: TObject);
var i: Integer;
s: string;
begin
Init;
s:=s+IntToStr(UniekRandomGetal);
for i:=0 to 9 do
s:=s+','+IntToStr(UniekRandomGetal);
showMessage(s);
end;

[Rene]

Post by Mathijs
GetallenSet[inx]:=GetallenSet[Length(GetallenSet)-1];
SetLength(GetallenSet,Length(GetallenSet)-1);

Kan dus ook in VB zonder collection, deze kende ik nog niet, nice ;-)

[Ewoud Dronkert]

Post by Mathijs
inx := Random(Length(GetallenSet)-1);
Result := GetallenSet[inx];
GetallenSet[inx]:=GetallenSet[Length(GetallenSet)-1];
SetLength(GetallenSet,Length(GetallenSet)-1);

Yep, dat is dezelfde gatenopvulmethode. Vraag me wel af hoe het zit
met de efficientie van SetLength; ik denk dat je dat soort
geheugenbeheerfuncties zoveel mogelijk moet vermijden in vaak
doorlopen loops (hier dus misschien niet zo erg).

[digibyte]

Dit is precies wat ik nodig had!
Het werkt perfect

Merci!!!
Digibyte

Post by Rene

Post by P. Puk
In een van mijn programma's heb ik ooit deze randomgenerator gebruikt.
In dit voorbeeld worden 6 willekeurige getallen gekozen tussen 1 en 12. De
getallen komen in de array 'volgorde(x) te staan.

Door gebruik te maken van een collection hoef je niet bij te houden wel
nummer getrokken is, code kun je plakken op een nieuwe form met een button
Option Explicit
Private Sub Command1_Click()
Dim col As New Collection
Dim Results() As Integer
Dim i As Integer
' Initialiseer nummers van 1 t/m 12
InitCollection col, 1, 12
' Trek 6 getallen uit de lijst
Results = GetRandomNumbers(col, 6)
' Toon de 6 getallen
For i = 1 To 6
Debug.Print Results(i) ' Print alle nummer
Next
' Opruimen
Set col = Nothing
End Sub
Private Function GetRandomNumbers(pCollection As Collection, NumbersWanted
As Integer) As Integer()
Dim Results() As Integer
Dim i As Integer
Dim idx As Integer
' Ruimte reserveren voor resultaat
ReDim Results(NumbersWanted)
' Initialiseren van de randomizer
Randomize
For i = 1 To NumbersWanted
idx = (Rnd() * (pCollection.Count - 1)) + 1
Results(i) = pCollection(idx)
pCollection.Remove idx
Next
GetRandomNumbers = Results
Erase Results
End Function
Private Sub InitCollection(pCollection As Collection, LowestNumber As
Integer, HighestNumber As Integer)
Dim i As Integer
Set pCollection = New Collection
For i = LowestNumber To HighestNumber
pCollection.Add i
Next
End Sub

Post by P. Puk
Public Sub RandomGenerator()
Dim x As Long, y As Long, z As Long, tempnum As Long
Dim flag As Integer
Dim i As Integer
Dim zoekstring As String
Dim start As Integer
x = 1 'begingetal
y = 12 'max te kiezen getal
z = 6 'aantal te kiezen getallen
Randomize
Num_list = " " & Int((y - x + 1) * Rnd + x) & ", "
For i = 2 To z
Do
flag = False
Randomize
tempnum = Int((y - x + 1) * Rnd + x)
zoekstring = " " & tempnum & ","
If (InStr(Num_list, zoekstring)) Then
flag = True
End If
Loop Until Not flag
Num_list = Num_list & tempnum & ", "
Next
start = 0
For x = 1 To Len(Num_list)
If Mid$(Num_list, x, 1) = " " Then
Volgorde(start) = Mid$(Num_list, x + 1, 2)
If Right$(Volgorde(start), 1) = "," Then
Volgorde(start) = Mid$(Num_list, x + 1, 1)
End If
start = start + 1
End If
Next x

[Hans Stavleu]

Ik bedacht me het volgende. Zet elk getal tot x in een array. Loop de array
van 1 tot en met x door en wissel de inhoud met een random ander element van
de array. Als je daarna bijvoorbeeld tien willekeurige getallen uit de reeks
nodig hebt, neem je gewoon de eerste tien elementen van het array.

hans stavleu

Post by Digibyte
Ik moet een willekeurig aantal getallen kiezen (vb. 10) uit een rij getallen
die optelt van 0 tot x. (vb. 0, 1, 2, 3, 4, 5, 6, ..., 99)
Randomize
randomValue = Int(100 * Rnd)
Maar nu weet ik niet hoe ik het tweede getal er moet uithalen. Mag dus niet
hetzelfde zijn als het vorige getrokken getal. En de kans om ieder getal te
nemen moet even groot zijn. Ik kan dus niet zeggen dat als het getal al
getrokken is, plus 1 te doen.
Kan iemand me tips geven of me verder helpen? Alvast bedankt!
Greetz ;)
Digibyte

[Rudy]

Post by Hans Stavleu
Ik bedacht me het volgende. Zet elk getal tot x in een array. Loop de array
van 1 tot en met x door en wissel de inhoud met een random ander element van
de array. Als je daarna bijvoorbeeld tien willekeurige getallen uit de reeks
nodig hebt, neem je gewoon de eerste tien elementen van het array.
hans stavleu

Bij deze methode moet wel de range waarin de willekeurige getallen worden
getrokken correct zijn. Stel A is een array met n elementen [0, 1, ..., n-1]
en random(x) geeft een willekeurig getal in de range 0 ... x, inclusief 0 en
exclusief x. Deze methode is fout:


for i = n-1 down to 1
j = random( n+1 )
swap A[i] , A[j]


Met random(n+1) zijn er n^n combinaties, terwijl er maar n! permutaties
mogelijk zijn. Deze methode is goed:


for i = n-1 down to 1
j = random( i+1 )
swap A[i] , A[j]



Met groet,

Rudy

[Rudy]

Post by Hans Stavleu
Ik bedacht me het volgende. Zet elk getal tot x in een array. Loop de array
van 1 tot en met x door en wissel de inhoud met een random ander element van
de array. Als je daarna bijvoorbeeld tien willekeurige getallen uit de reeks
nodig hebt, neem je gewoon de eerste tien elementen van het array.
hans stavleu

Bij deze methode moet wel de range waarin de willekeurige getallen worden
getrokken correct zijn. Stel A is een array met n elementen [0, 1, ..., n-1]
en random(x) geeft een willekeurig getal in de range 0 ... x, inclusief 0 en
exclusief x. Deze methode is fout:


for i = n-1 down to 1
j = random( n+1 )
swap A[i] , A[j]


Met random(n+1) zijn er n^n combinaties, terwijl er maar n! permutaties
mogelijk zijn. Deze methode is goed:


for i = n-1 down to 1
j = random( i+1 )
swap A[i] , A[j]



Met groet,

Rudy

[Lambik69]

Post by Rudy

Post by Hans Stavleu
Ik bedacht me het volgende. Zet elk getal tot x in een array. Loop de array
van 1 tot en met x door en wissel de inhoud met een random ander element van
de array. Als je daarna bijvoorbeeld tien willekeurige getallen uit de reeks
nodig hebt, neem je gewoon de eerste tien elementen van het array.
hans stavleu

Bij deze methode moet wel de range waarin de willekeurige getallen worden
getrokken correct zijn. Stel A is een array met n elementen [0, 1, ..., n-1]
en random(x) geeft een willekeurig getal in de range 0 ... x, inclusief 0 en
for i = n-1 down to 1
j = random( n+1 )
swap A[i] , A[j]
Met random(n+1) zijn er n^n combinaties, terwijl er maar n! permutaties
for i = n-1 down to 1
j = random( i+1 )
swap A[i] , A[j]

Voordat jullie het wiel opnieuw gaan uitvinden zoek eens naar het in Perl
alom bekende Fisher-Yates shuffle algoritme. Onderstaand een javascript
uitvoering (Bron: http://sedition.com/perl/javascript-fy.html) .

<script type="text/javascript">
function fisherYates ( myArray ) {
var i = myArray.length;
while ( i-- ) {
var j = Math.floor( Math.random() * ( i + 1 ) );
var tempi = myArray[i];
var tempj = myArray[j];
myArray[i] = tempj;
myArray[j] = tempi;
}
}

var asLucky = new Array ( 2, 3, 4, 5, 7, 9, 11, 13 );
fisherYates(asLucky);
var yourNumber = asLucky[0];
document.write("Your lucky number is: <b>" + yourNumber + "</b>");
</script>

[Ewoud Dronkert]

Post by Lambik69
Voordat jullie het wiel opnieuw gaan uitvinden

Voordat jij ook weer een willekeurig stukje code hier neerplempt, zou
je eerst eens moeten lezen wat in de vorige posts stond. Rudy heeft
gelijk (behalve een typo n+1 ipv n in het eerste stukje code), het
zgn. Fisher-Yates algoritme is niet zo goed. Zie ook
http://216.239.37.104/search?q=cache:i4fYIDxsza4J:penguin.ewu.edu/~trolfe/Unpublished/Shuffles/
(uit de Google cache omdat de pagina zelf niet bereikbaar was; jammer
want er staan wel leuke plaatjes op). De al door de eerste reply
genoemde 'gatenvulmethode' is een variant op het tweede, correcte,
shuffle algoritme.

[Dr.Ruud]

Post by Lambik69
function fisherYates ( myArray ) {
var i = myArray.length;
while ( i-- ) {
var j = Math.floor( Math.random() * ( i + 1 ) );
var tempi = myArray[i];
var tempj = myArray[j];
myArray[i] = tempj;
myArray[j] = tempi;
}
}

Vreemde swap-code, en i en j kunnen gelijk zijn.


function fisherYates ( myArray ) {

var i = myArray.length;
var j;
var temp;

while ( i-- ) {
j = Math.floor( Math.random() * ( i + 1 ) );
if ( i != j ) {
temp = myArray[i];
myArray[i] = myArray[j];
myArray[j] = temp;
}
}
}

[Rene]

Post by Dr.Ruud
Vreemde swap-code, en i en j kunnen gelijk zijn.

Dit is op zich niet fout en ik denk dat performance technisch gezien de
vergelijking i != j meer overhead geeft dan (statistisch gezien) 1 op n keer
een onnodige swap, behalve bij kleine arrays dan (dat wordt CPU ticks tellen
:-))

Post by Dr.Ruud
function fisherYates ( myArray ) {
var i = myArray.length;
var j;
var temp;
while ( i-- ) {
j = Math.floor( Math.random() * ( i + 1 ) );
if ( i != j ) {
temp = myArray[i];
myArray[i] = myArray[j];
myArray[j] = temp;
}
}
}
--
Affijn, Ruud

[Dr.Ruud]

Post by Rene
(statistisch gezien) 1 op n

Het hangt ook nog af van de verdeling van de gekozen
randomizer. En je vergeet denk ik dat i omlaagt stapt:
hoe kleiner i is, hoe groter de kans dat j weer eens
gelijk aan i is.

Een vergelijking van loopvariabelen kost normaal
gesproken veel minder CPU dan een swap.

[Jos A. Horsmeier]

Post by Dr.Ruud

Post by Rene
(statistisch gezien) 1 op n

Het hangt ook nog af van de verdeling van de gekozen
hoe kleiner i is, hoe groter de kans dat j weer eens
gelijk aan i is.
Een vergelijking van loopvariabelen kost normaal
gesproken veel minder CPU dan een swap.

Is Donald Knuth nu al helemaal de vergetelheid in geduwd?
ref: 'The Art Of Computer Programming -- Seminumerical Algorithms'
(volume 2) pag 139-141. Niks geen gedoe met tests of i gelijk aan
j is etc. etc. gewoon een correct, simpel algorithme.

Jos (het gaat slecht met de 'wetenschap' informatica zo te merken)

[Ewoud Dronkert]

Post by Jos A. Horsmeier
Is Donald Knuth nu al helemaal de vergetelheid in geduwd?

Ik heb vaak getwijfeld om de set te kopen, maar vond het altijd te
duur. Of althans, veel geld.

Post by Jos A. Horsmeier
ref: 'The Art Of Computer Programming -- Seminumerical Algorithms'
(volume 2) pag 139-141.

Tja, ik heb 'm dus niet. Zou je niet even willen quoten?

Post by Jos A. Horsmeier
Niks geen gedoe met tests of i gelijk aan
j is etc. etc. gewoon een correct, simpel algorithme.
Jos (het gaat slecht met de 'wetenschap' informatica zo te merken)

Ach hou op man. Het perfecte algoritme waar alle mogelijke permutaties
even waarschijnlijk zijn (alleen nog afhankelijk van de kwaliteit van
de random number generator) is al meteen genoemd in de 1e reply. Ik
gaf een stukje C code in mijn 1e reply. Dat "gedoe met tests" is niet
relevant voor de correctheid van het algoritme, maar misschien wel
voor de performance van de implementatie. De snelheid wordt niet van
een andere orde, maar scheelt binnen de orde wel een bepaalde factor.
Kan ook belangrijk zijn.

Hier, het is niet Knuth, maar ook interessant:
http://okmij.org/ftp/Haskell/perfect-shuffle.txt

[Dr.Ruud]

Post by Jos A. Horsmeier

Post by Dr.Ruud

Post by Rene
(statistisch gezien) 1 op n

Het hangt ook nog af van de verdeling van de gekozen
hoe kleiner i is, hoe groter de kans dat j weer eens
gelijk aan i is.
Een vergelijking van loopvariabelen kost normaal
gesproken veel minder CPU dan een swap.

Is Donald Knuth nu al helemaal de vergetelheid in geduwd?

Maar het ging inmiddels over patronen in bagger.

[Jan de Vos]

Post by Dr.Ruud
Een vergelijking van loopvariabelen kost normaal
gesproken veel minder CPU dan een swap.

Nog los van het feit dat meestal i niet gelijk is aan j, en je in die
gevallen dus verlies boekt, moet je ook nog rekening houden met
pipiline-bubbles. Op de momenten dat i gelijk is aan j, en je dus
verwacht door die check wat tijd te besparen, wordt meestal de branch
verkeerd voorspeld, en moet de pipeline geflushed worden.

Waarschijnlijk is de code zonder die check dus sneller.


jdv

[Dr.Ruud]

Post by Jan de Vos
Op de momenten dat i gelijk is aan j, en je dus
verwacht door die check wat tijd te besparen,
wordt meestal de branch
verkeerd voorspeld, en moet de pipeline geflushed worden.

Je doet een flink aantal aannames, over wat ik verwacht en
over de omgeving waarin die code draait. Overigens is er
normaal gesproken weinig mis met het flushen van overbodige
code.

Een memcopy( a, a, n ) doet misschien niks,
maar levert wel function-call-overhead op.

Post by Jan de Vos
Waarschijnlijk is de code zonder die check dus sneller.

Ik denk niet dat dat verschil opmerkwaardig is.

[Jan de Vos]

Post by Jan de Vos
verkeerd voorspeld, en moet de pipeline geflushed worden.

[...] Overigens is er normaal gesproken weinig mis met het flushen van
overbodige code.
Een memcopy( a, a, n ) doet misschien niks, maar levert wel
function-call-overhead op.

Volgens mij snap je niet helemaal wat het flushen van de pipeline
inhoud.

Post by Jan de Vos
Waarschijnlijk is de code zonder die check dus sneller.

Ik denk niet dat dat verschil opmerkwaardig is.

Dat kan soms heel opmerkwaardig zijn. Als je in een klein loopje, dat
/erg vaak/ wordt uitgevoerd, moet kiezen tussen in een paar instructies
een swap doen, en en vergelijking met een branch die vaak verkeerd
voorspeld kan worden, dan is het sneller om maar gewoon die swap te doen
(ook al doe je in feitte niets). Zeker op een moderne processor als de
P4, met een erg diepe pipeline.


jdv

[Dr.Ruud]

Post by Jan de Vos
Volgens mij snap je niet helemaal wat het flushen
van de pipeline inhoud.

Je snapt ongetwijfeld wel meer niet.

Post by Jan de Vos

Post by Dr.Ruud
Ik denk niet dat dat verschil opmerkwaardig is.

Dat kan soms heel opmerkwaardig zijn.

Ik beperk me tot de situatie van de OP.

[Jan de Vos]

Post by Dr.Ruud

Post by Jan de Vos
Volgens mij snap je niet helemaal wat het flushen
van de pipeline inhoud.

Je snapt ongetwijfeld wel meer niet.

Abosoluut, deze opmerking snap ik bijvoorbeeld niet zo goed...

Post by Dr.Ruud

Post by Jan de Vos

Post by Dr.Ruud
Ik denk niet dat dat verschil opmerkwaardig is.

Dat kan soms heel opmerkwaardig zijn.

Ik beperk me tot de situatie van de OP.

Tja. Dan was de hele discussie een beetje onzinnig. Maar de opmerking

Post by Dr.Ruud

Post by Jan de Vos

Post by Dr.Ruud

Post by Dr.Ruud
Een vergelijking van loopvariabelen kost normaal
gesproken veel minder CPU dan een swap.

Dat leek me een redelijk algemene opmerking, en ik wilde alleen
duidelijk maken dat dat volgens mij in het geval van de OP precies niet
zo was.


jdv