Uniek random getal

Pagina: 1
Acties:
  • 645 views sinds 30-01-2008
  • Reageer

Acties:
  • 0 Henk 'm!

  • Beyond
  • Registratie: Juni 2001
  • Laatst online: 00:25

Beyond

Dussssss.......

Topicstarter
[Javascript]

Ik heb een lijst van 25 getallen. Nu wil ik graag dat alle getallen 1x voorkomen maar dan wel random.

Met Math.Random() komen er ook dezelfde getallen voor.


Hoe pak ik dit aan ?

[ Voor 5% gewijzigd door Beyond op 28-03-2003 20:09 ]

Al het goeie.......


Acties:
  • 0 Henk 'm!

  • dominic
  • Registratie: Juli 2000
  • Laatst online: 21:19

dominic

will code for food

Hou in een array bij welke getallen er al uitgedeeld zijn.

Download my music on SoundCloud


Acties:
  • 0 Henk 'm!

  • Beyond
  • Registratie: Juni 2001
  • Laatst online: 00:25

Beyond

Dussssss.......

Topicstarter
dat heb ik gedaan. Maar nu krijg ik af en toe nog 1 dubbele

Al het goeie.......


Acties:
  • 0 Henk 'm!

  • Apache
  • Registratie: Juli 2000
  • Laatst online: 09-07 11:41

Apache

amateur software devver

Dan is je algo buggy?

If it ain't broken it doesn't have enough features


Acties:
  • 0 Henk 'm!

  • Beyond
  • Registratie: Juni 2001
  • Laatst online: 00:25

Beyond

Dussssss.......

Topicstarter
var randomNummers = new Array();
for (i=0;i<25;i++) {
var randomNr = Math.floor(1 + Math.random() * 25 ); //Random getal


for (j=0;j<25;j++) {
if (randomNummers[j] == randomNr ) {
randomNr = Math.floor(1 + Math.random() * 25); //Random getal
j = 0;
}
}

randomNummers[i] = randomNr;
document.write(randomNummers[i]+'<br>');
}

Dit gaat soms wel goed en soms zit er dus 1 dubbele tussen

[ Voor 19% gewijzigd door Beyond op 28-03-2003 20:14 ]

Al het goeie.......


Acties:
  • 0 Henk 'm!

  • HunterPro
  • Registratie: Juni 2001
  • Niet online
Je genereert een getal, kijkt of ie al in de array staat, zo nee display je 'm en zet je 'm in de array er bij, als ie wel al bestaat begin je opnieuw. Simple as that. Had je zelf ook kunnen verzinnen.

Acties:
  • 0 Henk 'm!

  • Denhomer
  • Registratie: Augustus 2000
  • Laatst online: 02-06 11:19

Denhomer

Doh !

probeer es iets a la
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for (i=0;i<MAX;i++) {
  randomNr = Math.floor(1 + Math.random() * 25);
  while (zitAlInArray(randomNr) {
    randomNr = Math.floor(1 + Math.random() * 25);
  }
  randomNummers[i] = randomNr;
}

function zitAlInArray(nummer) {
  erIn = false;
  for (i=0;i<MAX;i++) {
    if (randomNummers[i] == nummer)
      erIn = true;
  }
  return erIn;
}

Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
Poe wat een gedoe... Wat ik meestal doe is een array van (in dit geval) 25 cijfers netjes vullen op volgorde en dan een stuk of tig keer wat random nummers swappen. Dat resulteert vaak in een kortere code. Ik vind dat persoonlijk leesbaarder...

Tevens kan de executie tijd van bovengenoemde methodes flink oplopen bij meer getallen. Stel dat je 10.000 willekeurige getallen wil hebben. Voor de eerste paar honderd valt het nog mee, maar tegen het eind moet je steeds een array van 10.000 elementen checken of je het getal al hebt gehad, en zo ja dan kun je een nieuw getal genereren en opnieuw beginnen. Dan is mijn methode denk ik toch vlotter.

Maar da's just my $0.02

/edit/
Effe snel in mekaar geflanst...Verander maxLen in elke willekeurige waarde (>0) om een andere array grootte te nemen...
JavaScript:
1
2
3
4
5
6
7
8
9
10
var myArr = new Array;
var maxLen = 25;
var r1, r2;
        
for(t=1;t<=maxLen;t++) { myArr[t]=t; }  //Vul array oplopend
for(t=1;t<=maxLen;t++) {        //Hussel array
    r1 = 1 + parseInt(Math.random() * maxLen);  //Random getal 1
    r2 = 1 + parseInt(Math.random() * maxLen);  //Random getal 2
    myArr[0] = myArr[r1]; myArr[r1]=myArr[r2]; myArr[r2]=myArr[0];  //Swap getallen m.b.v. Array element 0 (wordt niet gebruikt)
}   


You get the point...

/edit2/
Dit is de inhoud van myArr in 4 runs:
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
1   6   13  14
23  16  9   22
19  3   5   3
4   24  11  25
5   2   3   21
24  9   18  12
11  17  6   6
8   11  20  24
22  20  19  7
25  8   7   20
17  13  25  2
18  18  2   5
20  21  1   19
3   14  24  11
7   5   12  4
14  4   16  15
12  10  4   17
9   23  8   18
16  1   10  1
15  15  15  8
21  19  17  10
10  22  22  13
2   12  23  23
6   7   14  16
13  25  21  9

[ Voor 104% gewijzigd door RobIII op 28-03-2003 23:05 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

Anoniem: 26306

JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
function getRandomArray(size) {
   var stack = [], output = [];

   for (var i = 0; i < size; i++) stack[i] = i;
   for (var i = 0; i < size; i++) {
      r = Math.floor(Math.random() * stack.length);
      output[output.length] = stack[r];
      stack[r] = null;
   }

   return output;
}

Het is niet de mooiste code, maar wel de snelste die ik kon bedenken, en 100% zeker volledig random. Deze blijft ook met grote array's lekker werken, in tegenstelling tot de manier van HunterPro.

Deze geeft bij mij 100 array's met 1000 willekeurige getallen terug in 0.8 seconde in IE 6.0.

[edit]
Ergens in het optimizen is er een bug ingeslopen, die mag je er zelf uithalen ;) Het principe is wel duidelijk.

[ Voor 10% gewijzigd door Anoniem: 26306 op 28-03-2003 21:05 ]


Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
<hier stond onzin>

Laat maar...* RobIII heeft niet goed gekeken...
Anoniem: 26306 schreef op 28 maart 2003 @ 21:03:
[edit]
Ergens in het optimizen is er een bug ingeslopen, die mag je er zelf uithalen ;) Het principe is wel duidelijk.
Het kan aan mij liggen, maar ik zie het "principe" hier niet... :? Behalve dat je willekeurige items van een "stack" wipt (popt). Is dat het "principe" dat je bedoelt? Want "poppen" kan volgens mij (en volgens MS) alleen met het laatste element.

Als dat wél zou kunnen zou je idd een hele optimale methode hebben...

[ Voor 157% gewijzigd door RobIII op 28-03-2003 23:02 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

Anoniem: 10445

* Anoniem: 10445 is dan wel geen javascript held....maar probeert ook wat

vin dit persoonlijk het mooist...

JavaScript:
1
2
3
4
5
6
7
function getShuffleArray(size){
    var arr = new Array;
    for(var t=0;t<=size;t++) { arr[t]=t; }
    return arr.sort(function(){return (Math.floor(Math.random() * 3)) -1});
}

alert(getShuffleArray(20));


In actionscript is deze methode de netste, en de snelste omdat je de sort procedure gebruikt....weet niet in JS ... just my 2 centjes :)

