Efficacement la sélection d'un ensemble d'éléments aléatoires à partir d'une liste liée
Dire que j'ai une liste de nombres de longueur N. N est très grand et je ne sais pas à l'avance la valeur exacte de N.
Comment puis-je écrire le plus efficacement une fonction qui retournera k complètement nombres aléatoires de la liste?
6 réponses
Il y a un algorithme très agréable et efficace pour cela en utilisant une méthode appelée reservoir sampling .
Permettez-moi de commencer par vous donner son histoire:
Knuth appelle cet algorithme R à la p. 144 de son édition 1997 des algorithmes Seminumériques (volume 2 de L'Art De La Programmation informatique), et fournit un code pour cela. Knuth attribue L'algorithme à Alan G. Waterman. Malgré une longue recherche, Je n'ai pas pu trouver Waterman document original, s'il existe, ce qui peut expliquer pourquoi vous verrez le plus souvent Knuth cité comme source de cet algorithme.
McLeod et Bellhouse, 1983 (1) Fournir une discussion plus approfondie que Knuth ainsi que la première preuve publiée (dont je suis conscient) que l'algorithme fonctionne.
Vitter 1985 (2) examine L'algorithme R et présente ensuite trois algorithmes supplémentaires qui fournissent la même sortie, mais avec une torsion. Plutôt que de faire un choix pour inclure ou ignorer chaque élément entrant, Son algorithme prédétermine le nombre d'éléments entrants à ignorer. Dans ses tests (qui, certes, sont obsolètes maintenant), ce temps d'exécution a considérablement diminué en évitant la génération de nombres aléatoires et les comparaisons sur chaque nombre entrant.
Dans pseudo-code, l'algorithme est:
Let R be the result array of size s
Let I be an input queue
> Fill the reservoir array
for j in the range [1,s]:
R[j]=I.pop()
elements_seen=s
while I is not empty:
elements_seen+=1
j=random(1,elements_seen) > This is inclusive
if j<=s:
R[j]=I.pop()
else:
I.pop()
Notez que j'ai spécifiquement écrit le code pour éviter de spécifier la taille de l'entrée. C'est l'une des propriétés cool de ceci algorithme: vous pouvez l'exécuter sans avoir besoin de connaître la taille de l'entrée au préalable et vous assure toujours que chaque élément que vous rencontrez a une probabilité égale de se retrouver dansR (c'est-à-dire qu'il n'y a pas de biais). De plus, R contient un échantillon juste et représentatif des éléments que l'algorithme a pris en compte à tout moment. Cela signifie que vous pouvez l'utiliser comme un algorithme en ligne.
Pourquoi cela fonctionne-t-il?
McLeod et Bellhouse (1983) fournir une preuve en utilisant les mathématiques des combinaisons. C'est joli, mais ce serait un peu difficile de le reconstruire ici. Par conséquent, j'ai généré une preuve alternative qui est plus facile à expliquer.
Nous procédons par preuve par induction.
Disons que nous voulons générer un ensemble de s éléments et que nous avons déjà vu n>s éléments.
Supposons que nos éléments s actuels ont déjà été choisis avec Probabilité s/n.
Par la définition de l'algorithme, nous choisissons l'élément n+1 avec la probabilité s/(n+1).
Chaque élément déjà partie de notre jeu de résultats a une probabilité 1/s d'être remplacé.
La probabilité qu'un élément du jeu de résultats n-seen soit remplacé dans le jeu de résultats n+1-seen est donc (1/s)*s/(n+1)=1/(n+1). Inversement, la probabilité qu'un élément ne soit pas remplacé est 1-1/(n+1)=n/(n+1).
Ainsi, le jeu de résultats n+1-seen contient un élément soit s'il faisait partie du jeu de résultats n-seen et n'a pas été remplacé---cette probabilité est (s/n)*n/(n+1)=s/(n+1)---ou si l'élément a été choisi---avec une probabilité s/(n+1).
La définition de l'algorithme nous indique que les premiers s éléments sont automatiquement inclus en tant que premiers n=s membres du jeu de résultats. Par conséquent, l'ensemble de résultats n-seen inclut chaque élément avec une probabilité s/n (=1) nous donnant le cas de base nécessaire pour l'induction.
Références à
McLeod, A. Ian et David R. Bellhouse. "Un algorithme pratique pour dessiner un échantillon aléatoire simple."Journal of the Royal Statistical Society. Série C (Statistiques Appliquées) 32.2 (1983): 182-184. (Lien)
Vitter, Jeffrey S. "échantillonnage Aléatoire avec un réservoir."ACM Transactions sur les Logiciels de Mathématiques (TOMS) 11.1 (1985): 37-57. (Lien)
C'est ce qu'on appelle un problème d'échantillonnage de réservoir . La solution simple consiste à attribuer un nombre aléatoire à chaque élément de la liste tel que vous le voyez, puis à conserver les K éléments supérieurs (ou inférieurs) ordonnés par le nombre aléatoire.
Je suggère: trouvez D'abord vos k nombres aléatoires. Les trier. Ensuite, parcourez à la fois la liste liée et vos nombres aléatoires une fois.
Si vous ne connaissez pas la longueur de votre liste liée (comment?), vous pourriez saisir le premier k dans un tableau, puis pour le nœud r, générer un nombre au hasard dans [0, r), et si c'est inférieur à k, remplacer la rd point de la matrice. (Pas tout à fait convaincu que ne biaise pas...)
Autre que cela: "si j'étais toi, Je ne partirais pas d'ici." Êtes-vous sûr que la liste liée est bonne pour votre problème? N'y a-t-il pas une meilleure structure de données, comme une bonne vieille liste de tableaux plats.
Si vous ne connaissez pas la longueur de la liste, alors vous devrez la parcourir complète pour assurer des choix aléatoires. La méthode que j'ai utilisée dans ce cas est celle décrite par Tom Hawtin (54070). En parcourant la liste, vous conservez les éléments k qui forment votre sélection aléatoire jusqu'à ce point. (Au départ, vous ajoutez simplement les premiers éléments k que vous rencontrez.) Ensuite, avec probability k/i, vous remplacez un élément aléatoire de votre sélection par le i ème élément de la liste (c'est-à-dire le élément que vous êtes à, à ce moment-là).
Il est facile de montrer que cela donne une sélection aléatoire. Après avoir vu m éléments (m > k), nous avons que chacun des premiers m éléments de la liste font partie de votre sélection aléatoire avec une probabilité k/m. Que cela tient initialement est trivial. Ensuite, pour chaque élément m+1, vous le mettez dans votre sélection (en remplaçant un élément aléatoire) par probability k/(m+1). Vous devez maintenant montrer que tous les autres éléments ont également une probabilité k/(m+1) d'être sélectionnés. Nous avons que la probabilité est k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (c'est-à-dire la probabilité que cet élément soit dans la liste multiplié par la probabilité qu'il soit toujours là). Avec le calcul, vous pouvez montrer clairement que c'est égal à k/(m+1).
Eh bien, vous devez savoir ce que N est au moins à l'exécution, même si cela implique de faire un passage supplémentaire sur la liste pour les Compter. L'algorithme le plus simple pour ce faire est de simplement choisir un nombre aléatoire dans N et de supprimer cet élément, répété k fois. Ou, s'il est permis de retourner des numéros de répétition, ne retirez pas l'article.
Sauf si vous avez un très grand N, et des exigences de performance très strictes, cet algorithme s'exécute avec O(N*k) complexité, ce qui devrait être acceptable.
Modifier: Peu importe, la méthode de Tom Hawtin est bien meilleure. Sélectionnez d'abord les nombres aléatoires, puis parcourez la liste une fois. Même complexité théorique, je pense, mais beaucoup mieux attendu runtime.
Pourquoi ne pouvez-vous pas simplement faire quelque chose comme
List GetKRandomFromList(List input, int k)
List ret = new List();
for(i=0;i<k;i++)
ret.Add(input[Math.Rand(0,input.Length)]);
return ret;
Je suis sûr que vous ne voulez pas dire quelque chose d'aussi simple, alors pouvez-Vous spécifier plus loin?