i [sûrement] inventé cette [Wheel] lorsque je voulais calculer l'Union et l'intersection et la diffusion de deux ensembles (stockés comme des listes) en même temps. Code initial (pas le plus serré):
dct = {}
for a in lst1:
dct[a] = 1
for b in lst2:
if b in dct:
dct[b] -= 1
else:
dct[b] = -1
union = [k for k in dct]
inter = [k for k in dct if dct[k] == 0]
oneminustwo = [k for k in dct if dct[k] == 1]
twominusone = [k for k in dct if dct[k] == -1]
4 Réponses :
est l'idée d'un champ de bit ce que vous cherchez? Chaque morceau de votre ... champ (faute d'un mot meilleur) représente un drapeau. Dans ce cas, votre drapeau est membre de l'ensemble n.
Edit - Je pense que j'ai mal compris quelle idée vous faisiez appelé. Ne pas tenir compte?
OK, le champ Bit est la valeur, mais qu'enversez-vous d'utiliser le champ de bit pour les requêtes?
Ce n'est pas exactement de quoi vous parlez, mais vous pourriez être intéressé à lire sur "Filtres de fleurs". Ils utilisent un champ de bit pour vérifier l'appartenance à des fins (mais peuvent augmenter les faux positifs).
Il est très courant d'utiliser un entier pour représenter un ensemble de petits entiers; Il est souvent appelé un bitset ou bitvector . Ici, vous utilisez un entier pour représenter "l'ensemble des séquences d'entrée contenant cette valeur". L'opération que vous faites me rappelle Dans votre cas, l'entrée est une liste des listes: mais vous pouvez le penser comme un sac de paires commandées, comme ceci: < Pré> xxx Vous construisez simplement une table contenant les paires inversées qui ressemble à ceci: Et vous représenteriez ces réseaux d'entiers à l'aide de bitvecteurs. La structure de données d'origine (la liste des listes) a facilité la gestion de toutes les valeurs pour une liste donnée. La structure de données inversée (le dictionnaire des listes) facilite la recherche de toutes les listes ayant une valeur donnée.
Utilisation d'un nombre N Bit Entere pour représenter N Booleans est un cas particulier de la structure de données appelée table de hachage formule la fonction de hachage, ce qui montre comment il est différent d'un tableau: P> class Sieve(object):
def __init__(self, stop):
self.stop = stop
self.data = [0] * (stop // 32 // 2 + 1)
self.len = 1 if stop >= 2 else 0
for n in xrange(3, stop, 2):
if self[n]:
self.len += 1
for n2 in xrange(n * 3, stop, n * 2):
self[n2] = False
def __getitem__(self, idx):
assert idx >= 2
if idx % 2 == 0:
return idx == 2
int_n, bit_n = divmod(idx // 2, 32)
return not bool(self.data[int_n] & (1 << bit_n))
def __setitem__(self, idx, value):
assert idx >= 2 and idx % 2 != 0
assert value is False
int_n, bit_n = divmod(idx // 2, 32)
self.data[int_n] |= (1 << bit_n)
def __len__(self):
return self.len
def __iter__(self):
yield 2
for n in xrange(3, self.stop, 2):
if self[n]:
yield n
Vous avez expliqué l'idée en détail, alors je devrais expliquer pourquoi je pense que cela ne voler pas. Dans une table de hachage, il y a un tableau plat et une fonction de hachage. Si nous prenons vos définitions, la fonction de hachage est (1 <<) .. qui rendrait l'opération de recherche de tableau & , qui n'a aucun sens.
Je l'ai appelé un cas particulier en raison de la comptabilité de sa stockage. Dans une table de hachage non parfaite, qui est la plus courante, je n'appellerais pas la résolution de collision d'un "tableau plat", même si un tableau est couramment utilisé, car il y a beaucoup plus de choses à vivre. Pour moi, c'est un détail de mise en œuvre de toute façon, et c'est la recherche rapide des valeurs de hachage (clé) qui est la partie importante de la définition. - Bien que je viens de réaliser que si vous "prenez mes définitions", vous les obtenez tous et il n'y a donc pas de problème. :)
Je n'ai pas dit que la résolution de collision était un tableau plat. Ça n'a aucun sens.
"C'est la recherche rapide des valeurs de hachage (clé) qui est la partie importante de la définition" Votre définition d'une table de hachage est "toute structure de données avec une recherche rapide basée sur hachage (clé)". Je pense que cela est trop lâche une définition car, comme vous l'avez démontré, vous pouvez indiquer n'importe quel résultat intermédiaire de l'algorithme de recherche et l'appeler un code de hachage. Dans votre définition, un tableau simple est une table de hachage avec hachage (IDX) = (AddR + IDX * Taille).
Plus précisément, vous ignoriez complètement les collisions. La mise en œuvre de la liste de répertorie populaire-de-liaison, par exemple n'est pas un tableau plat . Et non, si vous voulez étirer des objets de cette façon, un tableau simple serait une table de hachage avec une fonction de hachage d'identité --- qui n'est qu'une fonction de hash dans le sens le plus fondamental. S'il vous plaît, ne mettez pas de mots dans ma bouche, car je n'ai jamais dit l'accent sur aucune structure de données comme celle-ci, juste cette recherche rapide des clés est plus important que les problèmes de mise en œuvre.
Un tableau est un cas particulier d'un dictionnaire (ou, alternativement, un dictionnaire est une généralisation de la matrice). Les dictionnaires sont souvent mis en œuvre à l'aide de tables de hachage. Par conséquent, ce n'est pas un énorme étirement d'appeler un tableau un cas particulier de table de hachage.
Roger: Je ne voulais pas mettre des mots dans la bouche, comprendre simplement ce que vous disiez. À votre santé!
Je pense que c'est clairement un cas particulier d'une table de hachage parfaite. Je pense aussi que ce n'est pas une description particulièrement utile - c'est plus directement un cas particulier d'un tableau.
Oui, il est parfois utilisé dans des bases de données, par exemple PostgreSQL. Comme mentionne Wikipedia:
Certains systèmes de base de données qui ne font pas Offrez des index bitmap persistants bitmaps interne pour accélérer la requête En traitement. Par exemple, PostgreSQL versions 8.1 et ultérieure implémenter un "Numérisation de l'index bitmap" d'optimisation à accélérer la logique complexe arbitraire complexe Opérations entre index disponibles sur une seule table.
(de http://en.wikipedia.org/wiki/bitmap_index ) < / p>
Ce n'est pas une réponse, mais ... sûrement
importer des ensembles aurait été une option ici?Pas besoin de
Importer des ensembles plus.SET s sont des produits.Ouais, les ensembles sont bons.
One = Set (LST1); deux = set (LST2); Union = un | deux; inter = un et deux .Et croyez-le ou non
Oneminustwo = un - deux .Je pense qu'il y a une disparition - dans la dernière ligne de code. Actuellement, les deux dernières lignes calculent la même liste.
"Cela a sûrement été inventé avant et a un nom." Clarifier "ceci", s'il vous plaît; Je pense que nous avons 4 réponses et 4 interprétations différentes sur ce que vous voulez dire.
C'est le même concept derrière
Enumset : Java.sun.com/j2se/1.5.0/docs/ajava/util/enumset.html La documentation de cette classe utilise le terme "bit vecteur" comme certaines des réponses ci-dessous indiquez.@Jason, ETS sont super, mais réfléchissez à la durée de fonctionnement.
@IPTHNC: Je m'attendrais à ce que les opérations définies soient plus rapides, principalement parce qu'elles sont mises en œuvre dans C. Je ne l'ai pas mesurée cependant.