[ Voor 11% gewijzigd door Anoniem: 10445 op 29-03-2003 00:17 . Reden: code tag ]


Acties:
  • 0 Henk 'm!

Anoniem: 26306

RobIII schreef op 28 March 2003 @ 22:45:

Het kan aan mij liggen, maar ik zie het "principe" hier niet... :? Behalve dat je willekeurige items van een "stack" wipt (popt). Is dat het "principe" dat je bedoelt? Want "poppen" kan volgens mij (en volgens MS) alleen met het laatste element.

Als dat wél zou kunnen zou je idd een hele optimale methode hebben...

Ik gebruikte eerst Array.splice, maar die methode is helaas wat trager. Ik dacht eigenlijk dat de waarde opvragen, en vervolgens de waarde in die array als null in te stellen hetzelfde effect had, maar helaas is dat dus niet zo. Goed: dit had ik eerst, maar is dus iets trager:
JavaScript:
1
2
3
4
5
6
7
8
function getRandomArray(size) {
   var stack = [], output = [];

   for (var i = 0; i < size; i++) stack[i] = i;
   for (var i = 0; i < size; i++) output.push(stack.splice(Math.floor(Math.random() * stack.length), 1));

   return output;
}

Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

Voor mijn schuifpuzzle heb ik de volgende methode gebruikt:
JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var winnum = new Array();
for (var num = 0; num < (numx * numy - 1); num++) { winnum[num] = num; }

// shuffle
for (num = 0; num < 2 * winnum.length; num++) {

  var x = Math.floor(Math.random() * winnum.length);
  var y = Math.floor(Math.random() * (winnum.length-1));
  if (y >= x) y++;
  winnum[x] += winnum[y];
  winnum[y] = winnum[x] - winnum[y];
  winnum[x] -= winnum[y];

}

niet volledig opgemaliseerd, en achteraf snap ik de y>=x vergelijking ook niet meer; volgens mij is y==x afdoende. Maar de bedoeling mag duidelijk zijn: ik swap dus een x aantal keer twee waarden met elkaar. Het voordeel hierbij was dat ik ook altijd een puzzel kreeg die weer op te lossen was :)

Intentionally left blank


Acties:
  • 0 Henk 'm!

Anoniem: 39126

Gebruik:

code:
1
2
3
4
5
6
7
8
9
10
randomNumbers = new Array(25)
for (var i = 0; i != randomNumbers.length; ++i)
  randomNumbers[i] = i
for (var i = 0; i != randomNumbers.length; ++i) {
// swap every element with random element
  var r = parseInt(Math.random() * randomNumbers.length)
  var temp = randomNumbers[i]
  randomNumbers[i] = randomNumbers[r]
  randomNumbers[r] = temp
}


Je hoeft elk element maar 1x te verwisselen met een ander element. Nu heb je een perfect geshuffled array met 25 elementen, waarin alle 25 getalletjes (0 tot en met 24) 1x voorkomen.

EDIT: alle andere methodes in deze thread zijn trager omdat ze meer dan 25 keer een random nummer moeten genereren, terwijl het hier 25 keer hoeft voor 25 nummers.

Oh ja, als je nummers van 1 tot en met 25 i.p.v. 0 tot en met 24 wil dan voeg je gewoon deze regel toe:
code:
1
for (var i = 0; i != randomNumbers.length; ++i) ++randomNumbers[i]


EDIT 2: Vooral de methode van RobIII (NOFI) is slecht: bij deze methode worden niet alle nummers gehusseld, of je hebt heeeel veel rondes nodig.

[ Voor 36% gewijzigd door Anoniem: 39126 op 29-03-2003 13:59 ]


Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
Anoniem: 39126 schreef op 29 March 2003 @ 13:39:
EDIT 2: Vooral de methode van RobIII (NOFI) is slecht: bij deze methode worden niet alle nummers gehusseld, of je hebt heeeel veel rondes nodig.
Ik ben het met je eens dat 2x een rnd getal genereren niet erg optimaal is. maar als je mijn output bekijkt zie je toch duidelijk dat alle getallen gehusseld worden :?

JavaScript:
1
2
3
4
5
6
7
8
9
var myArr = new Array;
var maxLen = 25;
var r;
        
for(t=1;t<=maxLen;t++) { myArr[t]=t; }  //Vul array oplopend
for(t=1;t<=maxLen;t++) {        //Hussel array
    r = 1 + parseInt(Math.random() * maxLen);   //Random getal
    myArr[0] = myArr[r]; myArr[r]=myArr[t]; myArr[t]=myArr[0];  //Swap getallen m.b.v. Array element 0 (wordt niet gebruikt)
}   


Maar dan is dit toch net zo makkelijk? Zoals ik al aangaf heb ik 'm snel in mekaar geflanst, en niet echt geoptimaliseerd. Maar dit werkt dus echt wel even goed als je het mij vraagt, want het is zo'n beetje dezelfde code als jouw code...En ik was de eerste in deze draad die met deze methode kwam, en goed onderbouwde waarom bovenstaande methodes niet goed werken bij grote aantallen... Het ging om het princiepe, niet de uitvoering...

dus...

maar verder inderdaad No Flame Taken ;)

[ Voor 19% gewijzigd door RobIII op 29-03-2003 15:07 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

Anoniem: 39126

Zoals je hem nu veranderd hebt werkt hij natuurlijk wel perfect. Je eerdere methode garandeert nooit dat alle nummers verhusseld zijn (alleen bij oneindig veel rondes). In de praktijk zal hij best goed werken, maar als je er statistiek op los zou laten, zou je zien dat de kansverdeling niet totaal uniform is, maar dat er een voorkeur onstaat voor de startplaats van elk nummer (dus het cijfer 4 zal een (iets) verhoogde kans hebben om op de vierde plaats terecht te komen). Ik gebruik pseudo random nummers vaak voor wetenschappelijke simulaties, en dan is zoiets absoluut dodelijk en niet verdedigbaar, vandaar dat ik je methode "slecht" noemde. Voor simpele spelletjes ofzo zal niemand het merken en dan is hij wel "goed".

Dat jouw code op die van mij leek was toevallig (mijn code had ik gekopieerd uit een oeroud programma van mezelf). Dat je steeds 2 nummers i.p.v. 1 nummer genereert is niet zo erg, maar het gaat om het principe dat je dan niet alle nummers hebt verwisseld na 1 ronde, dat is het probleem van je eerste methode. Optimalisatie is vaak onbelangrijk, alleen als je in tijdnood komt met simulaties, maar het principe moet wel goed werken, en dan bedoel ik dat de kans dat een nummer op een bepaalde plaats eindigt exact hetzelfde moet zijn voor elke plaats.

Anyway, volgens mij zijn we het qua code i.i.g eens geworden ;)

Acties:
  • 0 Henk 'm!

Anoniem: 26306

Even een dikke teleurstelling voor de heren John_Smith en robIII, als ik dit eens 10.000 keer uitvoer, en dan keek hoeveel keer nummer 1 op elke plaats in de array stond, dan is dat bij mijn methode altijd redelijk dicht bij de 400 keer bij een array met een lengte van 25.
Dat getal ligt voor elke positie ergens tussen de 375 en 425.

