Algorithme de sélection aléatoire rapide

Étant donné un tableau de valeurs vrai/faux, quel est l'algorithme le plus efficace pour sélectionner un index avec une vraie valeur au hasard.Algorithme de sélection aléatoire rapide

Un algorithme simple esquisse est

a <- the array 
c <- 0 
for i in a: 
    if a[i] is true: c++ 
e <- random number in (0, c-1) 
j <- 0 
for i in e: 
    while j is false: j++ 
return j

Quelqu'un peut-il trouver un algorithme plus rapide? Peut-être existe-t-il un moyen de ne parcourir la liste qu'une seule fois même si le nombre d'éléments vrais n'est pas connu au début?

Source

2009-12-03 momeara

Juste curieux de savoir, dans quelles applications ces types d'algorithmes sont-ils utilisés? Il y a quelque temps, je suis tombé sur une question similaire, étant donné un tableau de taille infinie, les n premiers endroits sont remplis de 1, les autres sont des zéros. Maintenant, ce tableau est donné à un nouvel utilisateur (qui ne connaît pas la valeur de n). Maintenant, découvrez un algorithme pour marquer l'endroit où le dernier 1 est là. Cela j'ai résolu par la recherche binaire. S'il vous plaît donner quelques exemples où ceux-ci sont utilisés. – avd

Près de dupliquer: http://stackoverflow.com/questions/1133942/what-is-the-most-efficient-way-to-pick-a-random-card-from-a-deck-when-some-cards. Dans cette question le tableau est de taille 52, cependant, ce qui pourrait affecter les réponses (par exemple, vous êtes à peu près certain qu'un arary de taille 52 tient dans la mémoire, alors que 'a' ici ne correspond pas). –

Utilisez l'algorithme "Choisir un élément aléatoire dans une liste infinie". Conservez un index de votre choix actuel, ainsi qu'un décompte du nombre de valeurs vraies que vous avez vues.

Lorsque vous voyez une valeur vraie, incrémentez le compte puis remplacez votre choix par l'indice actuel avec une probabilité de P = (1/nombre). (Vous toujours choisir le premier que vous trouverez ... vous pourrait passer à la seconde, avec une probabilité 1/2, vous pourrait passer à la troisième avec probabilty 1/3, etc.)

Ceci nécessite seulement un balayage sur la liste et un stockage constant. (Cela vous oblige cependant à calculer un plus grand nombre de nombres aléatoires.) En particulier, il ne vous est jamais nécessaire de mettre en mémoire tampon la liste ou de revenir au début - donc cela peut fonctionner sur un flux d'entrée non borné.

Voir this answer pour un exemple de mise en œuvre LINQ de l'algorithme simple "choisir un élément aléatoire"; il aurait juste besoin de petites modifications.

Source

2009-12-03 15:32:06

Un peu plus de détails et une preuve ici: http://stackoverflow.com/questions/1133942/what-is-the-most-efficient-way-to-pick-a-random-card-from-a-deck- quand-certaines-cartes/1134286 # 1134286. Cette question est fonctionnellement une copie de celle-là, bien que libellée un peu différemment. Mon instinct est qu'il sera probablement plus lent que l'algorithme à deux passages, en supposant des données en mémoire. Mais vaut la peine d'être testé si la performance en deux passes est inacceptable pour une raison quelconque. –

@Steve: Cela dépend de la parcimonie des "vraies" valeurs par rapport au coût de génération d'un nombre aléatoire. Si vous avez un million d'entrées dans la liste, dont seulement 2 sont "vraies", alors il s'agit probablement d'une victoire. Si, par contre, vous avez un million d'entrées * toutes * vraies, l'algorithme à deux passages sera probablement plus rapide. En général, j'aime juste l'élégance des algorithmes de stockage constant à un passage :) –

Heh, je viens juste de faire le même commentaire sur la clarté de la réponse de Johannes. Je suis également d'accord sur l'élégance, bien que je m'inquiète légèrement du fait que l'utilisation d'un grand nombre de nombres aléatoires rend plus difficile l'analyse des effets des faiblesses du RNG. –

Créez une liste avec des index qui pointent vers true et sélectionnez-en un au hasard. Nécessite O (n) pour la traversée de liste et un essai pour le nombre aléatoire.

Source

2009-12-03 15:27:31 Joey

C'est certainement plus rapide que ce que j'ai imaginé, bien qu'il utilise l'espace de travail O (n), où le mien utilise uniquement un espace de travail constant. Donc, il pourrait encore y avoir une marge d'amélioration. – momeara

Est-ce certainement plus rapide? Si les vraies valeurs sont très rares, alors c'est presque certainement plus rapide. Si les valeurs fausses sont très rares, alors c'est presque certainement plus lent. Là où le seuil de rentabilité est, je ne sais pas. –

Oui, la distribution des valeurs vrai/faux est certainement importante pour la question de savoir quel algorithme est le plus efficace. Mais quand ce n'est pas connu tous les paris sont éteints, comme d'habitude. Pourtant, je trouve la réponse de Jon très agréable et susceptible d'être meilleure que celle-ci. – Joey

Algorithme de sélection aléatoire rapide

Répondre

Questions connexes