Sélection efficace d'un ensemble d'éléments aléatoires dans une liste chaînée

Question

Disons que j'ai une liste chaînée de nombres de longueur N. N est très grande et je ne connais pas à l'avance la valeur exacte de N.

Comment puis-je écrire le plus efficacement possible une fonction qui retournera k nombres complètement aléatoires de la liste?

Answer 1

Il y a une très belle et algorithme efficace pour cela à l'aide d'une méthode appelée réservoir d'échantillonnage.

Permettez-moi de commencer en vous donnant son histoire:

Knuth appelle cela un Algorithme de R sur p. 144 de son édition de 1997 de Seminumerical Algorithmes (volume 2 de The Art of Computer Programming), et fournit un code pour cela. Knuth attributs de l'algorithme d'Alan G. Waterman. Malgré une longue recherche, je n'ai pas été en mesure de trouver Waterman document d'origine, si elle existe, ce qui peut être la raison pour laquelle vous aurez le plus souvent voir Knuth cité comme la source de cet algorithme.

McLeod et Bellhouse, 1983 (1) fournir une discussion plus approfondie de Knuth ainsi que le premier publié la preuve (que je connais) que l'algorithme fonctionne.

Vitter 1985 (2) examens de l'Algorithme de R et présente ensuite les trois autres algorithmes qui fournissent le même résultat, mais avec une torsion. Plutôt que de faire un choix d'inclure ou ignorer chaque élément entrant, son algorithme détermine le nombre de nouveaux éléments pour être ignorée. Dans ses essais (ce qui, certes, ne sont pas à jour maintenant) cette diminution du temps d'exécution de façon spectaculaire en évitant la génération de nombres aléatoires et des comparaisons sur chaque de numéro.

Dans le pseudo-code de l'algorithme est:

Let R by 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 précisément écrit le code pour éviter de spécifier la taille de l'entrée. C'est l'une des cool propriétés de cet algorithme: vous pouvez l'exécuter sans avoir besoin de connaître la taille de l'entrée à l'avance et encore vous assure que chaque élément que vous rencontrez a une probabilité égale de se retrouver en R (qui est, il n'y a pas de parti pris). En outre, R contient une juste et de l'échantillon représentatif de l'ensemble des éléments de l'algorithme a examiné en tout temps. Cela signifie que vous pouvez l'utiliser comme un algorithme en ligne.

Pourquoi ce travail?

McLeod et Bellhouse (1983) de fournir une preuve en utilisant les mathématiques de combinaisons. C'est joli, mais il pourrait être un peu difficile de reconstruire ici. Donc, j'ai généré une preuve alternative qui est plus facile à expliquer.

Nous procédons par une 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 notre actuel s des éléments ont déjà été choisis avec le plus de probabilité s/n.

Par la définition de l'algorithme, nous avons choisi l'élément n+1 avec une 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 de l' n-vu ensemble de résultats est remplacé dans l' n+1-vu de résultat est, par conséquent, (1/s)*s/(n+1)=1/(n+1). À l'inverse, la probabilité qu'un élément n'est pas remplacé est - 1-1/(n+1)=n/(n+1).

Ainsi, l' n+1-vu ensemble de résultats contient un élément que ce soit s'il faisait partie de l' n-vu ensemble de résultats 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 dit que la première s des éléments sont automatiquement inclus dès la première n=s des membres de l'ensemble de résultats. Par conséquent, l' n-seen résultat inclut chaque élément avec s/n (=1) probabilité de nous donner le nécessaire de base pour l'induction.

Références

1. McLeod, A. Ian, et David R. Bellhouse. "Une pratique de l'algorithme de dessin d'un échantillon aléatoire simple." Journal of the Royal Statistical Society. Série C (Statistiques Appliquées) 32.2 (1983): 182-184. (Lien)

2. 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)

Answer 2

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 premiers (ou derniers) éléments ordonnés par le nombre aléatoire.

Answer 3

Je suggère: d'Abord trouver votre k de nombres aléatoires. Les trier. Puis traverse à la fois la liste, et vos nombres aléatoires une fois.

Si vous ne connaissez pas la longueur de votre liste chaînée (comment?), ensuite, vous pouvez attrapez la première 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 qui n'a pas de biais...)

Autre que cela: "Si j'étais vous, je ne serais pas commencer à partir d'ici." Êtes-vous sûr de liste chaînée est bon pour votre problème? N'est-il pas une meilleure structure de données, comme un bon vieux plat de tableau liste.

Answer 4

Si vous ne connaissez pas la longueur de la liste, alors vous aurez à traverser pour s'assurer aléatoire de la pioche). La méthode que j'ai utilisé dans ce cas est celle décrite par Tom Hawtin (54070). En parcourant la liste, vous gardez k les éléments qui constituent votre sélection aléatoire à ce point. (Initialement, il suffit d'ajouter le premier k que vous rencontrez.) Puis, avec une probabilité de k/i, le remplacement d'un élément aléatoire à partir de votre sélection avec l' ième élément de la liste (c'est à dire l'élément que vous êtes, à ce moment-là).

Il est facile de montrer que ce donne une sélection aléatoire. Après avoir vu m éléments (m > k), nous avons, chacun de la première m des éléments de la liste sont partie de vous, une sélection aléatoire avec une probabilité k/m. Que cette d'abord détient, est trivial. Ensuite, pour chaque élément, m+1, vous le mettez dans votre sélection (remplacement d'un élément aléatoire) avec une probabilité k/(m+1). Maintenant, vous avez besoin de montrer que tous les autres éléments ont également une probabilité k/(m+1) d'être sélectionné. Nous avons que la probabilité est - k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (c'est à dire la probabilité que l'élément est dans la liste fois la probabilité qu'il est toujours là). Avec le calcul, vous pouvez simplement montrer que ce n'est égal à k/(m+1).

Answer 5

Une implémentation C ++ et un autre déguisement du même problème (flux de données infini).