Bij jullie methoden, die inderdaad sneller zijn, is dat lang niet altijd zo, sterker nog, bij de methoden van jullie is de kans wat groter dat het getal op zijn eigen plaats blijft staan, resp. 1 plaats 'zakt'. Getallen van in de 500 zijn bij jullie niet ongewoon.

In mijn functie is de standaarddeviatie zo rond de 20, bij bijvoorbeeld John_Smith's functie is dat nogal fluctuerend, tussen de 30 en 50.
Ik durf wel te beweren dat jullie geen wiskundig bewijs kunnen leveren dat jullie methode werkt ;)

Acties:
  • 0 Henk 'm!

  • Clay
  • Registratie: Oktober 1999
  • Laatst online: 21-08-2024

Clay

cookie erbij?

dan post ik mijnes ook :P
ik zou em zo gedaan hebben:

JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
function getRandomList(amount, from, to) {
    var res = [], unique = true;
    for(var i=0; i<amount; i++) {
        do {
            unique = true;
            res[i] = Math.floor(Math.random() * (to - from)) + from;
            for(var j=0; j<res.length; j++)
                if(i != j && res[i] == res[j]) unique = false;
        } while (unique == false);
    } return res;   
}

alert(getRandomList(25, 0,50));

Instagram | Flickr | "Let my music become battle cries" - Frédéric Chopin


Acties:
  • 0 Henk 'm!

Anoniem: 26306

Oei Clay, die functie is best zwaar als je heb 10.000 keer uitvoert :D

En die functie wordt heel vlug minder efficiënt als het om grotere array's gaat. Bij een array met een lengte van 1000 elementen gaat al het niet zo lekker :)

Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

Edit: code ff verbouwen; doorrekenen met een al gehusselde array geeft natuurlijk altijd betere random resultaten....

[ Voor 121% gewijzigd door crisp op 30-03-2003 17:20 ]

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
En dit is wat ik met mijn functie krijg:
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
Pos| 1   2   3   4   5   6   7   8   9   10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25 
---|---------------------------------------------------------------------------------------------------
1  |419 541 524 524 542 454 439 439 426 425 395 394 382 409 401 373 339 348 355 311 304 331 297 319 309 
2  |396 414 522 515 468 504 453 448 429 431 406 396 407 410 388 368 378 360 321 337 328 334 325 328 334 
3  |409 383 380 589 502 509 453 478 476 451 439 417 426 407 363 371 353 350 384 318 313 314 303 303 309 
4  |429 369 406 378 499 521 491 437 478 438 434 413 417 373 401 409 389 369 367 364 323 315 323 331 326 
5  |416 377 400 377 355 503 484 488 465 476 425 459 418 396 409 393 386 381 363 346 347 345 363 324 304 
6  |427 390 396 374 369 342 492 466 454 421 421 438 448 408 416 416 408 370 353 383 409 369 375 336 319 
7  |403 436 407 358 374 339 339 505 481 479 502 480 416 429 416 393 400 373 329 416 343 375 350 340 317 
8  |383 385 367 396 337 377 358 356 499 477 466 439 435 419 434 410 434 415 393 359 356 388 376 378 363 
9  |391 385 389 354 365 327 377 319 354 479 489 482 447 473 481 461 424 397 425 362 374 350 377 344 374 
10 |358 413 386 392 392 348 361 329 350 340 492 480 459 466 424 411 420 396 436 407 380 384 392 399 385 
11 |410 352 350 353 390 342 363 385 380 355 360 460 458 457 434 393 448 431 473 429 418 399 421 390 349 
12 |387 442 375 371 346 372 380 387 336 312 342 362 481 476 456 432 424 442 465 424 408 416 395 359 410 
13 |427 401 375 370 373 361 375 326 339 383 381 343 354 473 463 450 453 446 440 439 408 402 394 404 420 
14 |426 406 372 400 382 370 341 361 309 361 351 344 319 388 454 489 497 467 434 458 436 396 448 395 396 
15 |364 414 371 387 386 392 398 382 344 356 315 344 359 346 347 455 494 471 454 451 477 417 412 441 423 
16 |336 381 406 383 396 385 389 359 345 358 346 326 356 371 364 333 430 520 527 485 466 479 441 393 425 
17 |409 410 384 376 390 388 383 374 369 398 376 383 343 359 342 346 359 477 435 489 442 471 442 410 445 
18 |415 382 403 363 327 419 362 378 398 396 364 368 336 383 341 371 367 375 435 453 495 482 473 479 435 
19 |427 417 392 357 410 389 398 386 374 364 380 346 399 340 347 342 364 332 343 503 501 487 507 449 446 
20 |395 401 411 380 377 361 384 419 389 362 388 362 386 334 367 404 333 357 385 368 522 481 474 508 452 
21 |414 367 418 396 384 378 350 386 387 396 370 399 401 347 368 395 357 372 340 382 362 532 486 495 518 
22 |389 363 376 404 407 416 387 383 402 381 362 370 398 356 401 378 375 385 380 366 397 369 526 532 497 
23 |418 404 379 371 405 390 408 403 417 374 386 360 393 386 388 384 375 399 377 371 365 386 372 553 536 
24 |377 391 388 418 420 396 429 394 392 378 397 411 377 387 405 429 396 365 381 386 397 386 362 401 537 
25 |375 376 423 414 404 417 406 412 407 409 413 424 385 407 390 394 397 402 405 393 429 392 366 389 371

Horizontaal: Telling hoe vaak het cijfer voorkwam op de (verticale) positie
Veticaal: De positie in de array

Mijn (brakke ;)) testcode:
JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
<script language="JavaScript">
var myArr = new Array;
var maxLen = 25;
var r;
var arrCount = new Array(maxLen);        

for(t=1;t<=maxLen;t++) {    //Init "count" array
    arrCount[t] = new Array(maxLen);
    for(u=1;u<=maxLen;u++) {arrCount[t][u]=0;}
}

for (lLoop=1;lLoop<=10000;lLoop++) {    //Loop 10.000 keer
    for(t=1;t<=maxLen;t++) { myArr[t]=t; }    //Vul array oplopend
    for(t=1;t<=maxLen;t++) {        //Hussel array
        r = 1 + parseInt(Math.random() * maxLen);    //Random getal
        myArr[0] = myArr[r]; myArr[r]=myArr[t]; myArr[t]=myArr[0];    //Swap getallen
    }

    for (t=1;t<=maxLen;t++) { arrCount[t][myArr[t]]++;} //Tel welk getal op welke positie staat
}

document.write ('<table><tr><th>Pos</th>'); //Maak een tabel kop
for (t=1;t<=maxLen;t++) {document.write('<th>' + t + '</th>');}
document.write ('</tr>');

for (t=1;t<=maxLen;t++) {   //Druk de array met tellingen af
    document.write('<tr><th>' + t + '</th>');
    for(u=1;u<=maxLen;u++) { document.write('<td>' + arrCount[t][u] + '</td>'); }
    document.write('</tr>');
}
document.write ('</table>');    //sluit tabel
</script>


..en ik moet zeggen: Ik heb zojuist Cheatah's code getest, maar die komt idd beter in de buurt van de 400...
Ik vraag me nu dus wel af waar John_Smith en ik de mist in gaan. Ik zie niet in waarom onze methode niet goed is. Het lijkt me eerder dat onze code "randomer" is :+

