Sous échantillonage histogramme sans remise
Bonjour,
Je dispose d'un histogramme représentant la probabilité d'obtenir des évènements. J'aimerais sous échantilloner cet histogramme de facon aléatoire, sans remise, en respectant les probabilités de tirage ( la probabilité de tirer une coordonnée sera décrémentée à chaque fois que je la tire) .
Une solution assez lourde est de construire un histogramme cumulatif, de tirer une valeur aléatoire entre 0 et le max de cumul ( ou 0 et 1 si l'histogramme est normalisé), et faire un binary search pour trouver l'index de la valeur tiree ( correspondant à l'évènement). Le sous histogramme verra la valeur de cet index incrémenté, et l'histogramme initial verra la valeur de cet index décrémenté.
Pour passer au tirage suivant , il faut ensuite reconstruire l'histogramme cummulatif.
Pour un histogramme de taille avoisinant les dizaines de millions, et des tailles de sous histogrammes allant de quelques milliers a quelques millions, je vous laisse imaginer le temps que ca met....
Quelqu'un aurait une idée pour réduire le temps de calcul ?
Merci d'avance!
Répondre avec citation
Envoyé par johnkhm
?
Partager