Ajustez les réglages de chance d'être sélectionné dans une liste
https://stackoverflow.com/questions/1589321
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai une liste d'éléments. Lorsque je crée la liste chaque élément a les mêmes chances d'être sélectionné. Mais comme un élément est sélectionné ses chances diminue tandis que les autres chances monte. Si un nouvel élément est ajouté au cours du processus, il devrait avoir la plus grande chance d'être sélectionné avec ses chances de tomber car il est sélectionné. Je cherche un bon algorithme qui peut accomplir cela est C #.
idée Generalizaed: J'ai 5 articles, au fil du temps l'ensemble des 5 articles seront sélectionnés 20% du temps de temps. Je suis en train de garder les sélections d'un proche de 20% que possible, en réduisant les déviants. Si l'on existe, il sera sélectionné plus / moins pour le ramener en ligne.
La solution
Ici, nous allons concevoir un générateur de nombres aléatoires qui a une distribution qui favorise des valeurs faibles. Vous pouvez l'utiliser pour préférer les éléments au début d'une liste. Pour diminuer les chances de quelque chose étant sélectionné, déplacer cet élément dans la liste. Vous avez quelques options pour la façon dont vous voulez déplacer l'élément dans la liste. Revoyons la transformation variable aléatoire première.
En appliquant la fonction suivante à une variable aléatoire uniforme entre 0 et 1:
index = Int(l*(1-r^(0.5)) # l=length, r=uniform random var between 0 and 1
Vous obtenez une distribution cool qui réduit considérablement les chances d'un indice plus grand
p(0)=0.09751
p(1)=0.09246
p(2)=0.08769
p(3)=0.08211
p(4)=0.07636
p(5)=0.07325
p(6)=0.06772
p(7)=0.06309
p(8)=0.05813
p(9)=0.05274
p(10)=0.04808
p(11)=0.04205
p(12)=0.03691
p(13)=0.03268
p(14)=0.02708
p(15)=0.02292
p(16)=0.01727
p(17)=0.01211
p(18)=0.00736
p(19)=0.00249
Voici la distribution pour une liste de taille 2
0.75139
0.24862
Taille 3
0.55699
0.33306
0.10996
Taille 4
0.43916
0.31018
0.18836
0.06231
Maintenant abordons les deux options pour déplacer les éléments dans la liste. Je l'ai testé deux:
-
ToEnd - Déplacer l'élément le plus récemment sélectionné pour la fin de la liste
-
Trier -. Gardez un tableau associé du nombre de fois que chaque élément a été sélectionné et trier la liste du moins au plus sélectionné
J'ai créé une simulation pour choisir parmi une liste et d'examiner l'écart-type du nombre que chaque élément a été sélectionné. Plus l'écart-type le mieux. Par exemple, 1 simulation pour une liste de 10 articles où 50 sélections où fait a créé la diffusion:
{"a"=>5, "b"=>5, "c"=>6, "d"=>5, "e"=>4, "f"=>4, "g"=>5, "h"=>5, "i"=>6, "j"=>5}
Le Devation standard pour cette simulation était
0.63
Avec la possibilité d'exécuter une simulation, je calcule ensuite des méta-statistiques en exécutant la simulation 500 fois et en fournissant l'écart-type moyen pour chaque méthode: ToEnd et Trier. Je me attendais à l'écart-type à être élevé pour une faible nombre de choix, mais en fait pour l'algorithme ToEnd l'écart-type augmente avec le nombre de choix. La méthode de tri fixe cela.
Testing ["a", "b", "c", "d", "e"]
-------------------------
Picks ToEnd (StdDev) Sort (StdDev)
5 0.59 0.57
10 0.76 0.68
15 0.93 0.74
20 1.04 0.74
25 1.20 0.73
30 1.28 0.73
35 1.34 0.74
40 1.50 0.75
45 1.53 0.75
45 1.56 0.77
80 2.04 0.79
125 2.52 0.74
180 3.11 0.77
245 3.53 0.79
320 4.05 0.75
405 4.52 0.76
500 5.00 0.78
Voici quelques résultats des tests pour un ensemble plus large.
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
Avec un bon cadre de test, je ne pouvais pas résister à essayer une autre transformation de nombres aléatoires. Mon hypothèse était si je prends la racine cubique au lieu de la racine carrée de x que mon écart-type diminuerait. Il a en fait, mais je craignais que cela diminuerait le caractère aléatoire. Ici vous pouvez observer quelques simulations lorsque la formule est modifiée pour
index = Int(l*(1-r^(0.33)) # l=length, r=uniform random var between 0 and 1
inspecter les choix réels. Comme je le pensais, il est très pondéré au début de la liste au début. Si vous voulez poids ce fortement, vous devriez probablement votre liste randomiser avant de commencer.
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
Autres conseils
Utiliser une file d'attente pondérée en seau: Au lieu d'utiliser une liste, divisez votre collection dans des seaux - chaque seau a une fréquence associée de recherche. Les produits se déplacent des seaux de fréquences plus élevées pour abaisser les fréquences de leur sélection.
Un moyen facile à mettre en œuvre est d'attribuer à chaque seau une plage de valeurs, et de générer un nombre aléatoire dans la gamme combinée de choisir un seau à choisir. Vous aurez probablement envie de faire abstraction de cette collection dans une sorte de classe afin que vous ne pas exposer les consommateurs aux détails.
Algorithme:
Dans un premier temps, tous les éléments commencent dans le seau même (de haut niveau).
Lorsque vous sélectionnez un élément, déplacez-le dans le seau, il est dedans, à l'autre seau inférieur. Si nécessaire, créez le seau niveau suivant.
Quand un nouvel élément est ajouté, l'ajouter au plus haut sommet seau (le plus utilisé).
Pour sélectionner au hasard un élément, d'abord choisir un seau, puis choisissez un élément dans le seau. Déplacer l'élément sélectionné vers le bas dans le seau niveau suivant. Notez que le déplacement d'un élément vers le bas dans un seau de fréquence inférieure est en option -. Vous pouvez définir un point de coupure
Lors de la création d'un nouveau seau, mettez à jour la gamme de récupération associée à tous les godets pour donner le nouvel ensemble la caractéristique de distribution de fréquence souhaitée.
C mise en œuvre de # (première coupe) d'une file d'attente pondérée buckets générique:
using System;
using System.Collections.Generic;
using System.Linq;
namespace Utility
{
public class BucketWeightedQueue<T>
{
private int m_MaxFallOff;
private readonly double m_FallOffRate;
private readonly List<List<T>> m_Buckets;
private readonly List<int> m_FallOffFactors;
private readonly Random m_Rand = new Random();
public BucketWeightedQueue(IEnumerable<T> items, double fallOffRate )
{
if( fallOffRate < 0 )
throw new ArgumentOutOfRangeException("fallOffRate");
m_MaxFallOff = 1;
m_FallOffRate = fallOffRate;
m_Buckets = new List<List<T>> { items.ToList() };
m_FallOffFactors = new List<int> { m_MaxFallOff };
}
public T GetRandomItem()
{
var bucketIndex = GetRandomBucketIndex();
var bucket = m_Buckets[bucketIndex];
var itemIndex = m_Rand.Next( bucket.Count );
var selectedItem = bucket[itemIndex];
ReduceItemProbability( bucketIndex, itemIndex );
return selectedItem;
}
private int GetRandomBucketIndex()
{
var randFallOffValue = m_Rand.Next( m_MaxFallOff );
for (int i = 0; i < m_FallOffFactors.Count; i++ )
if( m_FallOffFactors[i] <= randFallOffValue )
return i;
return m_FallOffFactors[0];
}
private void ReduceItemProbability( int bucketIndex, int itemIndex )
{
if( m_FallOffRate <= 0 )
return; // do nothing if there is no fall off rate...
var item = m_Buckets[bucketIndex][itemIndex];
m_Buckets[bucketIndex].RemoveAt( itemIndex );
if( bucketIndex <= m_Buckets.Count )
{
// create a new bucket...
m_Buckets.Add( new List<T>() );
m_MaxFallOff = (int)(m_FallOffFactors[bucketIndex] / m_FallOffRate);
m_FallOffFactors.Add( m_MaxFallOff );
}
var nextBucket = m_Buckets[bucketIndex + 1];
nextBucket.Add( item );
if (m_Buckets[bucketIndex].Count == 0) // drop empty buckets
m_Buckets.RemoveAt( bucketIndex );
}
}
}
Tout dépend comment le probablility d'être sélectionnée devrait varier lorsqu'un élément donné obtient sélectionné.
Une façon simple d'y parvenir est avec double drawring, par 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 article (ou plutôt valeur de l'élément) revient à nouveau, il n'est pas sélectionné (par exemple tirage invalide, recommencer à zéro), sinon le tirage compte et la valeur correspondante est ajoutée à la seconde liste.
Le concept général semble lié à des sources ergodiques.
DigitalJoe commenté un inconvénient évident de cette approche. En un mot, Joe a noté que la probabilité d'empêcher les répéter (pas nécessairement répétitions consécutives, juste « répéter ») d'une valeur d'élément précédemment dessiné (une valeur trouvée dans la deuxième liste de l'algorithme) varie considérablement dans les premières centaines de dessins . Un autre commentaire implicite est que, après la deuxième liste contient quelques valeurs douzaine, la probabilité d'éviter une telle duplication est extrêmement faible. Ce sont les deux points valables et exigent la qualification.
Ce raisonnement correspond à notre compréhension intuitive de la façon dont la deuxième liste fonctionne: les valeurs plus d'articles sont là, les moins de chances que nous avons à « double tirage », donc pour éviter une répétition. Cela est vrai, mais il se concentre uniquement sur la deuxième liste. La probabilité d'obtenir [de la première liste] un élément vu précédemment doit être prise en compte. Nous pouvons utiliser deux exemples pour Intuit cette idée, mais cela est bien sûr un gradient:
- Cas « A »: la probabilité d'obtenir une valeur de l'élément donné est relativement faible par rapport à la probabilité d'obtenir autre chose. La probabilité combinée de dessiner cet objet à plusieurs reprises au cours des premiers dessins est donc faible, et la probabilité de le faire et de le jeter en raison du dessin (s) dans la liste deux est encore plus faible (même si cette dernière probabilité peut être élevé, en raison du petit nombre d'élément dans la deuxième liste).
- cas « B »: la probabilité d'obtenir un élément donné est élevé par rapport à la probabilité d'obtenir d'autres éléments. Dans ce cas, la probabilité d'avoir des répétitions dans les premiers tirages est élevée, et que la probabilité d'éviter une répétition réelle (avec le dessin de la seconde liste) est élevée également (une certitude pour le deuxième dessin, un 50% de chance sur le deuxième dessin ... une chance de 10% sur le 11 dessin), la probabilité globale de « punir » un élément hautement probable est élevé. Ceci est cependant pas un problème, car la probabilité relative à attirer l'élément de la première liste veillerai à ce qu'il y aura, statistiquement, beaucoup d'autres occasions de produire des doublons qui ne sera pas si « avec force » refusés comme le nombre de dessins progresse .
Dans les deux cas, ce qui importe est que la répartition globale des dessins réels correspond à celle de la distribution dans la liste d'entrée. Cela est particulièrement vrai que le nombre de dessins devient plus statistiquement significative.
Sur la question de la possibilité d'avoir trop faible d'un filtre à répétition, que trop obtient d'être moins pertinente que la seconde liste reflète de plus en plus de la distribution de la première liste. Peut-être un moyen d'obtenir une idée de tout cela est d'envisager d'autres moyens d'atteindre les objectifs décrits dans la question de l'OP.
algorithmes alternatifs :
Algo 1: Dessin sans remplacement de la première liste. Que nous utiliserions une copie de la liste initiale pour commencer, et à chaque fois un élément donné est tiré, nous aimerions le retirer de cette liste, ce qui rend ce que la même valeur globale moins probablement se présenteraient à nouveau. Au moment où nous « d dessiné tous les éléments, nous avions Reproduced exactement la distribution de la liste initiale.
Algo 2: Dessin sans remplacement , à partir d'une liste où le liste originale a été reproduit un certain nombre de fois . Ceci est similaire à ce qui précède, mais introduit un peu plus aléatoire, à savoir en exigeant un plus grand nombre de dessins d'avoir des dessins approche distrubution et correspondre à celle de la liste initiale.
D'une certaine manière, les deux algorithme de liste je l'ai suggéré à l'origine (tirage avec le remplacement de la liste originale et gérer une deuxième liste pour éviter parfois des répétitions) est similaire à Algo 2, de la façon dont ces rend la distribution de dessin convergent vers celui de la liste originale. L'avantage de l'algorithme original cependant, est qu'il rend la gestion des listes plus facile (même si, en toute équité un moyen simple de le faire est de remplacer les éléments dessinés avec une valeur « nulle » de toutes sortes, et redessiner ensuite frapper un tel « cellule vide », qui est en fait la même chose, à l'inverse, à redessiner lorsque le dessin dans la seconde liste produit la même valeur de l'élément ..)
Vous pouvez 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 est une pondération de 0,8 ou 0,5 - vous auriez beaucoup de contrôle sur la vitesse, il est la probabilité de sélection tombe off), 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.
Utilisez le temps écoulé depuis l'élément a été inséré ou le dernier sélectionné comme mofifier prioritaire ... Définir chaque élément priority = quantité de temps depuis qu'il a été inséré ou le dernier sélectionné, puis l'ajuster est la chance d'être sélectionné en multipliant par cette priorité.
Une fois que vous avez tous les éléments chances, les normaliser, (adjsut tous par le même rapport calculé pour les amener tous à ajouter à 1.000), puis d'utiliser ces valeurs comme leur probabilité d'être sélectionné.
la stratégie générale pour choisir 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 égal à 1. (donc au début, chaque élément a un poids de 1 / n). trier votre liste en poids. maintenant choisir un nombre aléatoire entre 0 et 1, et descendre la liste d'accumuler les totaux jusqu'à ce que vous traversez votre numéro. par exemple. si les poids sont [0,4, 0,3, 0,2, 0,1] et le nombre aléatoire est 0,63215, les deux premières étapes ont totale = 0,4, total = 0,7 et notez que 0,7 est supérieur à 0,63215 afin de renvoyer le second élément.
une fois que vous choisissez un élément, vous ajustez la pondération vers le bas (vous aurez besoin d'expérimenter des formules de downweighting jusqu'à ce que vous trouviez celui qui fonctionne pour vous, le plus simple que de le multiplier par une fraction constante à chaque fois), puis et répéter normaliser de.
Notez que ceci est assez inefficace si vous avez un beaucoup d'éléments puisqu'il est O (n) de la longueur de la liste, mais il ne devrait pas d'importance dans la pratique, à moins que vous faites ceci dans une boucle interne qui doit être fortement optimisé, ou similaire. si elle se révèle être une question que vous pourriez regarder dans les structures de données géométriques comme des arbres de gamme pour optimiser la recherche.