/edit/
De enige plek waar ik denk "de mist in te gaan" is idd dat het bij ons kan voorkomen dat een element soms vaker geswapt kan worden, en dat kan bij Cheatah niet. Zijn SD is daarom dus ook beter en idd bij ons dus slechter. Maar ik denk wel dat het voor het uiteindelijke doel idd allemaal niet zoveel uitmaakt. Maarre, Cheatah: _/-\o_ netjes hoor!

* RobIII gaat zich zitten schamen in een hoekje :+

[ Voor 52% gewijzigd door RobIII op 30-03-2003 16:59 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

RobIII schreef op 30 maart 2003 @ 16:39:
[...]
..en ik moet zeggen: Ik heb zojuist Cheatah's code getest, maar die komt idd beter in de buurt van de 400...
Ik vraag me nu dus wel af waar John_Smith en ik de mist in gaan. Ik zie niet in waarom onze methode niet goed is.
Even een beetje verbouwd en in mijn script gepropt:
JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function shuffle(arr) {

  var i,j;
  var l = arr.length;

  for (i = 0; i < l; i++) {

    j = parseInt(Math.random() * (l - 1));
    if (j == i) j++;
    arr[i] += arr[j];
    arr[j] = arr[i] - arr[j];
    arr[i] -= arr[j];

  }

  return arr;

}

Nu zie je dat je wel degelijk in de buurt van een SD van 20 komt tegen aanzienlijk lagere processingtijd (3.125 seconde vs 4.357 voor mijn code @AMD XP2000 IE6SP1) :)

Aarrggh, vergeten dat als je een array als parameter meegeeft dat het een pass by reference is en niet by copy in JS |:(
Even de boel weer verbouwen....

[ Voor 12% gewijzigd door crisp op 30-03-2003 18:05 ]

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

Deze is bij kleine l (ongeveer tot 100 getallen) sneller dan de implementatie van Chaetah, met gelijke SD (rond de 20):
JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function shuffle5(l) {

  var i,j;
  var res = [];

  for (i = 0; i < l; i++) {

    do {
      j = Math.floor(Math.random() * l);
    } while (typeof res[j] != 'undefined');

    res[j] = i;

  }

  return res;

}

[ Voor 3% gewijzigd door crisp op 30-03-2003 18:05 ]

Intentionally left blank


Acties:
  • 0 Henk 'm!

Anoniem: 39126

Cheatah, er lijkt inderdaad iets mis te gaan in mijn algoritme.
* Anoniem: 39126 gaat zich ook zitten schamen in een hoekje, maar vooral ook even nadenken wat er mis gaat als hij weer tijd heeft....

Cheatah, ongeveer jouw manier kan misschien iets sneller met:
JavaScript:
1
2
3
4
5
6
function getRandomArray(size) {
  var output = []
  for (var i = 0; i < size; ++i) 
    output.splice(parseInt(Math.random() * (output.length + 1)), 0, i)
  return output;
}


omdat je dan maar 1 array en geen push functie nodig hebt. Misschien kan een van jullie die een testprogje heeft dit even uitproberen, want je weet nooit wat nou sneller is met js (ligt er maar net aan hoe alles diep in de browser gebeurt).

Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

De verschillende methoden even in een script gezet waarmee de SD en parsetime te bekijken valt (ik ben erg vrij geweest in het implementeren van de verschillende methoden en heb hier en daar wat veranderingen / verbeteringen aangebracht - hier valt natuurlijk over te discuseren ;) ):

Note: RobIII's eerste voorbeeld was qua algorithme ongeveer gelijk aan mijn 1e voorbeeld; RobIII's 2e voorbeeld volgde John_Smith's voorbeeld

[knip]script even naar verderop geplaatst met toevoegingen[/knip]

De resultaten, bij 10000 maal met l = 25:

shuffle1: SD: 33.48; tijd: 4.677 sec
shuffle2: SD: 62.56; tijd: 1.993 sec
shuffle3: SD: 18.84; tijd: 6.720 sec
shuffle4: SD: 18.72; tijd: 30.414 sec
shuffle5: SD: 21.32; tijd: 3.525 sec

De resultaten, bij 1000 maal met l = 100:

shuffle1: SD: 3.50; tijd: 1.642 sec
shuffle2: SD: 3.35; tijd: 0.912 sec
shuffle3: SD: 3.02; tijd: 6.289 sec
shuffle4: SD: 3.07; tijd: 61.098 sec
shuffle5: SD: 3.10; tijd: 6.319 sec

[ Voor 81% gewijzigd door crisp op 31-03-2003 02:35 ]

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
Anoniem: 39126 schreef op 30 March 2003 @ 18:17:
Cheatah, er lijkt inderdaad iets mis te gaan in mijn algoritme.
* Anoniem: 39126 gaat zich ook zitten schamen in een hoekje, maar vooral ook even nadenken wat er mis gaat als hij weer tijd heeft....

Cheatah, ongeveer jouw manier kan misschien iets sneller met:
JavaScript:
1
2
3
4
5
6
function getRandomArray(size) {
  var output = []
  for (var i = 0; i < size; ++i) 
    output.splice(parseInt(Math.random() * (output.length + 1)), 0, i)
  return output;
}


omdat je dan maar 1 array en geen push functie nodig hebt. Misschien kan een van jullie die een testprogje heeft dit even uitproberen, want je weet nooit wat nou sneller is met js (ligt er maar net aan hoe alles diep in de browser gebeurt).
toon volledige bericht
Het probleem in onze methode is dat het bij ons kan voorkomen dat je eerst positie 12 naar 7 swapt, en later positie 18 naar 7 toe. Dan heb je dus plekje 7 twee keer overschreven. In het geval van Cheatah wordt er altijd 1 nummer van de stack "gewipt" en vervolgens een ander nummer dat achter in de array aan sluit. Vandaar dat zijn SD rond de 20 ligt, en die van ons nogal "schommelt" :+

Excuses voor de brakke uitleg. Het is zondag :+

/edit/
...en ondertussen duizelt het bij TS Beyond! We zijn nogal offtopic geraakt vrees ik :+

[ Voor 6% gewijzigd door RobIII op 30-03-2003 18:36 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

Anoniem: 39126 schreef op 30 maart 2003 @ 18:17:
[...]
omdat je dan maar 1 array en geen push functie nodig hebt. Misschien kan een van jullie die een testprogje heeft dit even uitproberen, want je weet nooit wat nou sneller is met js (ligt er maar net aan hoe alles diep in de browser gebeurt).
Is inderdaad sneller:
JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// vrij naar Cheatah / John_Smith
function shuffle6(l) {

  var i;
  var res = [];

  for (i = 0; i < l; i++) {

    res.splice(Math.floor(Math.random() * (res.length + 1)), 0, i)

  }

  return res;

}


10000 keer bij l = 25:
SD: 19.52; tijd: 3.725 sec

1000 keer bij l = 100:
SD: 3.02; tijd: 3.475 sec

:)

Intentionally left blank


Acties:
  • 0 Henk 'm!

Anoniem: 39126

Ok, ik kan natuurlijk niet gaan slapen voordat de fout gevonden is ;). Ik geloof dat ik nu begrijp wat er mis gaat in mijn eerste algoritme. Ook heb ik nu een algoritme bedacht waarvan ik claim dat hij wel gegarandeerd altijd goed werkt en...... dat hij het snelste is van allemaal :7 (er hoeft maar 24 keer i.p.v. 25 keer een random nummer gegenereerd te worden):

