Recherche dans un grand ensemble de données

Question

Comment chercher dans une liste avec ~ 5 mil 128bit (ou 256, selon la façon dont vous le regardez) chaînes rapidement et trouver les doublons (en python)? Je peux transformer les cordes en nombres, mais je ne pense pas que ça va aider beaucoup. Puisque je n'ai pas appris beaucoup de théorie de l'information, y a-t-il quelque chose à ce sujet dans la théorie de l'information?

et puisque ceux-ci sont déjà hash, il est inutile de les hacher à nouveau

Answer 1

Est-ce tableau trié? Je pense que la solution la plus rapide peut être un tri de tas ou un tri rapide, et après avoir parcouru le tableau, et trouver les doublons.

Answer 2

Chargez-les dans la mémoire (5M x 64B = 320MB), triez-les et parcourez-les pour trouver les doublons.

Answer 3

Dans Python2.7 +, vous pouvez utiliser collections.Counter pour les anciennes versions de Python collections.deaultdict(int). De toute façon est O (n).

d'abord une liste avec quelques hash dans ce

>>> import hashlib 
>>> s=[hashlib.sha1(str(x)).digest() for x in (1,2,3,4,5,1,2)] 
>>> s 
['5j\x19+y\x13\xb0LTWM\x18\xc2\x8dF\xe69T(\xab', '\xdaK\x927\xba\xcc\xcd\xf1\x9c\x07`\xca\xb7\xae\xc4\xa85\x90\x10\xb0', 'w\xdeh\xda\xec\xd8#\xba\xbb\xb5\x8e\xdb\x1c\x8e\x14\xd7\x10n\x83\xbb', '\x1bdS\x89$s\xa4g\xd0sr\xd4^\xb0Z\xbc 1dz', '\xac4x\xd6\x9a<\x81\xfab\xe6\x0f\\6\x96\x16ZN^j\xc4', '5j\x19+y\x13\xb0LTWM\x18\xc2\x8dF\xe69T(\xab', '\xdaK\x927\xba\xcc\xcd\xf1\x9c\x07`\xca\xb7\xae\xc4\xa85\x90\x10\xb0'] 

Si vous utilisez python2.7 ou plus tard

>>> from collections import Counter 
>>> c=Counter(s) 
>>> duplicates = [k for k in c if c[k]>1] 
>>> print duplicates 
['\xdaK\x927\xba\xcc\xcd\xf1\x9c\x07`\xca\xb7\xae\xc4\xa85\x90\x10\xb0', '5j\x19+y\x13\xb0LTWM\x18\xc2\x8dF\xe69T(\xab'] 

si vous utilisez python2.6 ou plus tôt

>>> from collections import defaultdict 
>>> d=defaultdict(int) 
>>> for i in s: 
... d[i]+=1 
... 
>>> duplicates = [k for k in d if d[k]>1] 
>>> print duplicates 
['\xdaK\x927\xba\xcc\xcd\xf1\x9c\x07`\xca\xb7\xae\xc4\xa85\x90\x10\xb0', '5j\x19+y\x13\xb0LTWM\x18\xc2\x8dF\xe69T(\xab'] 

Answer 4

Si cela correspond à la même chose, utilisez set(). Je pense que ce sera plus rapide que le tri. O (n log n) pour 5 millions d'articles va vous coûter cher.

Si cela ne rentre pas dans la mémoire, disons que vous avez plus de 5 millions d'enregistrements, diviser et conquérir. Briser les records au milieu comme 1 x 2^127. Appliquez l'une des méthodes ci-dessus. Je suppose que la théorie de l'information permet d'affirmer qu'une bonne fonction de hachage distribuera les touches uniformément. Donc, la méthode de division par point milieu devrait fonctionner très bien.

Vous pouvez également appliquer une division et une conquête, même si elles s'inscrivent dans la mémoire. Le tri des enregistrements 2 x 2,5 mil est plus rapide que le tri des enregistrements 5 mil.

Answer 5

Vous dites que vous avez une liste d'environ 5 millions de chaînes et que la liste peut contenir des doublons. Vous ne dites pas (1) ce que vous voulez faire avec les doublons (consignez-les, supprimez toutes sauf une occurrence, ...) (2) ce que vous voulez faire avec les non-doublons (3) si cette liste est une structure autonome ou si les chaînes sont des clés pour d'autres données que vous n'avez pas mentionnées (4) pourquoi vous n'avez pas supprimé les doublons au moment de l'entrée au lieu de construire une liste contenant des doublons. En tant qu'exercice de structure de données et d'algorithmes 101, la réponse que vous avez acceptée est un non-sens. Si vous avez assez de mémoire, la détection des doublons en utilisant un ensemble devrait être plus rapide que de trier une liste et de l'analyser. Notez que la suppression de M éléments d'une liste de taille N est O (MN). Le code pour chacune des différentes alternatives est court et plutôt évident; Pourquoi n'essaies-tu pas de les écrire, de les chronométrer et de faire un rapport?

S'il s'agit d'un problème du monde réel, vous devez fournir beaucoup plus d'informations si vous voulez une réponse sensée.