J'ai une liste d'articles. Lorsque je crée la liste, chaque élément a une chance égale à être sélectionnée. Mais comme un élément est sélectionné, sa chance diminue alors que les autres changent la chance. Si un nouvel élément est ajouté pendant le processus, il devrait avoir la plus grande chance d'être sélectionné avec ses chances qui tombent comme sélectionnées. Je cherche un bon algorithme qui peut accomplir ceci est C #.
idée généralisée: J'ai 5 articles, au fil du temps, les 5 articles seront sélectionnés 20% du temps. J'essaie de garder les sélections à proximité de 20% de plus que possible, réduisant les ailettes. Si l'on existe, il sera sélectionné plus / moins pour le ramener en ligne.
6 Réponses :
Vous pourriez faire quelque chose comme faire une classe personnalisée (pour votre liste), qui stocke l'article plus une pondération.
Par défaut la pondération à 1 lorsque vous ajoutez un élément, et le magasin (dans la « liste ») le total de toutes les pondérations de tous les éléments.
Vous pouvez ensuite, lorsque vous sélectionnez un élément au hasard, il suffit de choisir un nombre entre 0 -> pondérations au total de tous les éléments de la liste, et parcourir la liste pour trouver l'élément à cette « position » (par pondération) . Décrémenter la pondération de cet élément (cela peut être une falloff, à savoir: multiplier c'est la pondération de 0,8 ou 0,5 - vous auriez beaucoup de contrôle sur la vitesse il de probabilité de sélection tombe), et le retourner
L'inconvénient ici, si vous avez beaucoup d'articles, est que votre sélection est O (n) (puisque vous devez marcher à travers la liste). À cause de cela, je serais probablement utiliser une liste liée au stockage (vous allez devoir marcher pour la récupération de toute façon, donc cela vous donne plus rapide insertion / suppression).
Si vous n'êtes pas stocker un grand nombre d'options, cependant, ce serait très facile à mettre en œuvre, et vous donner beaucoup de contrôle sur les probabilités ainsi que la réduction de la probabilité au moment de la sélection.
Je serais probablement stocker du poids comme un entier, en commençant à 100 ou quelque chose, et décrémenter, si seulement pour rendre les cas d'indice arrondi plus évidents, mais c'était à peu près ma réponse aussi.
En plus de l'heure de récupération O (n), cet algorithme présente deux déficits supplémentaires (potentiels). 1) il nécessite un stockage de mémoire supplémentaire à mettre en œuvre, de stocker des poids., 2) Les éléments pondérés peuvent ne pas avoir la même probabilité d'être sélectionné même si elles ont le même poids car (comme décrit) l'algorithme trouve le premier élément avec un poids avec un poids Convient à la recherche.
Ouais, poids comme entier a du sens. C'est probablement une meilleure approche.
@Lbushkin: Je pensais en fait que vous choisiriez de 0-> Poids total et trouvez la position à cet indice, et non le premier élément qui a une probabilité spécifique. Vous auriez une chance égale de trouver un élément, par probabilité, de cette façon. Le stockage supplémentaire est un véritable inconvénient, cependant.
Si c'est un processus de course à long terme, que faites-vous lorsque les poids de tous les articles arrivent à 0? Stocker un entier supplémentaire par choix ne semble pas être un inconvénient majeur pour moi.
@DigitalJoel: C'est un avantage à mon approche originale en utilisant des valeurs de points flottants pour la pondération. Vous n'obtiendrez jamais une probabilité de 0 si vous échouez la pondération par un facteur.
Utilisez le temps écoulé car l'élément a été inséré ou la dernière sélection comme la priorité mofive ... Définissez chaque article de priorité = la durée car elle a été insérée ou la dernière sélection, puis ajustée, puis a la chance d'être sélectionné en multipliant par cette priorité.
Une fois que vous avez toutes les chances d'articles, les normalisez-les, (adjectez-les tous par le même rapport calculé pour les faire ajouter à 1 000), puis utilisez ces valeurs comme leur probabilité d'être sélectionnée.
Il ne voulait pas que des priorités tombent de temps, mais plutôt à quelle fréquence ils ont été sélectionnés. Comment utiliser le temps écoulé qui aidait cela?
Où dit-il ça? Il dit simplement que la chance devrait tomber lorsqu'il est sélectionné, pas par "combien de fois" il est sélectionné ...
Un moyen facile de mettre en œuvre est d'attribuer à chaque godet une gamme de valeurs et générer un nombre aléatoire dans la plage combinée pour choisir un godet à choisir parmi . Vous voudrez probablement résumer cette collection dans une sorte de classe de sorte que vous n'exposez pas les consommateurs aux détails. algorithme: initialement , tous les éléments commencent dans le même godet (de niveau supérieur). Lorsque vous sélectionnez un élément, déplacez-le du godet, c'est dans le seau inférieur suivant. Si nécessaire, créez le godet de niveau suivant. Lorsqu'un nouvel élément est ajouté, ajoutez-le au godet le plus (le plus fréquemment utilisé). Pour sélectionner un élément, d'abord Choisissez un seau, puis choisissez un élément dans le godet. Déplacez l'élément sélectionné dans le godet de niveau suivant. Remarque, qui déplaçant un élément sur un godet inférieur de fréquence est facultatif - vous pouvez définir un point de coupure. Lors de la création d'un nouveau godet, mettez à jour la plage de récupération associée à tous les godets pour donner à la nouvelle réglage de la fréquence. Caractéristique de distribution que vous voulez.
Je pense que cela est le plus proche des exigences du questionneur, pourquoi aucun vote?
J'aime l'idée de la structure de données encapsulant les règles. Bon travail.
Tout dépend de la manière dont la probabilité d'être sélectionnée devrait varier lorsqu'une élément donné est sélectionné.
Un moyen simple d'y parvenir est avec le double drawring, dans lequel vous commencez avec la liste d'entrée (qui ne change jamais) et une liste vide à laquelle vous ajoutez les éléments sélectionnés au hasard. Après chaque tirage normal (de la première liste), vous dessinez un élément de la deuxième liste. Si le même élément (ou une valeur plutôt sur l'élément) revient à nouveau, il n'est pas sélectionné (c'est-à-dire dessiner non valide, démarrer à nouveau), sinon les comptes de tirage et la valeur correspondante sont ajoutés à la deuxième liste.
Le concept général semble lié aux sources ergodiques.
DigitalJoe a commenté un inconvénient apparent à cette approche. En résumé, Joe a noté que la probabilité d'empêcher les répétitions répétitives (pas nécessairement consécutives, juste "répéter") d'une valeur d'élément préalablement dessinée (une valeur trouvée dans la deuxième liste de l'algorithme) fluctue grandement dans les premiers centaines de dessins . Un autre commentaire implicite a été que, une fois la deuxième liste contenant quelques dizaines de valeurs, la probabilité d'empêcher une telle duplication est extrêmement faible. Ce sont des points valides et nécessitent une qualification.
Ce raisonnement correspond à notre compréhension intuitive de la manière dont la deuxième liste fonctionne: plus il y a des valeurs d'éléments, les moins de chances que nous devons "doubler", donc pour éviter une répétition. Ceci est vrai, mais cela ne se concentre que sur la deuxième liste. La probabilité de dessiner [de la première liste] un élément précédemment observé doit être prise en compte. Nous pouvons utiliser deux exemples pour intuiter cette idée, mais ceci est bien sûr un gradient:
Dans les deux cas, ce qui compte, c'est que la répartition globale des dessins réels correspond à celle de la distribution dans la liste des intrants. Ceci est particulièrement vrai car le nombre de dessins devient plus statistiquement significatif .
sur la question de la possibilité d'avoir trop faible d'un filtre répété, cela devra également être moins pertinent car la deuxième liste reflète de plus en plus la distribution de la première liste. Peut-être qu'un moyen d'avoir une idée de tout cela est de prendre en compte des moyens alternatifs d'atteindre les objectifs décrits dans la question de l'OP.
D'une certaine manière, les deux algorithmes de liste que j'ai suggéré à l'origine (tirent avec le remplacement de la liste d'origine et gérer une deuxième liste pour empêcher parfois les répétitions) est similaire à l'algo 2, de la manière dont ils rend la distribution de dessin convergent vers celle de la liste d'origine. L'avantage de l'algorithme d'origine est cependant qu'il facilite la gestion des listes (bien que dans l'équité, un moyen simple de le faire est de remplacer les éléments dessinés avec une valeur «null» de TRES et de reconquérir une telle "Cellule vide", qui est effectivement la même chose, en sens inverse, de redessiner lorsque le dessin de la deuxième liste produit la même valeur d'article.)
Algo 1: Dessin sans remplacement de la première liste. Que nous utiliserions une copie de la liste d'origine pour commencer, et chaque fois qu'un article donné est dessiné, nous l'enlevions de cette liste, ce qui le rendait donc globalement moins probablement que la même valeur apparaisse à nouveau. Au moment où nous avons tiré tous les éléments, nous avons reproduit exactement la distribution de la liste d'origine.
Algo 2: dessin sans remplacement , à partir d'une liste où la liste d'origine
J'aime cette approche. Il s'occupe de la baisse des chances de sélection en tant qu'élément sélectionné et de supposer que vous mettez des doublons dans la liste précédemment dessinée, il réduit davantage les risques de sélection chaque fois qu'un élément est sélectionné. Un problème que je vois, c'est que la pénalité pour être choisie est considérablement réduite car le nombre de sélections est effectué. Sur le deuxième tirage au sort, les chances de répéter l'élément précédent sont de 0. Au 11ème tirage au sort, les chances de répéter l'élément précédent ne sont que de 10% moins susceptibles que d'obtenir un article précédemment non sélectionné. 1% au 101ème, etc.
@digitaljoe Je ne suivez pas exactement les chiffres que vous citez des probabilités. Néanmoins, on peut compenser ce problème en introduisant des tentatives supplémentaires pour disqualifier un tirage donné (c.-à-d. Dessin selon 3 ou 4 fois de la liste "précédemment dessinée"), il vient une fois (et cela varie avec le nombre d'éléments distincts, et avec leur probabilité d'être dessinée en premier lieu), lorsque la liste précédemment dessinée constitue un outil viable pour assurer la variabilité associée à des tirages individuels, tout en respectant la distribution souhaitée associée aux données)
Je ne suis pas un statisticien, mais voici ma pensée. Sur le premier tirage au sort, vous mettez l'article dans la liste 2. Au deuxième tirage, si vous dessinez à nouveau le premier élément, il s'agit de la seule option de la liste 2, il est donc automatiquement dessiné de la liste 2 et invalide le choix de la liste 1. Sur le 11ème tirage au sort, la liste 2 dispose désormais de 10 éléments de 10% seulement de choisir l'article de la liste 2 choisis lors de l'essai précédent de la liste 1, de sorte que la chance d'invalider le tirage au sort, même si elle Est-ce que le même article qui a été dessiné précédemment n'est que de 10%, et non les 100% que nous avions dans le tirage 2.
@digitaljoe. Votre raisonnement est correct, en partie, voir mon [long] modifier dans le texte, ce qui montre comment les grandes variations de la probabilité de filtrer les valeurs d'élément de sortie des premières étapes du dessin n'affectent pas la capacité de l'algorithme de produire des dessins qui sont "true" à la distribution trouvée dans la liste orginale.
La stratégie générale de cueillette d'un élément aléatoire pondéré à partir d'une liste est la suivante: donner à chaque élément un poids. Normaliser, de sorte que le poids total est 1. (Pour commencer, chaque élément a du poids 1 / N). Triez votre liste en poids. Choisissez maintenant un nombre aléatoire entre 0 et 1 et descendre la liste accumulant des totaux jusqu'à ce que vous traversiez votre numéro. par exemple. Si vos poids sont [0,4, 0,3, 0,2, 0,1] et votre nombre aléatoire sont de 0,63215, vos deux premières étapes ont total = 0,4, total = 0,7, puis remarquez que 0,7 est supérieur à 0,63215 afin de retourner le deuxième élément.
Une fois que vous choisissez un élément, vous ajustez sa pondération vers le bas (vous aurez besoin d'expérimenter des formules en baisse avant de trouver un qui vous convient, le plus simple est simplement de la multiplier par une fraction constante à chaque fois), puis renormaliser et répéter.
Notez que cela est assez inefficace si vous avez un lot d'éléments puisqu'il s'agit de O (n) dans la longueur de la liste, mais cela ne devrait pas avoir d'importance en pratique, à moins que vous ne le faisiez Ceci dans une boucle interne qui doit être fortement optimisée, ou similaire. S'il s'avère être un problème, vous pouvez regarder dans des structures de données géométriques telles que des arbres de plage pour optimiser la recherche.
Ici, nous allons ingénieur un générateur de nombres aléatoires qui a une distribution qui favorise les valeurs faibles. Vous pouvez l'utiliser pour préférer les articles au début d'une liste. Pour diminuer les chances de quelque chose d'être sélectionné, déplacez cet élément dans la liste. Vous avez quelques options pour la manière dont vous souhaitez déplacer l'élément dans la liste. Permet de passer en revue la transformation variable aléatoire d'abord.
En appliquant la fonction suivante à une variable aléatoire uniforme entre 0 et 1: p> Vous obtenez une distribution froide qui réduit considérablement la Cotes d'un index plus grand p> Voici la distribution d'une liste de taille 2 p> taille 3 p > toend strong> - déplacer le plus récemment article sélectionné à la fin de la liste p> li>
Sort fort> - Gardez une matrice associée du nombre de fois que chaque élément a été sélectionné et trier la liste de la moins à la plupart sélectionnée. P> li>
ul> J'ai créé une simulation à choisir dans une liste et examinez l'écart type du nombre de comptes que chaque élément a été sélectionné. Plus le déviation type est inférieur. Par exemple, 1 simulation pour une liste de 10 éléments où 50 sélections utilisées ont créé la propagation: p> la dévation standard de cette simulation était p> Avec la possibilité d'exécuter une simulation, j'ai ensuite calculé certaines méta-statistiques en exécutant la simulation 500 fois et en fournissant l'écart type moyen pour chaque méthode: Toind et Trier. Je m'attendais à ce que l'écart-type soit élevé pour un nombre bas de choix, mais en fait pour l'algorithme de TOEND, l'écart type augmentait avec le nombre de pics. La méthode de tri fixe ceci. P> Voici quelques résultats de test pour un ensemble plus grand. P> StdDev = 0.632455532033676
{"a"=>10, "b"=>10, "c"=>11, "d"=>9, "e"=>10}
a d e c b c e b a d b e c a d d e b a e e c c b d a d c b c e b a a d d b e a e a b c b d c a c e c
StdDev = 0.0
{"a"=>10, "b"=>10, "c"=>10, "d"=>10, "e"=>10}
b c d a a d b c b a d e c d e c b e b a e e d c c a b a d a e e b d b a e c c e b a c c d d d a b e
StdDev = 0.632455532033676
{"a"=>9, "b"=>10, "c"=>10, "d"=>10, "e"=>11}
b d a e b c a d c e e b a c a d d c b c e d a e b b a c d c d a e a e e b d c b e a b c b c d d e e
StdDev = 0.0
{"a"=>10, "b"=>10, "c"=>10, "d"=>10, "e"=>10}
a b e d c e a b d c b c c a d b e e b e a d d c e a d b b c c a a a b e d d e c c a b b e a c d e d
StdDev = 0.632455532033676
{"a"=>11, "b"=>10, "c"=>9, "d"=>10, "e"=>10}
b a d c d c a e b e a e b c d b c a a d e e d c d e c b a b b e d c d b c e a a a d b c e b e a d a
Testing ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
-------------------------
Picks ToEnd (StdDev) Sort (StdDev)
10 0.68 0.65
20 0.87 0.77
30 1.04 0.80
40 1.18 0.82
50 1.30 0.85
60 1.43 0.84
70 1.57 0.87
80 1.65 0.88
90 1.73 0.87
90 1.71 0.87
160 2.30 0.89
250 2.83 0.88
360 3.44 0.88
490 3.89 0.88
640 4.54 0.87
810 5.12 0.88
1000 5.66 0.85
Que faites-vous avec l'article lorsque vous "sélectionnez"? Courir? le traitement? la mettre dans une file d'attente? Peut-il être sélectionné plus d'une fois? Est-ce que cela devient "non sélectionné" à un moment donné après sa sélection? I.e .. est quelque chose qui se passe à l'article alors qu'il est sélectionné que "finitions"? Si tel est le cas, d'autres éléments peuvent-ils être sélectionnés avant qu'un élément actuellement sélectionné "se termine" et "non sélectionné"?
Une copie de l'élément est renvoyée mais non supprimée de la liste. Il est possible que l'article puisse être retourné à la demande arrière. Les articles ne peuvent pas être supprimés en courant, il suffit d'ajouter. Vous pouvez faire autant de choix que vous le souhaitez, seul changé serait la probabilité d'être sélectionnée.
@Thad, alors si une chance d'être sélectionnée est-elle dépendante du moment où elle a été sélectionnée?, Sur combien de fois il a été sélectionné? ou sur une combinaison des deux? C'est-à-dire si un article a été sélectionné il y a 5 fois il y a un an, cela signifie-t-il que cela a moins de probabilité que celui qui a été sélectionné il y a une fois il y a une heure?
Je n'ai donné aucune pensée à l'aspect temporel, car le processus de sélection se produira fréquemment. Les éléments qui n'ont pas été sélectionnés dans un moment doivent constituer une chance plus élevée et être sélectionnés. Mais il peut être nécessaire de prendre en compte le temps, n'a pas été tenu à propos de cette possibilité.
Disons qu'il y ait initialement 4 articles et ont réalisé une répartition de 25%. Que se passe-t-il si un autre élément est ajouté? La distribution devient-elle progressivement 20% chacune? Si le nouvel élément cible pour un pourcentage plus faible car sa vie est plus courte que d'autres?
Les pourcentages de tous les articles seraient ajustés et le nouvel élément aurait presque 100% de chances de sélection. Au fil du temps, il résumerait à 20%