JavaScript:
1
2
3
4
5
6
7
8
9
function shuffle(size) {
  var random = []
  for (var i = 0; i < size; ++i) random[i] = i
  for (var i = size - 1; i > 0; --i) {
    var r = parseInt(Math.random() * (i + 1))
    temp = random[i]; random[i] = random[r]; random[r] = temp
  }
  return random
}


Nu dan de uitleg wat er fout was aan de eerste: stel dat er n getallen zijn. Als het eerste getal verwisseld wordt, heeft hij een kans van 1/n om op een bepaalde plaats te komen, gelijk voor alle n de plaatsen. Na n verwisselingen, zijn er nn (n tot de macht n) uitkomsten mogelijk, maar, er zijn maar n! (n faculteit) verschillende verwisselingen mogelijk. Omdat nn/n! geen geheel getal is meestal, heeft niet elke mogelijke verwisseling een exact gelijke kans om te worden gegenereerd. De verschillen zijn maar heel klein, maar omdat het net zo uitkomt dat het aantal verwisselingen waarin bijvoorbeeld getal 2 op plaats 2 eindigt (dit kan op (n - 1)! manieren) net allemaal behoren tot die verzameling waarvan de kans net iets groter dan gemiddeld is dat deze gegenereerd wordt, komt de totale kans een stuk groter uit.

Even een voorbeeldje ter verduidelijking:

Stel je hebt drie nummers. Je begint met

123

Na het verwisselen van het eerste nummer krijg je

123, 213 of 321 met elk een kans van 1/3.

Na verwisselen van het tweede nummer krijg je 9 uitkomsten waarvan er 5 verschillend zijn. Na verwisselen van het derde nummer krijg je 27 uitkomsten, waarvan er 6 verschillend zijn.

123 komt 5 keer voor van de 27.
132 komt 5 keer voor van de 27.
213 komt 4 keer voor van de 27.
231 komt 5 keer voor van de 27.
312 komt 4 keer voor van de 27.
321 komt 4 keer voor van de 27.

Nummer 1 op plaats 1 heeft een kans van 10/27, terwijl de kans dan nummer 1 op plaats 2 eindigt 8/27 is. En bijvoorbeeld nummer 3 heeft een grotere kans om op plaats 2 te eindigen dan op plaats 1.

crisp: mooi overzicht!

[ Voor 19% gewijzigd door Anoniem: 39126 op 31-03-2003 01:32 ]


Acties:
  • 0 Henk 'm!

Anoniem: 11670

Het kan nog sneller gewoon een tabel vullen met random getallen

Acties:
  • 0 Henk 'm!

Anoniem: 39126

Anoniem: 11670 schreef op 31 March 2003 @ 01:30:
Het kan nog sneller gewoon een tabel vullen met random getallen
En hoe garandeer je dan dat alle getallen in die tabel uniek zijn? :?

Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
Anoniem: 39126 schreef op 31 March 2003 @ 01:14:
<knip>en...... dat hij het snelste is van allemaal :7 (er hoeft maar 24 keer i.p.v. 25 keer een random nummer gegenereerd te worden)</knip>
Over nutteloze optimalisatie gesproken :7. Dus bij 10.000 getallen hoeft er "maar" 9.999 x een random getal te worden gegenereerd. Dan maakt die ene het ook niet meer sefke.. :*)

[ Voor 24% gewijzigd door RobIII op 31-03-2003 02:00 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

Anoniem: 39126

Ik bedoelde meer in vergelijking met de goedwerkende van Cheatah. Deze werkt net zo goed, maar de uitvoertijd is bij Cheatahs algoritme 8.9 seconden op mijn computer en bij de mijne 3.8 seconden. Dat is toch wel een groot verschil. Getest met de test van crisp.

Edit: .5 sec. langzamer dan welke? ik neem aan de niet goed werkende die we eerst hadden? Bij mij is hij .3 sec. sneller i.p.v. . seconden, maar ja, dat oudere algoritme werkte niet goed.

[ Voor 27% gewijzigd door Anoniem: 39126 op 31-03-2003 02:01 ]


Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

Toegevoegd aan het script; verder is een tijdelijke var voor het wisselen van 2 variabelen sneller dan mijn 'rekentruuk' - dus heb ik dat aangepast in shuffle1 en shuffle2
Ook is Math.floor sneller dan parseInt ;)

HTML:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
<html>
<head>
<title>Shuffle an Array</title>
<script type="text/javascript">

function doit() {

  var i,j;
  var l = 25;

  var verd = [];
  for (i = 0; i < l; i++) {
    verd[i] = [];
    for (j = 0; j < l; j++) {
      verd[i][j] = 0;
    }
  }

  var starttime = new Date().valueOf();

  for (i = 0; i < 10000; i++) {

    // !!! kies hier de methode !!!
    var numshuf = shuffle7(l);

    for (j = 0; j < l; j++) {

      verd[numshuf[j]][j]++;

    }

  }

  var endtime = new Date().valueOf();
  var duration = (endtime - starttime) / 1000;

  var res = '';
  var sdavg = 0;
  var cursd;
  for (i = 0; i < l; i++) {

    cursd = sd(verd[i]);
    sdavg += cursd;
    res += 'Verdeling '+i+': '+verd[i].toString()+' - SD: '+cursd+'<br />';

  }

  sdavg = sdavg / l;
  res += '<br />Average SD: '+sdavg+'<br />';
  res += 'Duration: '+duration+' seconds';

  document.getElementById('results').innerHTML = res;

}

// vrij naar RobIII / crisp
function shuffle1(l) {

  var i,x,y,temp;

  // fill number array;
  var arr = [];
  for (i = 0; i < l; i++) { arr[i] = i; }

  for (i = 0; i < 2*l; i++) {

    x = Math.floor(Math.random() * l);
    do {
      y = Math.floor(Math.random() * l);
    } while (y == x);

    temp = arr[x]; arr[x] = arr[y]; arr[y] = temp;

  }

  return arr;

}

// vrij naar John_Smith / RobIII
function shuffle2(l) {

  var i,j,temp;

  // fill number array;
  var arr = [];
  for (i = 0; i < l; i++) { arr[i] = i; }

  for (i = 0; i < l; i++) {

    do {
      j = Math.floor(Math.random() * l);
    } while (j == i);

    temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

  }

  return arr;

}

// vrij naar Cheatah
function shuffle3(l) {

  var i;
  var res = [];

  // fill number array;
  var arr = [];
  for (i = 0; i < l; i++) { arr[i] = i; }

  for (i = 0; i < l; i++) {

    res.push(arr.splice(Math.floor(Math.random() * arr.length), 1));

  }

  return res;

}

// vrij naar Clay
function shuffle4(l) {

  var i,j;
  var res = [];

  for (i = 0; i < l; i++) {

    do {

      unique = true;
      res[i] = Math.floor(Math.random() * l);

      for(j = 0; j < res.length; j++) {

        if (i != j && res[i] == res[j]) unique = false;

      }

    } while (unique == false);

  }

  return res;

}

// crisp
function shuffle5(l) {

  var i,j;
  var res = [];

  for (i = 0; i < l; i++) {

    do {
      j = Math.floor(Math.random() * l);
    } while (typeof res[j] != 'undefined');

    res[j] = i;

  }

  return res;

}

