J'ai un ensemble de nombreuses grandes chaînes que je veux faire des recherches d'existence. Je n'ai pas besoin de la chaîne entière pour être sauvée. Pour autant que je puisse dire, le jeu Cette structure de données existe-t-elle? P> () code> réellement stocké la chaîne qui mangent beaucoup de ma mémoire. done = hash_only_set()
while len(queue) > 0 :
item = queue.pop()
if item not in done :
process(item)
done.add(item)
6 Réponses :
Il est certainement possible de conserver un ensemble de hachages:
done = set()
while len(queue) > 0 :
item = queue.pop()
h = hash(item)
if h not in done :
process(item)
done.add(h)
Votre méthode stockerait-elle le hachage deux fois? une fois la clé de la table, et une fois la valeur?
L'utilisation d'un hachage ... Très intelligent :-)
Utiliser le hachage intégré aurez-vous beaucoup de chances de trouver des collisions (ce n'est que 32 bits).
E-Satis: Set () utilise toujours le hachage (mais non seulement le hachage), défini (), tout comme Dict () est une carte de hachage.
@Paul: Comme c'est un ensemble, non, cela ne le stockerait pas deux fois.
@Paul: sur un système 32 bits, chaque élément prendra 20 octets: 8 octets dans l'ensemble et 12 octets pour l'objet entier lui-même. Cela stockera effectivement la valeur deux fois (une fois dans la seinture, une fois dans l'objet INT); Les 12 octets restants sont de 3 pointeurs.
@tonfa: plus précisément, à cause du paradoxe d'anniversaire, la probabilité d'une collision est de 50% lorsque vous avez ca. 77.000 chaînes.
@ Martin, ma règle de base préférée est que vous vous inquiétez de la collision ("risque élevé / significatif") autour du SQRT du nombre de valeurs de hachage différentes (environ 64k pour des hachages 32 bits parfumés). Oui, vous pouvez le calculer précisément, mais cette approche de l'enveloppe de retour vous permet de votre vol d'oeil à la taille d'un espace de hachage dont vous avez besoin facilement (plus que le carré du nombre d'articles que vous attendez ;-).
@ Alex: Bien sûr, en utilisant la racine carrée du paradoxe d'anniversaire est une règle largement répandue du pouce. Cependant, il est souvent mal compris, alors j'ai décidé de calculer plus correctement (IIUC, la valeur réelle de la limite de 50% serait 77163, pour 2 ** 32 valeurs de hachage uniformément réparties).
Malheureusement, terminé.add (h) créera un hachage supplémentaire du hachage h . Probablement pas une grande surcharge, mais ce serait bien si les bibliothèques standard Python contenaient une variante de définir qui stockerait uniquement les hachages et non les valeurs. La longueur de hachage configurable serait également très utile.
Vous pouvez utiliser une structure de données appelée Filtre Bloom spécifique dans ce but. Une implémentation Python se trouve .
EDIT : Remarques importantes:
Cela dit, les chances que cela se produise peut être amené à un minimum si elle est utilisée correctement et donc je considère que cette structure de données est très utile.
Avec un filtre de floraison, les faux positifs sont possibles, que je pense que le règlement de ce que veut. Je suis sûr qu'il ne voudrait pas que l'un de ses articles ne soit pas traité à cause d'un faux positif.
Toutes les solutions qui ne stockent pas les chaînes entières auront la chance de faux positifs, mais celui-ci a une faible utilisation de la mémoire et peut être adapté à vos besoins.
Vous devriez penser à la recherche de la recherche, car il existe deux méthodes que les besoins définis, Le hachage est un "Partie libre" que vous pouvez enlever, mais le Si vous n'avez besoin que de confirmation négative (cet élément ne fait pas partie de l'ensemble), vous pouvez remplir une collection de configurations que vous avez implémentée avec vos chaînes, puis vous " Finaliser «l'ensemble en supprimant toutes les cordes, à l'exception de ceux-ci avec des collisions (celles-ci sont conservées pour EQ Strong> tests), et vous promettez de ne pas ajouter plus d'objets à votre ensemble. Maintenant, vous avez un test exclusif disponible .. Vous pouvez dire si un objet n'est pas em> dans votre ensemble. Vous ne pouvez pas être certain si "obj in set == true" est un faux positif ou non. P> EDIT: Ceci est essentiellement un filtre de fleurs intelligemment lié, mais un filtre de fleurs peut utiliser plus de Un hachage par élément qui est vraiment intelligent. P> EDIT2: Ceci est mon filtre de floraison de 3 minutes: P> __ hachage __ code> et __ eq __ code>. __ eq __ code> n'est pas une partie lâche que vous pouvez enregistrer; Vous devez avoir deux chaînes pour la comparaison. P> class BloomFilter (object):
"""
Let's make a bloom filter
http://en.wikipedia.org/wiki/Bloom_filter
__contains__ has false positives, but never false negatives
"""
def __init__(self, hashes=(hash, )):
self.hashes = hashes
self.data = set()
def __contains__(self, obj):
return all((h(obj) in self.data) for h in self.hashes)
def add(self, obj):
self.data.update(h(obj) for h in self.hashes)
Vous devez connaître toute la chaîne d'avoir 100% de certitude. Si vous avez beaucoup de chaînes avec des préfixes similaires, vous pouvez économiser de l'espace en utilisant un Trie pour stocker les chaînes. Si vos chaînes sont longues, vous pouvez aussi économiser de l'espace en utilisant une grande fonction de hachage SHA-1 comme pour faire la possibilité de collisions de hachage si éloignée que non pertinente.
Si vous pouvez faire le process () idempotent - à savoir l'avoir appelé deux fois sur un élément est seulement un problème de performance, le problème devient beaucoup plus simple et vous pouvez utiliser datastructures de lossy, tels comme filtres bloom.
Ceci est une très très bonne suggestion. Vous pouvez sauver toute la mémoire de chaîne juste pour l'extérieur (ou moins promille?) Surcharge du processeur.
Si vous utilisez une connexion sécurisée (comme SHA-256, trouvé dans le Le builtin hashlib module) fonction de hachage de hachage des chaînes, il est très peu probable que vous trouvé en double (et si vous trouvez certains vous pouvez probablement gagner un prix comme avec la plupart des fonctions de hachage cryptographique).
__ __ hachage () ne garantit pas que vous aurez pas les doublons (et puisqu'il utilise seulement 32 bits, il est très probable que vous trouverez quelques-uns).
Si le hachage de chaîne de Python peut contenir jusqu'à, il peut être raisonnable d'utiliser le hachage de chaîne avec <65000 chaînes: stackoverflow.com/questions/1303021/...
L'utilisation d'un hachage sécurisé n'est pas nécessaire. Sécurisé! = Faible probabilité de collision. Juste signifie qu'il Sécurisez est impossible de produire un certain hachage avec des données de « mauvaises ».
@truppo Si vous regardez en.wikipedia.org/wiki/Cryptographic_hash_function vous verrez que la faible probabilité de collision fait partie des propriétés d'un hachage cryptographique idéal.
@ Kaizer.se: Il a dit qu'il avait beaucoup de cordes :)
64K chaînes de longueur, soit 100 caractères => au moins 6400 kilo-octets; pas prohibitif et il est probablement beaucoup plus d'être un problème de mémoire afin que vous avez raison.
Comme on l'a déjà fait allusion, si les réponses proposées ici (dont la plupart se décomposer face à des collisions de hachage) ne sont pas acceptables, vous devez utiliser une représentation sans perte des chaînes.
Le module zlib Python fournit des capacités de compression de chaîne intégrée et pourrait être utilisé pour pré-traiter les chaînes avant de les mettre dans votre jeu. Notez cependant que les cordes ne doivent être assez long (que vous allusion qu'ils sont) et ont l'entropie minimale afin d'économiser beaucoup d'espace mémoire. D'autres options de compression pourraient offrir de meilleures économies d'espace et certaines implémentations basées sur Python peuvent être trouvés
BTW, êtes-vous lié à The Tarjan?
+1, cette question a apporté des réponses très intéressantes.