Je recherche l'algorithme le plus efficace pour choisir un ensemble de n entiers distincts, où tous les entiers sont dans une certaine distance [0..maxvalue].
contraintes:
Mon idée initiale était de construire une liste des entiers [0..maxvalue] puis d'extraire n éléments au hasard sans remplacement. Mais cela semble assez inefficace, surtout si Maxvalue est grand.
De meilleures solutions?
8 Réponses :
Pour de petites valeurs de maxvalue de manière à ce qu'il soit raisonnable de générer une matrice de tous les entiers en mémoire, vous pouvez utiliser une variation du Fisher-Yates Shuffle sauf uniquement effectuer le premier si si Voici un autre algorithme plus simple mais a une durée d'exécution potentiellement sans bornes:
En pratique si N étapes.
n est beaucoup plus petit que maxvalue et vous ne souhaitez pas générer l'ensemble de la matrice, vous pouvez utiliser cet algorithme:
l du nombre cueilli jusqu'à présent, initialement vide.
x entre 0 et Maxvalue - (éléments dans l )
l s'il est inférieur ou égal à x , ajoutez 1 à x
x dans la liste triée et répétez.
n est très proche de maxvalue alors vous pouvez choisir au hasard les éléments qui ne sont pas dans le résultat, puis trouver le complément de cet ensemble.
S de l'élément cueilli jusqu'à présent, initialement vide.
Maxvalue .
s , ajoutez-le à s .
s a n éléments.
n est petit et maxvalue est grand que cela sera assez bon pour la plupart des objectifs.
Je ne sais pas si je comprends votre algorithme correctement. Supposons que maxvalue est 1000. Si j'ai {1,4} dans la liste et la fonction aléatoire renvoie 3 , donc j'ajouter 1 Il y a un élément qui est inférieur à 3 . Maintenant, j'ai {1,4,4}. Désolé si j'ai mal compris.
@tia: il signifie, pour (l dans la liste) si (l <= x) ++ x; . Ainsi, une fois que vous avez incrémenté x une fois, car "1" est dans la liste, vous l'incrémenterez à nouveau, car "4" est dans la liste, ce qui a entraîné 5.
La première approche utilise l'espace proportionnelle à la maxvalue. Le second est O (n ^ 2) temps. Le troisième a une durée de fonctionnement attendue raisonnable (O (N log n), mais elle n'est pas limitée dans le pire des cas, comme vous l'avez dit. Voir ma réponse, qui offre une solution d'espace linéaire / temps en n.
Un moyen de le faire sans générer le tableau complet.
dis que je veux un sous-ensemble sélectionné au hasard de m d'éléments d'un ensemble {x1, ..., xn} où m <= n.
considérer l'élément x1. J'ajoute x1 à mon sous-ensemble avec probabilité m / n.
mousser, rincer et répéter jusqu'à m = 0.
Cet algorithme est O (n) où n est le nombre d'articles que je dois envisager.
J'imagine plutôt qu'il y a un algorithme O (m) où vous déterminez à chaque étape que vous considérez combien d'éléments à éliminer du "front" de l'ensemble des possibilités, mais je ne me suis pas convaincu d'une bonne solution et j'ai faire du travail maintenant!
J'aime beaucoup cette idée ... surtout s'il est possible de sauter des éléments à l'avant pour donner la bonne distribution!
Si vous sélectionnez S'ils sont de taille similaire, vous passez à travers chaque élément de Si, d'autre part, Ce sont à la fois de telles méthodes simples que vous pouvez simplement implémenter - en supposant que vous ayez accès à un arbre trié - et choisissez celui qui convient à la fraction des nombres qui seront cueillis.
(Notez que les numéros de sélection sont symétriques sans les choisir, donc si m des éléments de n , la stratégie change en fonction de la question de savoir si m est du même ordre que N ou beaucoup moins (c'est-à-dire moins de n / journal n).
1 à n . Vous gardez une trace du nombre d'éléments que vous avez jusqu'à présent (appelons que m choisis par n que vous avez passé), puis vous prenez la Numéro suivant avec probabilité (mm) / (nn) et le jeter autrement. Vous mettez ensuite à jour m et n de manière appropriée et continue. Ceci est un algorithme O (n) avec un coût constant faible.
m est significativement inférieur à n , une stratégie de rééchantillonnage est une bonne. Ici vous voudriez trier m afin que vous puissiez les trouver rapidement (et cela vous coûtera O (m journal) TEMPS - Collez-les dans un arbre, par exemple ). Maintenant, vous choisissez des nombres uniformément à partir de 1 à n et insérez-les dans votre liste. Si vous trouvez une collision, choisissez à nouveau. Vous allez entrer en collision sur m / n de l'heure (en réalité, vous vous intégrez de 1 / N à M / N), ce qui vous obligera à choisir (récursivement), vous vous attendez donc à ce que vous attendez. prendre m / (1-m / n) sélections pour terminer le processus. Ainsi, votre coût pour cet algorithme est approximativement o (m * (n / (n / m)) * journal (m)) .
m est presque égal à n , vous pouvez utiliser la stratégie de rééchantillonnage, mais choisir ces numéros to pas inclure; cela peut être une victoire, même si vous devez pousser tous les numéros presque- N , si votre génération de nombres aléatoires est chère.)
Ma solution est la même chose que Mark Byers '. Il faut du temps o (n ^ 2), donc c'est utile lorsque n est beaucoup plus petit que Maxvalue. Voici la mise en œuvre en Python:
def pick(n, maxValue):
chosen = []
for i in range(n):
r = random.randint(0, maxValue - i)
for e in chosen:
if e <= r:
r += 1
else:
break;
bisect.insort(chosen, r)
return chosen
Voici un algorithme optimal, en supposant que nous sommes autorisés à utiliser des hashmaps. Il fonctionne dans O (n) Heure et espace Strong> (et non O (maxvalue), ce qui est trop coûteux). Il est basé sur l'algorithme d'échantillon aléatoire de Floyd. Voir mon Publication du blog à ce sujet pour plus de détails.
Le code est en Java: P> private static Random rnd = new Random();
public static Set<Integer> randomSample(int max, int n) {
HashSet<Integer> res = new HashSet<Integer>(n);
int count = max + 1;
for (int i = count - n; i < count; i++) {
Integer item = rnd.nextInt(i + 1);
if (res.contains(item))
res.add(i);
else
res.add(item);
}
return res;
}
Bel article. Je trouve l'idée que, en cas de collision, je peux simplement choisir l'élément "max" ( i ici) contre-intuitif, soin de m'éclairer avec des mots "simples"?
Voir mon Réponse proposée avec strictement O (n) algorithme de temps et d'espace, ne nécessitant pas de hasmaps ( Ce qui peut ne pas être disponible et masquer certaines problèmes de complexité derrière leur implémentation, par exemple l'extraction du temps n'est pas O (1) ). Il est basé sur la variation de shuffle, c'est-à-dire que le mélange partiel
@Nikosm.: Votre approche est documentée dans mon blogpost (voir la section "Swapping"). Cependant, il suppose que vous recevez une matrice et que le tableau peut être commandé. De plus, dans le problème présenté ici, les entrées sont max et n, qui sont 2 entiers, vous ne pouvez donc pas appliquer cette approche (sans construire la maquette complète de taille maximale).
@Eyalschneider, oui, il y a un point là-bas, même si même des arraylistes immuables peuvent être mélangés (ce sont des références). Mais oui, il nécessite la matrice initiale et pas seulement la taille. Pour le point 4. Sur votre message (Randomising une liste de flux / hors ligne, probablement très grand), voir question associée ici
@Eyalschneider, la section d'échange du blog est une solution similaire (battant partielle), mais destructeur
@Eyalschneider, BTW travaillant sur strictement O (k) Solution de combinaison aléatoire (ne nécessitant pas une matrice, une taille suffisante n ) pour mon Combinatorics Lib Abacus
Je ne comprends pas pourquoi vous avez utilisé un hashset. Quelle valeur ajoute-t-il? Je pense que ma solution est meilleure Stackoverflow.com/a/38736104/5810023 - Peut-être que vous avez quelque chose de similaire dans votre blog, Mais je ne vois toujours pas pourquoi vous n'avez pas posté les meilleurs ici.
@Caveman: Votre approche est correcte et elle apparaît également dans mon article de blog (voir "Swapping"). Cependant, il dispose de 2 exigences importantes pour être appliquée: la collection d'intrants doit être un accès aléatoire et modifiable. Dans ce cas particulier, vous n'avez pas reçu de collection. Au lieu de cela, vous recevez deux chiffres (n, maxvalue). Si vous essayez d'appliquer votre algorithme, vous devez d'abord construire la matrice ... ce qui conduit à O (Maxvalue) espace et temps.
@Eyalschneider merci! Désolé j'ai manqué le mord maxvalue! Mais néanmoins initialiser un tableau jusqu'à Maxvalue ne fait que une fois ! Ainsi, je pense que doit être moins cher que d'utiliser un hashmap!
Générateur congruentiel linéaire MODULO Maxvalue + 1. Je suis sûr que j'ai déjà écrit cette réponse, mais je ne peux pas le trouver ...
Sûrement cela ne garantit pas de valeurs distinctes?
Avec des paramètres choisis de manière appropriée, un LCG MODULO M cycles à travers toutes les valeurs de [0, M-1]. C'est une des raisons qu'ils sont utilisées comme des PRNG (ils finissent par faire de manière à parcourir toutes les valeurs de sortie possibles et sont donc «uniformes»). La page Wikipedia répertorie les conditions nécessaires (insérer habituellement Wikipedia Cavaat): EN.Wikipedia.org/wiki/Lineear_Congruential_Generator < / a>
L'astuce consiste à utiliser une variante de shuffle ou d'autres mots un mélange partiel. adapté de Here o (n) dans temps et espace , produit o (1) , il pourrait même être o (n) dans le pire des cas)
L'espace n'est clairement pas O (n) comme vous le demandez. C'est plutôt O (n) . De plus, votre algorithme ne sélectionne pas uniformément les numéros. Cela est dû au fait que vous utilisez rand (0, --n) . Ceci est un problème, par exemple, le nombre A [n-1] ne peut être choisi que lorsque i = 0 (mais pas lorsque i! = 0 < / code>). De plus, je ne vois pas pourquoi vous utilisez deux tableaux cueillis et sauvegarde . Semble redondant. Vérifiez ma réponse: Stackoverflow.com/a/38736104/5810023
Je pense que cet algorithme ci-dessous est optimum . C'est à dire. Vous ne pouvez pas obtenir de meilleures performances que cela. Pour choisir Numéros de N de M , le meilleur algorithme proposé jusqu'à présent est présenté ci-dessous. Sa plus grande complexité du temps d'exécution est C'est aussi un Programme complet C. Ce que vous trouvez est: ici est la sortie d'un exemple Code où je publie au hasard
getrand : ceci est juste un prng qui renvoie un numéro de 0 jusqu'à jusqu'à . . .
randselect : Ceci est la fonction que Randmoly choisit Numéros uniques sur M de nombreux numéros. C'est à quoi c'est cette question.
principale : Ceci est uniquement pour démontrer une utilisation pour d'autres fonctions, de sorte que vous puissiez la compiler dans un programme et amusez-vous.
L'entrée dans cette question n'est pas un tableau. Cela change complètement les complexités de temps de votre approche. En raison de l'initialisation de la matrice, il fonctionne dans O (Maxvalue) temps et espace, ce qui n'est pas optimal.
Mais la partie d'initialisation de la matrice est hors de portée de la sélection aléatoire de permutation. La partie de permutation aléatoire ne se soucie pas du nombre d'éléments dans le tableau (Maxvalue), mais il ne se soucie que du nombre total de bits que vous souhaitez choisir, uniquement.
Désolé, j'ai raté le mors maxvalue. Mais voici la chose: l'allocation de tableau jusqu'à la valeur MaxValue n'est effectuée qu'une seule fois et n'est pas répétée pendant le temps d'exécution. Je pense que cela rend mon approche plus rapide que votre approche avec HashMaps. Donc, lors de l'allocation d'un tableau jusqu'à Maxvalue, mais ce coût est petit et ne se fait qu'une seule fois. Alors que votre utilisation de HASHMAP a un coût qui se reproduit au cours de la période de votre demande.
Oui, votre approche est plus rapide dans la complexité du pire des cas (en supposant une initialisation unique de la matrice), mais elle le fait au détriment de la complexité spatiale - O (Maxvalue). Cela devient peu pratique lorsque Maxvalue devient grande.
Je suis d'accord. BTW Toute réflexion sur la question de savoir si ma méthode est uniformément répartie sur les permutations qu'il génère?
Dupliqué possible de algorithme pour sélectionner une combinaison de valeurs unique et aléatoire? Voir la réponse acceptée pour Bob Floyd Algorithm, qui est adaptée spécifiquement pour cette situation.
Pas vraiment un duplicata, cette question fait référence à un sous-ensemble d'un ensemble arbitraire. Cela prend un échantillon à partir d'entiers séquentiels, qui constitue un problème plus spécifique (et donc potentiellement potentiellement aménageant à de meilleurs algorithmes / d'approches plus optimisées)
Je suis allé avec une approche mélangée qui a sélectionné un algorithme différent basé sur la taille des deux min et maxvalue, intégrant des idées de Mark, Eyal, Rafe et Rex. Merci pour toutes les grandes réponses!