// vrij naar Cheatah / John_Smith
function shuffle6(l) {

  var i;
  var res = [];

  for (i = 0; i < l; i++) {

    res.splice(Math.floor(Math.random() * (res.length + 1)), 0, i)

  }

  return res;

}

// vrij naar John_Smith
function shuffle7(l) {

  var i,j,temp;
  var res = [];

  for (i = 0; i < l; ++i) { res[i] = i; }

  for (var i = l - 1; i > 0; --i) {

    j = Math.floor(Math.random() * (i + 1))
    temp = res[i]; res[i] = res[j]; res[j] = temp;

  }

  return res;

}

function sd(arr) {

  var i;
  var l = arr.length;
  var avg = 0;

  for (i = 0; i < l; i++) {

    avg += arr[i];

  }
  avg = avg / l;

  var d;
  var d2 = 0;

  for (i = 0; i < l; i++) {

    d = arr[i] - avg;
    d2 += d * d;

  }

  var sd = Math.sqrt(d2 / l);

  return Math.round(sd);

}

</script>
</head>
<body onload="doit()">
<div id="results"></div>
</body>
</html>


resultaat van shuffle7 bij 10000 keer met l = 25:
SD: 19.88; tijd: 1.902 sec

resultaat van shuffle7 bij 1000 keer met l = 100:
SD: 3.06; tijd: 0.891 sec

Edit: shuffle2 is qua snelheid ongeveer gelijk in deze test na mijn laatste wijzigingen, maar minder accuraat

[ Voor 7% gewijzigd door crisp op 31-03-2003 02:08 ]

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
effe (nog verder) offtopic: Zijn hier nooit geen contests ofzo voor gehouden op het web? Lijkt me interessant om te kijken wie dat heeft gewonnen en hoe 'ie dat deed...
Heb wel ff gezocht, maar vond zo snel niks.

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij


Acties:
  • 0 Henk 'm!

Anoniem: 39126

effe mee offtopic: Kan ook niets vinden zo snel, maar dit probleem is ongetwijfeld vaker opgelost. Misschien iets te simpel voor een contest, maar wel leuk om te zien hoe veel er te zeggen/denken/optimaliseren valt aan een stukje code van een paar regels :)

Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

Anoniem: 39126 schreef op 31 March 2003 @ 02:13:
effe mee ontopic: Kan ook niets vinden zo snel, maar dit probleem is ongetwijfeld vaker opgelost. Misschien iets te simpel voor een contest, maar wel leuk om te zien hoe veel er te zeggen/denken/optimaliseren valt aan een stukje code van een paar regels :)
Vaak kan je dit soort dingen mooi gebruiken als optimalisatie binnen grotere stukken code, net zoals een floodfill algoritme of een collapse algoritme. Het kan je een contest zoals deze doen winnen :)

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • Clay
  • Registratie: Oktober 1999
  • Laatst online: 21-08-2024

Clay

cookie erbij?

crisp schreef op 31 March 2003 @ 02:00:
Toegevoegd aan het script; verder is een tijdelijke var voor het wisselen van 2 variabelen sneller dan mijn 'rekentruuk' - dus heb ik dat aangepast in shuffle1 en shuffle2
Ook is Math.floor sneller dan parseInt ;)

HTML:
1
2
3
<html>
...
</html>
Ik zie dat je mijn stukje code heb gerenamed naar "shuffle", maar dat deed die expliciet niet! het was een random zoeker waar je n getallen kreeg in een range van a tot b, dus 10 uit 100 oid, maar geen shuffle dus! uiteraard is die als shuffle trager als je em daarvoor gebruikt :D (moet me toch even verdedigen voor het produceren van de traagste code in dit topic ;) )

Instagram | Flickr | "Let my music become battle cries" - Frédéric Chopin


Acties:
  • 0 Henk 'm!

Anoniem: 10445

Is math.sort() dan zo traag?

Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

Clay schreef op 31 March 2003 @ 09:32:
[...]


Ik zie dat je mijn stukje code heb gerenamed naar "shuffle", maar dat deed die expliciet niet! het was een random zoeker waar je n getallen kreeg in een range van a tot b, dus 10 uit 100 oid, maar geen shuffle dus! uiteraard is die als shuffle trager als je em daarvoor gebruikt :D (moet me toch even verdedigen voor het produceren van de traagste code in dit topic ;) )
ja, en als je dus 25 unieke getallen wilt uit de range 0-24 dan is het dus een shuffle; het uniek moeten zijn verklaart dan de traagheid. 25 unieke getallen uit een range van 0 tot 999 zal inderdaad veel sneller gaan :)
mmmz, ik heb jouw code nog niet getest zie ik; zal ik vanavond nog even toevoegen (eerst werken...)

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • Clay
  • Registratie: Oktober 1999
  • Laatst online: 21-08-2024

Clay

cookie erbij?

ben laatst ook al eens bezig geweest met dingen in js timen, dus ik heb er nu maar een soort tooltje voor geschreven; deze.

beknopte uitleg: type code, geef het een title en klik "create". dan komt ie er rechts bij te staan. klik dan run, en tada, de tijd komt eronder, en nog es, en nog es ;) Wil je een andere bench maken? typ andere code, title, create, run. en dan kan je rechts in de lijst op de cols klikken om tussen tests te switchen. Naarmate je er meer hebt staan gaat alles overigens steeds trager. Ik heb verder geen idee in hoeverre alle code die erin hangt van invloed is op de benchtijden, maar het is denk ik niet veel.

Instagram | Flickr | "Let my music become battle cries" - Frédéric Chopin


Acties:
  • 0 Henk 'm!

Anoniem: 39126

Zelf als je 1 test meerdere keren runt wordt hij steeds trager:

demo4
991 ms
992 ms
992 ms
1011 ms
1001 ms
1011 ms
1011 ms
1012 ms
1022 ms
1021 ms
1041 ms
1042 ms
1032 ms
1052 ms
1051 ms
1062 ms
1052 ms
1062 ms
1082 ms
1071 ms
1081 ms
1092 ms
1102 ms
1102 ms
1112 ms
1112 ms
1121 ms
1122 ms
1131 ms
1142 ms
1172 ms

Verder zou het wel handig zijn als je kunt kiezen om een test een x aantal maal uit te voeren en ook zou ik testen wel willen kunnen deleten/overwriten/aanpassen. Verders leuk tooltje.

Acties:
  • 0 Henk 'm!

Anoniem: 10445

crisp schreef op 31 maart 2003 @ 13:22:
[...]

ja, en als je dus 25 unieke getallen wilt uit de range 0-24 dan is het dus een shuffle; het uniek moeten zijn verklaart dan de traagheid. 25 unieke getallen uit een range van 0 tot 999 zal inderdaad veel sneller gaan :)

[...]

mmmz, ik heb jouw code nog niet getest zie ik; zal ik vanavond nog even toevoegen (eerst werken...)
ben benieuwddddd

Acties:
  • 0 Henk 'm!

  • drm
  • Registratie: Februari 2001
  • Laatst online: 09-06 13:31

drm

f0pc0dert

[nohtml]
Clay:
ben laatst ook al eens bezig geweest met dingen in js timen, dus ik heb er nu maar een soort tooltje voor geschreven; deze.
Zit een "bugje" in. Als de code een fout bevat kun je de oude title niet overschrijven. Lijkt me eenvoudig af te vangen met een try { } catch () statement :)

