Compte tenu d'un entier 64 bits, où les 52 derniers bits à évaluer et les 12 bits de premier plan doivent être ignorés, quel est le moyen le plus rapide de boucler chaque combinaison de 7 bits sur et tous les autres bits?
Exemple:
première permutation: dernière permutation où vitesse est absolument crucial, nous cherchons à économiser chaque cycle d'horloge que nous pouvons car il fait partie d'un plus grand Solution qui doit évaluer des milliards d'états dans un délai raisonnable. Une solution de travail n'est pas requise, mais un pseudo code ferait juste bien :) 0 [ xn] signifie n désactivé (zéro) bits.
3 Réponses :
Ce dont vous avez besoin est un bon algorithme qui vous emmènera d'une permutation à la prochaine fois de temps minimal.
Maintenant, le premier algorithme qui me vient à l'esprit consiste à traverser toutes les combinaisons avec sept boucles. P>
Cela vous donnera l'itération la plus rapide. Voici quelques pseudo c ++ Code: P>
1100 1010 1001 0110 0101 0011
Tout comme une note: cet algorithme fonctionne sur les 52 premiers bits, pas le dernier. Une solution simple serait d'ajuster les opérations de décalage de bits.
Excellente réponse, merci. Je pense qu'il y a cependant plus de solutions, j'écris une réponse qui va se tromper mais pourrait vous donner une idée d'une manière différente de résoudre ce problème
Peu importe ma réponse sera trop vague, malade, écrivez-le dans la question des commentaires
J'ai écrit un commentaire à ma question si mon commentaire est plausible, cela surperformera probablement 7 boucles imbriquées?
C'est comme ça que je l'aurais fait. La boucle interne pourrait être déroulée et les bits «extérieurs» orient à l'extérieur. De plus, le déplacement du bit interne pourrait être fait avec un 1-décalage.
@Tom: avec des boucles imbriquées, et la boucle intérieure déroulée, la boucle interne ressemble à ceci comme suit: eval (OUTERBITS | 1); Eval (OUTERBITS | 2; EVAL (OUTERBITS | 4); ... . Semble difficile à battre.
Je pense que cela vous intéressera à cet article: http://realtimecollisionDetection.net/blog/ ? p = 78
Cela résout votre problème de manière très efficace.
J'ai pensé rapidement: "Détection de collision? WTF?"
+1. Chaque fois que je voyage sur ce blog, je pense que "je devrais lire ceci plus souvent." Ensuite, j'oublie jusqu'à ce que je tripelle à nouveau. Je vraiment devrait le lire plus souvent ;-) Retour sur le sujet, c'est une approche vraiment intéressante du problème.
Hmm .. sept opérations par itération. Ce serait beaucoup plus efficace.
Merci, excellent article, le lira pleinement, tout comme une question, cela fonctionnerait-il aussi vite que, sinon plus rapide que la solution de solution que j'ai exposée dans les commentaires de la question?
@Tom je ne pense vraiment pas que quelque chose puisse le surperformer.
Excellent article. Donc, si je déclare mon INT64 = 127, puis effectuez ces sept opérations 1000 fois, j'aurai mes sapins de 1000 permutations?
@Tom Droite. En outre, vous pouvez modifier à tout moment le nombre de bits requis uniquement en modifiant la valeur initiale: (1 << n) - 1
Excellent, merci encore! Et ai-je raison de dire qu'il y a 133 784 560 combinaisons pour mon arrangement de 7 bits dans un cadre de 52 (52 choix 7)? Je sais donc quand arrêter le déplacement, je garde une trace du nombre total de permutations.
Et existe-t-il un moyen facile de renvoyer le numéro de permutation en fonction d'une entrée? Ie GetPerm (127) = 1, GetPerm (4468415255281664) = 133 784 560 ou devrais-je probablement créer une autre question pour cela?
@Tom tandis que (! (Perm >> 52)) est plus sûr.
Je pense qu'il existe une relation entre chaque permutation.
p>
Nous pouvons voir le numéro augmente avec la permutation # avec un motif . P>
Ce maths n'est pas correct pour toutes les solutions, mais travaille pour certains, espérons-le, indiquant ce que je veux dire: p> donc nous serions donc en boucle de la Valeurs absolues: P> int perm = 1;
for int64 i = 127; perm < totalPermutations
{
i = i + ((perm%7+1)^2) * (roundUp(perm/7);
perm++;
}
Mes mathématiques sont horribles et je n'ai pas réussi à calculer une formule de travail pour que je ne sache pas encore :) postera ici si je peux le trouver
Juste pour être clair, tous les numéros sont-ils avec seulement sept morceaux de secours, ou juste ceux avec sept bits consécutifs? par exemple. 0 [x54] 1110010111, 0 [x30] 10 [x26] 111111
Ce sont toutes des combinaisons de 7 bits définies comme un maximum, non continu. Par exemple, on pourrait être 000 ... 1100..1 ... 01. Il y aura toujours 7 bits dans les 52 derniers bits.
En tant que solution pensée, s'il y avait une boucle qui fixait l'entier à la valeur de la première permutation (127) au dernier (446841525281664), je croyais une relation (peut-être un facteur de mise à l'échelle ou une valeur d'addition fixe lorsque vous permutation de modulus # par 7) qui peuvent être appliqués pour obtenir la prochaine permutation.
J'aurais appuyé vers l'approche d'Alexandre. Lorsqu'il est optimisé, la boucle interne semble plus rapide. Une seule étape prouverait le pudding. Mais - donnez-vous une attention égale à l'évaluation que vous appliquez à la combinaison? C'est-à-dire que vous étirez à nouveau les morceaux à nouveau? Si tel est le cas, un motif bit n'est peut-être pas la bonne représentation.