J'aimerais bien itérer au hasard par une plage. Chaque valeur ne sera visitée qu'une seule fois et toutes les valeurs seront éventuellement visitées. Par exemple: où Mon problème est que Ce code est très naïf et fonctionne rapidement de la mémoire comme Quel type d'algorithme peut accomplir ce que j'essaie de faire? p> [solution] strong>: Le code suivant est basé sur la solution de @ BTA. Pour des raisons de concistance, f (x) code> est une fonction qui fonctionne sur chaque valeur. Fisher-Yates Shuffle est utilisé pour fournir efficacement un ordre aléatoire. P> shuffle code> doit fonctionner sur un tableau, ce qui n'est pas cool parce que je travaille avec astronomiquement fort> grand nombre. Ruby consommera rapidement une grande quantité de RAM essayant de créer un tableau monstrueux. Imaginez remplacer (0..9) code> avec (0..99 ** 99) code>. C'est aussi pourquoi le code suivant ne fonctionnera pas: p> essayé code> obtient plus d'entrées. P> f (x) code> dans les exemples ci-dessus est une méthode qui génère un hachage et la compare à Un hachage de cible constant pour des collisions partielles. Je n'ai pas besoin de stocker la valeur de x code> après que j'appelle f (x) code> alors la mémoire doit donc rester constante au fil du temps. P> Next_prime code> n'est pas affiché. Il produit une aléatoire acceptable et ne visite que chaque numéro une fois. Voir le message réel pour plus de détails. P> N = size_of_range
Q = ( 2 * N / (1 + Math.sqrt(5)) ).to_i.next_prime
START = rand(N)
x = START
nil until f( x = (x + Q) % N ) == START # assuming f(x) returns x
11 Réponses :
Je pourrais avoir tort, mais je ne pense pas que cela soit faisable sans stocker un État. À tout le moins, vous allez avoir besoin d'un État.
Même si vous n'utilisez qu'un bit par valeur (cette valeur a-t-elle été essayée Oui ou Non), vous aurez besoin de x / 8 octets de mémoire pour stocker le résultat (où x est le plus grand nombre). En supposant que vous avez 2 Go de mémoire libre, cela vous laisserait plus de 16 millions de chiffres.
Systèmes de base de données et autres systèmes à grande échelle Le font en écrivant les résultats intermédiaires de Tries récursifs dans un fichier de base de données Temp. De cette façon, ils peuvent trier des nombres énormes d'enregistrements tout en conservant un nombre limité d'enregistrements en mémoire à une heure. Cela a tendance à être compliqué dans la pratique.
Casser la plage dans des lots gérables, comme indiqué ci-dessous:
def range_walker range, batch_size = 100
size = (range.end - range.begin) + 1
n = size/batch_size
n.times do |i|
x = i * batch_size + range.begin
y = x + batch_size
(x...y).sort_by{rand}.each{|z| p z}
end
d = (range.end - size%batch_size + 1)
(d..range.end).sort_by{rand}.each{|z| p z }
end
Même si "n" et "Batch_Size" étaient le même nombre (SQRT (N)), les matrices générées seront trop grandes pour stocker en mémoire. Belle approche cependant. Je pense que l'algorithme final doit faire quelque chose de similaire à celui-ci, sauf que les tableaux seraient de taille gérable.
Dans votre question, il n'était pas clair que vous vouliez les résultats comme une matrice. Je pensais que vous vouliez simplement traiter au hasard des nombres dans une plage garantissant que chaque nombre est traité. Cette solution le fait quelle que soit la taille de la plage. Si vous souhaitez renvoyer ces chiffres sous forme de tableau, vous avez un problème différent.
Je suis désolé de ne pas clarifier. Je ne veux pas les résultats comme une matrice. Quelque part à l'intérieur de cette boucle, j'aimerais appeler une méthode qui prend le nombre aléatoire généré comme entrée. L'utilisation de la mémoire devrait rester constante à long terme.
Essayez appelant gamme_walker (0..99 ** 99) et vous verrez ce que je veux dire.
J'ai réglé le problème. Réessayer. La consommation de mémoire restera la même. La CPU est proche de 60% en raison d'un traitement continu.
Suis-je comprendre ce code correctement? La gamme est divisée en lots. Chaque lot a une distribution aléatoire. Cependant, les lots sont toujours visités dans l'ordre lorsque elles doivent être visitées au hasard. Maintenant, nous sommes de retour au même problème. :-)
@Void: C'est un compromis entre l'utilisation aléatoire et la mémoire. Vous économisez un peu de mémoire en visitant les lots dans l'ordre. À peu près, toute solution consiste à sacrifier le hasard au hasard pour des raisons d'utilisation de la mémoire tant qu'il existe une restriction que chaque entrée est visitée exactement une fois.
@Void: Une autre façon de regarder cela: les lots ne sont pas visités dans l'ordre, ils sont visités en parallèle. Utilisez un appareil multi-processeur, multi-noyau et chargez un lot sur chaque noyau. Ce type de problème semble être extrêmement parallélizable et cette solution semble briser en morceaux parallèles.
Je suis d'accord. La parallélisation est très efficace pour cette situation. Je voulais juste que l'algorithme s'élève bien à des gammes extrêmement grandes sans utiliser beaucoup de mémoire, alors j'ai donné un exemple ridicule.
Comment "aléatoire" votre commande doit-elle être? Si vous n'avez pas besoin d'une distribution d'entrée spécifique, vous pouvez essayer un schéma récursif comme celui-ci pour minimiser l'utilisation de la mémoire: essentiellement, vous construisez l'index en générant au hasard un chiffre à la fois. . Dans le pire des cas, cela nécessitera suffisamment de mémoire pour stocker 10 * (nombre de chiffres). Vous rencontrerez chaque numéro dans la plage L'autre inconvénient est la nécessité de construire manuellement la fonction à une profondeur spécifiée. Dans votre (0 .. (10 ** 3)) exactement une fois, mais la commande n'est que pseudo-aléatoire. C'est-à-dire que si la première boucle définit a = 1 , vous rencontrerez tous les numéros à trois chiffres du formulaire 1xx avant de voir le changement de centaine de chiffres. (0 .. (99 ** 99)) CAS, Ceci serait probablement un problème (bien que je suppose que vous puissiez écrire un script pour générer le code pour vous). Je suis sûr qu'il y a probablement un moyen de réécrire cela de manière ultravée, mais je ne peux pas y penser au sommet de ma tête (idées, quiconque?).
Aussi aléatoire que possible. C'est ainsi qu'il peut épuiser efficacement l'espace de recherche. C'est aussi ce qui fait une attaque d'anniversaire possible, ce qui permet de réduire considérablement la durée de recherche. Pensez-y comme brute-forçant la combinaison à une serrure.
Ceci est une implémentation récursive de quelque chose de similaire à la solution de Kandadaboggu. Fondamentalement, l'espace de recherche (comme une plage) est partitionné en une matrice contenant N gammes de taille égale. Chaque gamme est alimentée dans un ordre aléatoire comme nouvel espace de recherche. Cela continue jusqu'à ce que la taille de la gamme frappe une liaison inférieure. À ce stade, la gamme est suffisamment petite pour être convertie en une matrice, mélangée et vérifiée. Même s'il est récursif, je n'ai pas encore soufflé la pile. Au lieu de cela, il est erroné lors de la tentative de partitionnement d'un espace de recherche plus grand que sur les touches J'espère que les commentaires du code aident à remettre une lumière sur ma question initiale. Remarque:
10 ^ 19 . Je dois faire avec les chiffres trop volumineux pour convertir en un long . Il peut probablement être corrigé: pw_len sous # Options peut être remplacé par un nombre inférieur afin d'obtenir des résultats plus rapides.
C'est bien, mais vous voyez comment ce n'est pas un vrai shuffle, non? Le premier numéro sera distribué aléatoirement, mais les numéros de bloc_size suivants seront tous de la même gamme.
À moins que je sois mal compris votre commentaire, Fisher-Yates est un vrai shuffle et il est utilisé de la bonne manière. Chaque bloc est partitionné et visité dans un ordre aléatoire. Cependant, le mieux qu'il puisse faire est des lots de nombres aléatoires ...
AS @turtle a répondu, vous avez un problème n'a pas de solution. @Kandadaboggu et @bta Solution vous donne des numéros aléatoires correspond à certaines gammes qui sont ou ne sont pas aléatoires. Vous obtenez des grappes de chiffres.
Mais je ne sais pas pourquoi vous vous souciez de double occurrence du même numéro. Si Même si vous utilisiez Jaguar (top 1 de www.top500.org supercalculateurs) Avec seulement cette tâche, vous avez toujours besoin de 10 ^ 174 ans pour obtenir tous les numéros. Si vous ne me croyez pas, essayez Je vais vous acheter une bière si vous allez même une fois voir "Oh, non!" Sur votre écran pendant votre vie :) (0..99 ** 99) est votre plage, puis si vous pourriez générer 10 ^ 10 numéros aléatoires par seconde (si vous avez un processeur de 3 GHz et environ 4 noyaux sur lesquels vous générez un Nombre aléatoire par cycle de la CPU - qui est impossible et RUBY ralentira même le ralentissez-le), il faudrait alors 10 ^ 180 ans pour épuiser tous les chiffres. Vous avez également une probabilité d'environ 10 ^ -180 que deux nombres identiques seront générés pendant une année entière. Notre univers a probablement environ 10 ^ 9 ans, donc si votre ordinateur pouvait commencer à calculer lorsque l'heure a commencé, vous auriez une probabilité d'environ 10 ^ -170 que deux nombres identiques ont été générés. En d'autres termes -
Merci pour l'information utile. La gamme (0..99 ** 99) n'était qu'un exemple. L'algorithme de hachage que je teste contre a un espace de recherche qui est évolutif dans une quantité de temps réaliste pour les entrées de longueur réalistes. Je voulais juste que mon algorithme s'améliore efficacement tout en donnant à chaque numéro la même probabilité d'être sélectionnée. Quant à la bière, je pense que le soleil a une probabilité plus élevée de téléporter spontanément de l'autre côté de la galaxie :)
L'espace de recherche que je passe est (0 .. (80 ** n-1)) pour une longueur d'entrée de N.
Pour n = 11, il fallaudra 34 ans pour épuiser tous les chiffres ayant la même vitesse que dans mon exemple ci-dessus. Donc, probablement lorsque vous utilisez Ruby et que vous ne générez pas seulement des chiffres, mais aussi des calculs avec eux, vous ne devriez pas vous soucier des nombres répétitifs, car il faudra des âges pour épuiser toutes les possibilités. De l'autre côté, pour N = 6, vous pouvez stocker tous les numéros éprouvés sur un seul bit de matrice - il faudra environ 409 Mo. Avec N = 7, vous devriez avoir environ 32 Go de mémoire - vous devez donc probablement le stocker sur le disque dur. Mais encore une fois, cela aura fallu beaucoup de temps.
Sur ma boucle simple informatique comme ceci: a = 80 ** 4; b = 0; aôt {b = b + 1} a pris environ 16 secondes. Cela signifie que lorsque vous augmentez N par un, cette fois augmentera 80 fois, donc pour N = 6, il faudra 24 minutes, pour N = 7, 28 heures, pour n = 8, plus de 9 jours. Avec ce calcul, il donne 13300 ans pour N = 11 (c'est un exemple réel sur un noyau avec 2,13 GHz).
On dirait que tu es gêné tes mathématiques. Aller de n = 7 à n = 8 vous multipliez par 8 au lieu de 80. Le temps réel de n = 8 est légèrement supérieur à 3 mois. Compte tenu de suffisamment de aléatoire dans la sélection d'une clé à tester, la durée de cas moyenne est coupée en deux. Profitant d'une CPU multicœur divisera la période moyenne du nombre de cœurs que vous avez. Si plus d'efficacité est nécessaire, je pourrais passer à une langue différente. En le prenant au niveau suivant, je pourrais utiliser mon GPU pour le traitement du flux.
Je viens de me souvenir d'un problème similaire d'une classe que j'ai pris il y a des années; c'est-à-dire itérant (relativement) au hasard à travers un ensemble (complètement l'épuisant) donné des contraintes de mémoire extrêmement serrées. Si je me souviens de cela correctement, notre algorithme de solution était quelque chose comme ceci:
n
- génère un point de départ aléatoire
x [0] intérieur n
- génère un itérateur
q moins que n
- générer des points successifs
x [n] en ajoutant q à
le point précédent et envelopper si nécessaire. Cette
est, x [n + 1] = (x [n] + q)% n
- Répétez la répétition jusqu'à ce que vous produisiez un nouveau point égal au point de départ.
L'astuce consiste à trouver un itérateur qui vous permettra de traverser toute la plage sans générer la même valeur deux fois. Si je me souviens bien, tout relativement ample N et q fonctionnera (plus le nombre est proche des limites de la plage, moins l'entrée "aléatoire"). Dans ce cas, un nombre premier qui n'est pas un facteur de n devrait fonctionner. Vous pouvez également échanger des octets / nibiles dans le numéro résultant pour modifier le motif avec lequel les points générés "sautent autour" dans n . .
Cet algorithme nécessite uniquement le point de départ ( x [0] ), le point de courant ( x [n] ), la valeur Itératrice ( q < / code>) et la limite de plage ( n ) à stocker.
Peut-être que quelqu'un d'autre se souvient de cet algorithme et peut vérifier si je me souviens de cela correctement?
Je pense que cela est aussi bon que vous pouvez obtenir si vous ne stockez pas les entrées éprouvées et que vous ne pouvez pas avoir de duplicates. Il n'y a vraiment pas besoin de shuffle vraiment aléatoire si vous allez tester toutes les intrants et ils n'interfèrent pas. Pour diffuser autant que possible les choix, utilisez un Q proche de la section dorée (2N / (1 + SQRT (5))).
Cela semble presque exactement comme ce que je veux faire. Je ne suis pas trop préoccupé par le hasard, mais c'est très important. Si quelqu'un connaît le nom de cet algorithme, ce serait génial.
Je ne sais pas s'il y a un nom pour l'algorithme. Le principe spécifique basé sur (une propriété mathématique de nombres premiers en ce qui concerne l'arithmétique modulaire) pourrait avoir un nom cependant.
Voir en.wikipedia.org/wiki/full_cycle (et peut-être
Vous pouvez aléater aléatoirement un tableau avec la méthode de shuffle
Vous voulez ce qu'on appelle un "itérateur à cycle complet" ...
Voici psudocode pour la version la plus simple qui est parfaite pour la plupart des utilisations ... p>
sample = 10
For i = 1 to sample
last_value = fullCycleStep(sample, last_value)
print last_value
next
Pour un espace large prohibitif, comme Vous pouvez ajouter cette méthode à la plage Vous pouvez alors avec une bonne quantité de aléatoire tant que votre espace est quelques commandes inférieures à M127. Crédit à .
Ce n'est pas vraiment une réponse spécifique à rubis, mais j'espère que cela est autorisé. Andrew Kensler donne une fonction de permutation C ++ "permutée ()" qui fait exactement cela dans son "" Multi corrélé - Échantillonnage jugé " rapport.
Si je comprends bien, la fonction exacte qui ne fonctionne vraiment que si votre" tableau "est jusqu'à la taille 2 ^ 27, mais l'idée générale pourrait être utilisée pour les tableaux de tout Taille.
Je ferai de mon mieux pour en quelque sorte expliquer. La première partie est que vous avez besoin d'un hachage réversible "pour tout domaine de la taille de la puissance de deux". Considérez Vous avez donc une fonction réversible Le hachage réversible est la clé d'utiliser une technique appelée "cycle marche", introduite dans " chiffres avec des domaines finis arbitraires" . Étant donné que le hachage est réversible (c'est-à-dire 1-à-1), vous pouvez simplement appliquer à plusieurs reprises le même hachage jusqu'à ce que votre valeur hachée soit plus petite que votre tableau! Parce que vous appliquez le même hachage, et que la cartographie est une-à-une, quelle que soit la valeur que vous vous retrouvez sur le plan, vous ramènerez exactement à un index, de sorte que vous n'avez pas de collision. Donc, votre fonction pourrait ressembler à ceci comme ceci pour des entiers 32 bits (pseudocode): Cela pourrait prendre beaucoup de hashes pour atteindre votre domaine, alors Kensler fait un simple Astuce: il conserve le hachage dans le domaine de la prochaine puissance de deux, ce qui nécessite très peu d'itérations (~ 2 en moyenne), en masquant les bits inutiles. L'algorithme final ressemble à ceci: et c'est tout! De toute évidence, la chose importante ici est de choisir une bonne fonction de hachage, que Kensler fournit dans le journal, mais je voulais décomposer l'explication. Si vous souhaitez avoir des permutations aléatoires différentes à chaque fois, vous pouvez ajouter une valeur "graine" à la fonction permutée qui est ensuite transmise à la fonction de hachage. x = i + 1 . Peu importe ce que X est, même si votre entier déborde, vous pouvez déterminer ce que j'étais. Plus spécifiquement, vous pouvez toujours déterminer les n-bits inférieurs de I des n-bits inférieurs de x. L'ajout est une opération de hachage réversible, de même que la multiplication par un nombre impair, tout comme un xor biteux par une constante. Si vous connaissez un domaine de puissance de deux spécifique, vous pouvez brouiller les bits dans ce domaine. Par exemple. x ^ = (x & 0xFF) >> 5) est valide pour le domaine 16 bits. Vous pouvez spécifier ce domaine avec un masque, par exemple masque = 0xFF et votre fonction de hachage devient x = hachage (i, masque) . Bien sûr, vous pouvez ajouter une valeur «graine» dans la fonction de hachage pour obtenir différentes randomisations. Kensler établit des opérations plus valides dans le papier. x = hachage (i, masque, graine) . Le problème est que si vous utilisez votre index, vous pouvez vous retrouver avec une valeur plus grande que votre taille de matrice, c'est-à-dire votre "domaine". Vous ne pouvez pas simplement modulo ceci ou vous obtiendrez des collisions.
Vous ne stockez évidemment pas le résultat de votre invocation de fonction, car cela prendrait également beaucoup de mémoire. Alors qu'est-ce que tu fais exactement? Pourquoi avez-vous besoin de le faire dans un ordre aléatoire? Si vous accumulez simplement les valeurs, l'ordre serait probablement hors de propos. J'aimerais savoir plus si vous voulez une solution.
Si vous n'avez pas besoin des résultats dans un tableau, modifiez le code d'exemple
(0..9) .Sort_by {rand} .map {| x | f (x)} pour utiliserchaque au lieu demappe . Cela rendra la question plus claire.trier_by rand n'est pas non correct; Cela donnera des résultats biaisés. Voir robweir.com/blog/2010/02/microsoft -random-navigateur-ballot.htm l (JavaScript, mais même concept).Comme @Matthew Flaschen a écrit, votre tentative de randomisation de l'ordre de la liste est horriblement brisée et retournera des résultats pouvant sembler aléatoires, mais qui ne le sont pas. Son lien donne une bonne description du problème.
vide, vous avez manqué le point. Ce lien était ce que pas à faire. Vous ne pouvez pas trier par une fonction aléatoire (une fonction aléatoire décalée n'est pas meilleure).
D'accord, je vois ce que tu dis. J'ai changé l'exemple pour utiliser un shuffle de pêcheur-Yates.
Créé un itérateur en dehors de ceci: gist.github.com/363914