Music is the pleasure the human mind experiences from counting without being aware that it is counting
~ Gottfried Leibniz


Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

Belofte maakt schuld:
JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
// vrij naar B-Top
function shuffle8(l) {

  var i;

  // fill number array;
  var arr = [];
  for (i = 0; i < l; i++) { arr[i] = i; }

  return arr.sort(function(){return (Math.floor(Math.random() * 3)) -1});

}

(een compare functie is niet voorbehouden aan actionscript, maar kan ook gewoon in javascript :) )

Resultaten:
10000 x met l = 25:
SD: 498.52; tijd: 5.138 sec

1000 x met l = 100:
SD: 26.57; tijd: 4.646 sec

Was enigszins te verwachten; de kans dat een nummer in de buurt van z'n originele plek blijft staan is namelijk relatief groot; ook qua tijd is de sort() toch kostbaar...

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • Clay
  • Registratie: Oktober 1999
  • Laatst online: 21-08-2024

Clay

cookie erbij?

Anoniem: 39126 schreef op 31 March 2003 @ 20:06:
Zelf als je 1 test meerdere keren runt wordt hij steeds trager:

demo4
991 ms
...
1172 ms

Verder zou het wel handig zijn als je kunt kiezen om een test een x aantal maal uit te voeren en ook zou ik testen wel willen kunnen deleten/overwriten/aanpassen. Verders leuk tooltje.
Jah. het wordt inderdaad trager. Dat was eerst nog erger :) maar heb er al wel iets aan kunnen doen dus. Als je weet waar het aan ligt, en wat eraan te doen is houd ik me aanbevolen :) Het kan overigens ook aan brak geheugendinges van de browser zelf liggen. Ken daar op zijn minst 1 voorbeeld van, dus ik sluit andere bugs niet uit.
zelfs als je de benchmark refresht en de demo nog een keer uitvoert gaat het al trager.

Try catch zal ik er ook ff in bouwen nog. Wat ook wel grappig is is dat online benchmarken veel trager gaat dan offline. :{ :? wat heeft dat nou met clients side code te maken.

[ Voor 5% gewijzigd door Clay op 01-04-2003 10:59 ]

Instagram | Flickr | "Let my music become battle cries" - Frédéric Chopin


Acties:
  • 0 Henk 'm!

  • edie
  • Registratie: Februari 2002
  • Laatst online: 22:35
Bijna. Volgens mij moet je * 2 ipv * 3 doen :)
If compareFunction(a, b) is less than 0, sort b to a lower index than a.

If compareFunction(a, b) returns 0, leave a and b unchanged with respect to each other, but sorted with respect to all different elements.

If compareFunction(a, b) is greater than 0, sort b to a higher index than a.
http://devedge.netscape.c...erence/array.html#1196882

De range is dus -1 tot +1 (-1, 0 en 1). Dus random * 2 - 1.

Dit is mijn codetje
JavaScript:
1
2
3
4
5
6
7
8
9
10
11
12
function sorteer( a, b )
{
    return (Math.round( Math.random() * 2) - 1);
}

function shuffle9( aantal )
{
    var arr = new Array( aantal );

    for( teller = 1; teller <= aantal; teller++ ){ arr[teller - 1] = teller; }
    return arr.sort( sorteer );
}

"In America, consumption equals jobs. In these days, banks aren't lending us the money we need to buy the things we don't need to create the jobs we need to pay back the loans we can't afford." - Stephen Colbert


Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

eddie19 schreef op 01 april 2003 @ 11:43:
[...]

Bijna. Volgens mij moet je * 2 ipv * 3 doen :)
Nope, ik gebruik nl Math.floor en niet Math.round:
JavaScript:
1
Math.floor(Math.random() * 3))

dit geeft dus een 0, 1 of 2 terug; trek er daar 1 vanaf en je krijgt -1, 0 of 1 :)

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • edie
  • Registratie: Februari 2002
  • Laatst online: 22:35
crisp schreef op 01 april 2003 @ 11:48:
[...]

Nope, ik gebruik nl Math.floor en niet Math.round:
JavaScript:
1
Math.floor(Math.random() * 3))

dit geeft dus een 0, 1 of 2 terug; trek er daar 1 vanaf en je krijgt -1, 0 of 1 :)
Kan Math.random() dan geen 1 terug geven? In de reference staat wel 'between 0 and 1', maar volgens mij is er een kans dat hij 0 of 1 teruggeeft.

"In America, consumption equals jobs. In these days, banks aren't lending us the money we need to buy the things we don't need to create the jobs we need to pay back the loans we can't afford." - Stephen Colbert


Acties:
  • 0 Henk 'm!

  • crisp
  • Registratie: Februari 2000
  • Nu online

crisp

Devver

Pixelated

eddie19 schreef op 01 April 2003 @ 11:55:
[...]

Kan Math.random() dan geen 1 terug geven? In de reference staat wel 'between 0 and 1', maar volgens mij is er een kans dat hij 0 of 1 teruggeeft.
Ik heb het nog nooit meegemaakt...

Intentionally left blank


Acties:
  • 0 Henk 'm!

  • xces
  • Registratie: Juli 2001
  • Laatst online: 07-07 20:37

xces

To got or not to got..

lol, "The quest for the ultimate random script" :D

Acties:
  • 0 Henk 'm!

Anoniem: 39126

Ik ging ervanuit dat Math.random() zoals de meeste pseudo random nummer generators een getal in de range [0, 1) geeft (dus 0 <= x < 1): 0 doet wel mee en 1 niet, maar dat staat niet duidelijk in de references van JavaScript en JScript. Daar staat alleen "between 0 and 1", niet helemaal duidelijk dus.

Edit:
Van de specificatie van ECMAscript (waaraan JScript en volgens mij ook JavaScript aan voldoen of aan gaan voldoen):

http://www.ecma-internati...iles/ecma-st/Ecma-262.pdf

...
15.8.2 Function Properties of the Math Object
...
15.8.2.14 random()

Returns a number value with positive sign, greater than or equal to 0 but less than 1, chosen randomly or pseudo randomly with approximately uniform distribution over that range, using an implementation-dependent algorithm or strategy. This function takes no arguments.

Inderdaad doet 0 mee en 1 niet. Ik las op nieuwsgroeps dat sommige versies van Opera een bug hebben dat 1 WEL meedoet, maar ik weet niet om welke versies het gaat.

[ Voor 57% gewijzigd door Anoniem: 39126 op 01-04-2003 17:12 ]


Acties:
  • 0 Henk 'm!

Anoniem: 39126

Hier een overzicht van hoe de algoritmes volgens mij werken en wat er mis/goed aan is. (Je moet toch wat doen als je een paar daagjes thuis zit ;) ).

Ik heb ze gesorteerd van slechts naar best (discussie is mogelijk).

De eerste drie werken met verwisselen van een gesorteerd array. Bij alle drie is het resulterende array niet goed random. Hiermee bedoel ik dat de kans dat een willekeurig gekozen nummer op een willekeurig gekozen plaats eindigt niet gelijk is voor alle nummers/plaatsen.

Tot deze categorie behoren:
shuffle8() B-Top ("randomness" is erg slecht)
shuffle1() RobIII / crisp
shuffle2() John_Smith / RobIII (snelste van de drie)

