Gewichtete zufällige Auswahl

[Andreas Pflug]

// Nun ein Beispiel zur gewichteten Selektierung:

double r = random();  // Zufallszahl zw. 0 und 1
int i=0;
while(r>A2[i]) ++i;
int iselected = i;

Es fiel woanders im Thread noch das Stichwort
'Binäre Suche'. Diese könnte man
hier wie folgt realisieren (in Pseudo-Code):

  
double r=random();  
int    i=0, imin=0, imax=length-1;  
while(imax-imin>1) {  
  i = imin + (imax-imin)/2; // wird automatisch gerundet, da vom Typ 'int'  
  if (r>A2[i]) { imin=i; } else { imax=i; }  
}  
int iselected = r>A2[imin] ? imax : imin;  

Das sollte auch bei 1 Mio Elementen noch ausreichend schnell sein
und die 8 MB für das Gewichtungs-Array sollten auch noch
über sein... ;-)

MfG

Andreas