arrière-plan:
Je travaille avec des permutations de la séquence d'entiers {0, 1, 2 ..., n}. J'ai un algorithme de recherche local qui transforme une permutation de manière systématique dans une autre permutation. Le point de l'algorithme est de produire une permutation qui minimise une fonction de coût. J'aimerais travailler avec une large gamme de problèmes, de n = 5 à n = 400.
Le problème:
Pour réduire les efforts de recherche, j'ai besoin de pouvoir vérifier si j'ai déjà traité une permutation particulière des entiers précédents. J'utilise une table de hachage pour cela et j'ai besoin de pouvoir générer un ID pour chaque permutation que je peux utiliser comme clé dans la table. Cependant, je ne peux penser à une belle fonction de hachage qui mappe un ensemble d'entiers dans une clé de telle sorte que les collisions ne se produisent pas trop fréquemment.
Des choses que j'ai essayées:
J'ai commencé en générant une séquence de n nombres premiers et en multipliant le numéro du numéro dans ma permutation avec le premier Prime puis en résumé les résultats. La clé résultante produit toutefois des collisions même pour n = 5.
J'ai également pensé concaténer les valeurs de tous les numéros et prenez la valeur entière de la chaîne résultante en tant que clé, mais l'ID devient rapidement trop gros pour de petites valeurs de n. Idéalement, j'aimerais pouvoir stocker chaque clé comme un entier.
Stackoverflow a-t-il des suggestions pour moi?
10 Réponses :
Vous pourriez que MD5 hachage une chaîne séparée par des virgules contaignant votre INT.
en C #, il ressemblerait à ceci (Disclaimer: Je n'ai pas de compilateur sur la machine que j'utilise aujourd'hui): p>
using System;
using System.Security.Cryptography;
using System.Text;
public class SomeClass {
static Guid GetHash(int[] numbers) {
string csv = string.Join(',', numbers);
return new Guid(new MD5CryptoServiceProvider().ComputeHash(Encoding.ASCII.GetBytes(csv.Trim())));
}
}
Le hash est une bonne idée parce qu'il veut un entier, pas seulement une chaîne, de représenter l'unicité. Mais, comme indiqué dans ma réponse, vous pouvez simplement prendre les 4 premiers octets de tout hachage pour obtenir ceci :)
Convertissez chaque numéro en chaîne, concaténate des chaînes (via Stringbuffer) et prenez le contenu de Stringbuffer comme clé.
Vous aurez besoin d'un délimiteur, bien sûr ou 12,3 serait identique à 1,23
Bonjour Victor, cette suggestion a été mentionnée dans mon post original. Cela fonctionnera mais le problème est que les clés deviennent rapidement très grandes. Considérons l'affaire pour n = 20. Si mon admédatoire est {1, 2, 3 ... 18, 19, 20} L'ID correspondant est: 01234567891011181314151617181920 Certains des problèmes plus importants que j'espère travailler avec N = 400. Idéalement, Je préférerais une solution plus efficace de la mémoire.
n = 400? Et vous souhaitez mapper des permutations uniquement aux entiers? 400! est un très grand nombre ... environ 870 chiffres décimaux. Vous devrez peut-être oublier l'unicité et optez pour une solution basée sur un hachage comme suggéré ci-dessus.
hachage Zobrist pourrait fonctionner pour vous. Vous devez créer une matrice NXN de nombres entiers aléatoires, chaque cellule représentant cet élément I dans la position de la JTH dans la permutation actuelle. Pour une permutation donnée, vous choisissez les n valeurs de cellules N, et xor-les un par un pour obtenir la clé de la permutation (notez que la clé de clés n'est pas garantie).
Le point de cet algorithme est que si vous échangez sur des éléments de vos permutations, vous pouvez facilement générer la nouvelle clé de la permutation actuelle en Xor-ing sur Xor-ing dans les nouveaux postes.
Merci pour votre suggestion Zed. Le hachage de Zobrist ressemble à un moyen assez facile d'aller. En regardant échecsProgramming.wikispaces.com/zobrist+hashaing Il semble que la sélection de bonnes graines aléatoires est plutôt important de minimiser les collisions.
À quelle vitesse faut-il?
Vous pouvez toujours rassembler les entiers comme une chaîne, puis prendre le hasch de cela, puis attrapez les 4 premiers octets.
Pour un hachage, vous pouvez utiliser une fonction vraiment, comme MD5 ou SHA-256.
Salut soyeux. Merci d'avoir posté. Le hachage doit être raisonnablement rapide car il existe de nombreuses permutations à prendre en compte. Je ne connais pas la complexité temporelle de MD5 ou SHA-256, bien que j'aime la suggestion de saisir les 4 premiers octets du résultat.
J'essayerais à la fois et de comparer les temps.
Comme d'autres l'ont suggéré, vous pouvez utiliser le hachage pour générer un entier qui sera unique avec une probabilité élevée. Cependant, si vous avez besoin de l'entier pour toujours être unique, vous devez rang les permutations, c'est-à-dire qui leur attribue une commande. Par exemple, un ordre commun des permutations pour la définition {1,2,3} est l'ordre lexicographique:
Dans ce cas, l'ID d'une permutation est son index dans l'ordre lexicographique. Il existe d'autres méthodes de classement des permutations, bien sûr.
Faire des IDS Une gamme d'entiers continus permet de mettre en œuvre le stockage des permutations traitées en tant que champ de bits ou une matrice booléenne.
Cette approche vous fournira le plus petit frappe possible que garantit unicité. Google "classement" "permutations" pour trouver des moyens efficaces de classer les permutations arbitraires. (Bien, plus efficace que d'énumérer chaque permutation inférieure ... :))
J'aime ça, mais cela nécessite d'économiser beaucoup plus de données que l'approche naïve de hachage.
Ce serait une bonne solution si N était, disons, environ 6 ou 7. Lorsque vous cartographiez les permutations de 20 au 20 premiers! Les entiers, ça deviennent assez stupides. Daniel parle de n = 400. L'unicité n'est pas réaliste.
Lorsque vous utilisez des hachages, il y a deux possibilités: 1. Le hachage est unique - dans ce cas, vous avez de nouveau la cartographie à N! Les entiers et 2. Le hachage n'est pas unique, auquel cas vous devez stocker chaque permutation transformée afin de vous assurer que vous l'avez traité. Pour un grand N, cependant, rien ne pourrait être efficace de la mémoire afin que l'on aura certainement avoir recours à l'utilisation de stockage externe.
@Daniel: Pourriez-vous mettre à jour votre question pour mentionner que vous avez N = 400 ou plus? Ozan a raison de dire que cette approche est inappropriée pour N> 10 environ.
Merci pour la suggestion bojan. J'ai eu le sens de regarder des algorithmes de classement depuis quelque temps maintenant et cela m'a rappelé. Comme vous et Ozan disent, il ne semble pas que cela fonctionnera pour des instances importantes car le rang déborde rapidement le type d'entier que j'utilise pour les clés. Néanmoins, une très belle idée! EDIT: republié; Correction d'une typo mineure.
@j_random_hacker: Tous fixes; avec un tas d'autres clarifications :)
Ne pas se rapporter directement à la question, mais comme une solution alternative, vous pouvez utiliser TRIE Tree comme une sur place structure. Les tries arbores sont très bonnes pour les opérations de chaînes, sa mise en œuvre relativement facile et elle devrait être plus rapide (max de n (k) où K est la longueur d'une clé) que le hashset pour une grande quantité de longues chaînes. Et vous n'êtes pas limité de la taille de la clé (tel dans un hashset régulier dans Int Int, pas plus gros). La clé de votre cas sera une chaîne de tous les numéros séparés par certains caractères.
Jugement par votre question et les commentaires que vous avez laissés, je dirais que votre problème n'est pas possible de résoudre.
Permettez-moi d'expliquer.
Vous dites que vous avez besoin d'un hachage unique de votre combinaison, faites donc cette règle n ° 1:
OK, puis dans un commentaire que vous avez dit que, étant donné que vous utilisez plusieurs numéros, les stockez comme une chaîne ou ce que vous n'avez pas la clé de la haquetable n'est pas réalisable, en raison des contraintes de mémoire. Réécrivez donc cela dans une autre règle:
Fondamentalement, vous essayez de prendre un grand nombre et de stocker cela dans une plage de nombres beaucoup plus petite, et d'avoir un caractère unique.
Désolé, mais vous ne pouvez pas faire ça.
Les algorithmes de hachage typiques produisent des valeurs de hachage relativement uniques, de sorte que vous n'êtes pas disposé à accepter des collisions, en ce sens qu'une nouvelle combinaison pourrait être signalée comme "déjà vue" même si elle n'a pas, alors vous n'êtes pas hors de chance.
Si vous deviez essayer un champ de bit, où chaque combinaison a un peu, qui est 0 si elle n'a pas été vue, vous avez toujours besoin de grandes quantités de mémoire.
Pour la permutation dans N = 20 que vous avez laissée dans un commentaire, vous en avez 20! (2 432 902 008 176 640 000) Combinaisons, que si vous avez essayé de stocker simplement chaque combinaison sous forme de 1 bit dans un champ de bits, il faudrait 276 589 To de stockage.
Vous allez devoir limiter votre portée de ce que vous essayez de faire.
Salut Lasse. Merci pour votre commentaire. Je pense que mon post aurait dû être plus clair; J'ai travaillé avec de petites instances toute la journée (n = 5) et dans ces cas, j'aimerais que l'unicité. Pour des cas plus importants, la réduction des collisions est suffisante. Je n'essaie pas d'énumérer de manière exhaustive toutes les permutations, mais plutôt d'exécuter une recherche locale dirigée.
Prime POUVOIRS fonctionnerait: si devrait être unique par le Théorème fondamental de Arithmétique . Ces chiffres deviendront assez gros, cependant: -) (par exemple, pour N = 5, (1,2,3,4,5) mappera à 870 037 764 750, qui est déjà plus de 32 bits) p_i est le i th premier et a_i est le i th élément de votre tuple, alors
Semblable à Poste de Bojan Cela ressemble à La meilleure façon d'y aller est d'avoir un ordre déterministe aux permutations. Si vous les traitez dans cet ordre, il n'est pas nécessaire de rechercher si vous avez déjà effectué une permutation particulière.
Obtenez deux permutations de la même série de chiffres {1, .., N}, construisez une mappage TUPple, (ID, permutation1 [ID], permutation2 [ID]) ou (ID, F1 (ID), F2 (ID), F2 (ID), F2 (ID), F2 (ID), F2 ( identifiant)); Vous obtiendrez une carte unique par {F3 (ID) | Pour tuple (ID, F1 (ID), F2 (ID)), à partir d'ID, nous obtenons une F2 (ID) et trouvez un ID 'à partir de tuple (ID', F1 (ID '), F2 (ID')) où F1 (ID ') == F2 (ID)}