De tweede categorie werkt met "trial and error", d.w.z.: blijf random nummers of random plaatsen proberen en als het nummer al bestaat of de plaats al bezet is, genereer dan opnieuw een nummer, net zolang tot het array gevuld is. Deze algoritmes zorgen WEL voor een goed random resultaat, maar het nadeel is dat ze traag kunnen worden, vooral als het aantal nummers groot wordt.

Tot deze categorie behoren:
shuffle4() Clay
shuffle5() crisp (veel sneller dan 4)

De laatste categorie werkt door steeds een willekeurig element uit een gesorteerd array te halen, dit te verwijderen en in een "resultaat"-array te stoppen, dan wel een gesorteerd nummer steeds op een willekeurige plaats in een resultaat-array te inserten.

Tot deze categorie behoren:
shuffle3() Cheatah (werkt het traagst van de drie)
shuffle6() Cheatah / John Smith
shuffle7() John_Smith (werkt het snelst van allemaal)


**********************************************
Overzicht van alle algoritmes in bovengenoemde volgorde, de genoemde tijden zijn voor een array van 25 elementen (10.000 keer) en voor een array van 100 elementen (1000 keer). Benchmarks uitgevoerd door crisp.

shuffle8() B-Top
* start met geordend array
* sorteer met "random" sorteerfunctie. De sorteerfunctie vertelt of element A groter, kleiner of gelijk is aan element B (+1, 0 , -1). Door random +1, 0 of -1 te
geven, wordt er min of meer random "gesorteerd".

uniform verdeeld: nee
probleem: de kans dat een nummer dicht in de buurt vanzijn originele plaats eindigt is erg groot
tijd: 5.138/4.646

shuffle1() RobIII / crisp
* start met geordend array
* kies steeds 2 random elementen en verwissel, herhaal dit 2 * size maal

uniform verdeeld: nee
probleem: er is een redelijke kans dat een element nooit verwisseld wordt
tijd: 4.677/1.642

shuffle2() John_Smith / RobIII
* start met geordend array
* verwissel elk element met een random gekozen ander element

uniform verdeeld: nee
probleem: niet alle mogelijke verwisselingen komen even vaak voor
tijd: 1.993/0.912

shuffle4() Clay
* genereer steeds een random nummer in de juiste range
* als dit nummer al in het "resultaat" array zit, gooi hem weg en genereeer een nieuw nummer
* herhaal dit tot het array gevuld is

uniform verdeeld: ja
tijd: 30.414/61.098
probleem: vooral het vinden van de laatste nummers zal erg lang duren omdat er dan meestal een al bestaand nummer gegenereerd zal worden

shuffle5() crisp
* genereer steeds een random nummer in de juiste range
* als er op deze plaats al een nummer staat, ga dan een nieuw nummer genereren
* zo niet, zet dan het i-de nummer op deze plaats

Lijkt op shuffle4(), maar dan veel efficienter

uniform verdeeld: ja
tijd: 3.525/6.319
probleem: bij grote size zal dit algoritme ook traag worden

shuffle3() Cheatah
* start met geordend array
* kies steeds random een element uit dit array; verwijder dit uit het geordende array en stop het in een "resultaat"-array, herhaal dit tot het geordende array leeg is

uniform verdeeld: ja
tijd: 6.720/6.289

shuffle6() Cheatah / John Smith
* start met leeg "resultaat"-array
* genereer steeds een random nummer dat de grootte van het "resultaat"-array + 1 is
* "insert" het i-de nummer op het random gegenereerde plaatsnummer, herhaal tot array gevuld is

Lijkt op shuffle3(), maar nu wordt maar 1 array gebruikt

uniform verdeeld: ja
tijd: 3.725/3.475

shuffle7() John_Smith
* start met geordend array
* verdeel het array denkbeeldig in twee: het voorste deel bestaat uit nog niet gebruikte nummers, het achterste deel bestaat uit nummers in random volgorde
* kies steeds random een van de voorste nummers (dit groepje wordt steeds kleiner), verwissel dit random gekozen nummer met het eerste nummer van de
"achterkant". De voorkant is nu 1 kleiner geworden en de groep random nummers (achterkant) is 1 groter geworden. Ga door tot alle nummers naar achteren zijn gewerkt.

Lijkt op shuffle3(), maar efficienter omdat inserten/deleten niet nodig is.

uniform verdeeld: ja
tijd: 1.902/0.891

**************************************
Conclusie: de eerste drie algoritmes zijn niet aan te bevelen omdat ze niet goed werken. De volgende twee zijn niet aan te bevelen als "shuffle" algoritme, maar zijn wel zeer geschikt om een klein aantal unieke willekeurige nummers uit een groot aantal te kiezen. De laatste drie algoritmes werken goed en zijn efficient. De eerste van de laatste drie laat het duidelijkst zien hoe het werkt, de laatste is een aantal maal sneller dan de eerste.

Acties:
  • 0 Henk 'm!

Anoniem: 4364

Een klein beetje offtopic, maar over random gesproken, een oude truc uit de demo-scene is van te voren een flinke array te maken met pre-calculated random nummers, en hier doorheen te lopen. Sneller dan steeds een nieuw random nummer uit te rekenen.

zoiets van (in java);

code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// global vars
    int radoz[] = new int[6000];  // random buffer
    int rstep;
    int rpos;

// init set data
    for (int i=0; i<6000; i++)
    {
        radoz[i]= (int) (Math.random()*255);
    }
    rstep=1;  // step through random buffer
    rpos=0; // random buffer position

// main-loop

    while ()
    { 
        mygreycolor=Randooz();
    }

// functions

    private int Randooz()
    {   
        rpos=rpos+rstep; 
        if (rpos>=6000) 
        {
            rstep=(int) (Math.random()*20)+1; //calculate a new step
            rpos=(int) (Math.random()*20); // calculate random buffer position
        }
        return (int) (radoz[rpos]); 
    }


Nu zat ik aan een alternatief voor random() te denken;

'human-based random'. Door bijvoorbeeld de random-buffer
te vullen/veranderen, doordat bijvoorbeeld de user zijn muis beweegt.

experiment hier;
http://www.xs4all.nl/~elout/2003/04/java/humanrandom02.html
(Beweeg je muis over de applet voor variatie.)

source;
http://www.xs4all.nl/~elout/2003/04/java/humanrandom02.java

De random buffer is nu express niet zo groot, wat leuke rasters opleverd,
mijn zwakke stukje zit nog in het stuk code, waar de nieuwe rstep en rpos
wordt berekend, mischien moet ik deze aan de klok-tijd hangen.

Acties:
  • 0 Henk 'm!

  • RobIII
  • Registratie: December 2001
  • Niet online

RobIII

Admin Devschuur®

^ Romeinse Ⅲ ja!

(overleden)
Anoniem: 4364 schreef op 02 april 2003 @ 15:29:
<knip>
experiment hier;
http://www.xs4all.nl/~elout/2003/04/java/humanrandom02.html
(Beweeg je muis over de applet voor variatie.)
<knip>
Heel heel heel flauw, maar wel een inkoppertje: "Ik krijg het beeld niet scherp" :+

Maarre, het gaat hier meer over het shuffelen dan om een random getal te genereren. Lees de thread er nog maar eens op na.

edit:

cel-ed schreef op 02 april 2003 @ 15:29:
Een klein beetje offtopic...


Oops.. Je zegt het zelf al ;)

[ Voor 19% gewijzigd door RobIII op 02-04-2003 18:06 ]

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Je eigen tweaker.me redirect

Over mij

Pagina: 1