J'ai une liste liée à une seule direction sans connaître sa taille.
Je veux obtenir un élément aléatoire dans cette liste et je viens d'avoir Quel est l'algorithme de ce problème? Merci!
4 Réponses :
Ceci est juste échantillonnage du réservoir avec un réservoir de taille 1.
essentiellement c'est vraiment simple
Ceci est uniformément échantillonné, car la probabilité de choisir n'importe quel élément à la fin de la journée est de 1 / N (exercice au lecteur).
@GiaComon est là une raison pour laquelle vous sentez que cela ne fonctionnera pas pour les petites collections. J'ai compris la question de fournir un algorithme d'échantillonnage uniforme en ligne, cela convient parfaitement à je pense
@Aurojit: Je pense que Giacomo dit simplement que cette solution est bonne pour les grandes et les petites collections.
@Giacomo merci, je ne me plaignais pas en réalité de votre commentaire, j'essayais simplement de trouver le problème, désolé si cela est sorti comme étant dur
Est-ce vraiment une probabilité de 1 / n? Prenez le dernier élément: il aura une chance de choisir 1/2 (dans la dernière étape), ainsi que le reste des éléments ont une somme de 1/2. Cela ne me semble pas juste.
@iuliux Pourquoi a-t-il une probabilité 1/2? L'élément lui-même a une chance d'être choisi. Si ce n'est pas choisi, aucun élément choisi est survivre avec la probabilité (n - 1) / n. (1 / N-1) = 1 / N. D'où une probabilité uniforme.
Ok, j'ai relu votre réponse et maintenant je l'ai eu, merci. (L'étape 2 est un peu ambiguë)
Ceci est probablement une question d'entretien.Reservoir Sampling est utilisé par les données scientifiques pour stocker des données pertinentes dans un stockage limité à partir de grand flux de données.
Si vous devez collecter des éléments K à partir de n'importe quel tableau avec des éléments N, de telle sorte que la probabilité de chaque élément collecté doit être identique (K / N), vous suivez deux étapes,
1) Stockez les premiers k éléments du stockage. 2) Lorsque l'élément suivant (K + 1) provient de votre flux, vous n'avez plus d'espace dans votre collection. Générer un nombre aléatoire de O à N, si le nombre aléatoire généré est inférieur à k Supposon L, remplacez le stockage [L ] avec l'élément (k + 1) du flux.
maintenant, revenez à votre question, la taille de stockage est 1.SO Vous choisirez le premier nœud, itérer sur la liste pour le deuxième élément.NOW générer le nombre aléatoire, si son 1, laissez l'échantillon seul. Élément de stockage de la liste
Cette question peut être effectuée à l'aide de l'échantillonnage du réservoir. Il est basé sur le choix de K articles aléatoires hors N articles, mais ici ne peut être très grand (qui ne doit pas correspondre à la mémoire!) Et (comme dans votre cas) Inconnu initialement.
La Wikipedia a une compréhension Algorithme que je cite ci-dessous: La question ne nécessite que 1 valeur pour que nous prenions k = 1. c implémentation:
C'est la manière la plus simple que j'ai trouvée, cela fonctionne bien et est compréhensible: