Efficacement la sélection d'un ensemble d'éléments aléatoires à partir d'une liste liée

Question

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 le plus efficacement possible d'écrire une fonction qui sera de retour k complètement nombres aléatoires à partir 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 par vous donner son l'histoire:

Knuth les appels de cet Algorithme 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) les 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 pseudocode 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 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 il encore qui vous assure que chaque élément que vous rencontrez a une probabilité égale de se retrouver dans 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 certains é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é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 la n-vu ensemble de résultats est remplacé, dans le n+1-vu de résultat est donc (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 les éléments sont automatiquement inclus en tant que la première n=s les 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."L'échantillonnage aléatoire avec un réservoir". ACM Transactions sur les Logiciels de Mathématiques (TOMS) 11.1 (1985):37-57.(Lien)

Answer 2

Ceci est appelé un Réservoir D'Échantillonnage problème.La solution la plus simple est d'attribuer un nombre aléatoire à chaque élément de la liste que vous le voyez, puis maintenir le haut (ou le bas) k éléments commandés par le nombre aléatoire.

Answer 3

Je vous 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).Tout en parcourant la liste vous garder k les éléments qui constituent votre sélection aléatoire à ce point.(Initialement, il suffit d'ajouter la première k les éléments que vous rencontrez.) Puis, avec une probabilité de k/i, vous devez remplacer un élément au hasard dans votre sélection avec la ième élément de la liste (c'est à direl'élément que vous êtes, à ce moment-là).

Il est facile de montrer que ce donne une sélection aléatoire.Après l'avoir vu m éléments (m > k), nous avons, chacun de la première m les é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 à direla probabilité que cet élément est dans la liste fois la probabilité qu'il est toujours là).Avec le calcul, vous pouvez simplement montrer que ce qui est égal à k/(m+1).

Answer 5

Eh bien, vous avez besoin de savoir ce qui N est au moment de l'exécution, au moins, même si cela implique de faire un supplément de passer au-dessus de la liste pour les compter.Le plus simple algorithme à faire est de choisir un nombre au hasard dans N et supprimer cet élément répété k fois.Ou, s'il est autorisé à retourner répéter les numéros de ne pas supprimer l'élément.

Sauf si vous avez un TRÈS grand N, et de très strictes exigences de performance, cet algorithme s'exécute avec O(N*k) la complexité, ce qui devrait être acceptable.

Edit:Tant pis, Tom Hawtin méthode est beaucoup mieux.La sélection au hasard des numéros d'abord, puis la traversée de la liste une fois.Même théorique de la complexité, je pense, mais beaucoup mieux attendus de l'exécution.

Answer 6

Pourquoi ne pouvez-vous pas tout 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 veux pas dire quelque chose d'aussi simple alors pouvez-vous préciser?