Comparer la valeur d'une liste dans la liste Gigantic Two Dimen en python, le plus rapide?

Question

Je veux comparer si la valeur d'une liste existe dans la valeur de l'autre liste.Ils sont énormes (50k + articles, de la base de données).

EDIT:

Je veux aussi marquer l'enregistrement qui est reproduit en double = True et les garder dans la table pour refrence plus tard.

ici comment les listes sont:

n_emails=[db_id,checksum for id,checksum in search_results] 
#I want to compare checksum if exist inside same list or other list and retrieve id (db_id , if exist) 
#example : n_emails= [[1,'CAFEBABE010'],[2,'bfeafe3df1ds],[3,'deadbeef101'],[5,'CAFEBABE010']] 
#in this case i want to retrive id 1 and 5 coz they are same checksum 

for m in n_emails: 
    dups=_getdups(n_emails,m[1],m[0])   
    n_dups=[casesdb.duplicates.insert(**dup) for dup in dups] 
    if n_dups: 
     print "Dupe Found" 
     casesdb(casesdb.email_data.id == m[0]).update(duplicated=True) 

def _getdups(old_lst,em_md5,em_id): 
    dups=[] 
    for old in old_lst: 
     if em_md5==old[0] and old[1]!=em_id: 
      dups.append(dict(org_id=old[1],md5hash=old[0],dupID=em_id,)) 
    return dups 

Mais il semble trop long et plus grande liste (50k vs records 50k +) Il a couru pendant plus de 5000 secondes, jamais fait, ne semble jamais boucle sans fin? Le serveur que j'utilise possède 4 Go de RAM et 4 cœurs. De toute évidence, je fais quelque chose de mal.

S'il vous plaît aider .. merci beaucoup!

SOLVED:

Dict Index Mapping est une façon beaucoup plus rapide! (Lorsque la table mysql n'est pas indexée, veuillez noter que je n'ai pas testé la table indexée).

Ses 20 secondes contre 30 milisecondes = 20 * 1000/30 = 666 fois! LOL

Answer 1

le moyen le plus rapide est d'utiliser un dict comme ceci:

n_emails= [[1,'CAFEBABE010'],[2,'bfeafe3df1ds'],[3,'deadbeef101'],[5,'CAFEBABE010']] 

d = {} 
for id, hash in n_emails: 
    if hash not in d: 
     d[hash] = [id] 
    else: 
     d[hash].append(id) 

for hash, ids in d: 
    if len(ids) > 1: 
     print hash, ids 

c'est presque l'algorithme pour une jointure de hachage

---

for hash, count in select hash, count(id) as num from emails group by num having num > 1: 
    first = None 
    for index, id in enumerate(select id from emails where hash=hash sort by desc id): 
     if index == 0: 
      first = id 
      continue 
     update emails set duplicate=first where id=id 

serait la solution sql/python dans ce que je prends la colonne en double et l'utiliser pour stocker quel message celui-ci est considéré comme un double de

la table des e-mails serait au moins:

create table emails (id, hash, duplicate default null) 

Answer 2

Vous feriez mieux de rechercher des doublons avec SQL. Par exemple, voir this page describing how to find duplicates.

Tirer tous ces résultats en Python et leur traitement ne va jamais être très rapide, mais si vous devez, votre meilleur pari est d'avoir un dictionnaire de checksums aux ID:

got_checksums = {} 
for id, checksum in emails: 
    if checksum in got_checksums: 
     print id, got_checksums[checksum] 
    else: 
     got_checksums[checksum] = id 

Answer 3

Qu'est-ce que vous faites mal est:

• vous pouvez probablement obtenir le résultat directement à partir de la base de données. C'est beaucoup plus rapide que Python.
• Vous faites une recherche linéaire pour les checksums, ce qui signifie que chacune des 50k entrées est comparée à chaque des autres 50k entrées ... ce qui est un grand nombre de comparaisons.

Ce que vous devez faire est de construire un index sur les sommes de contrôle. Faire un dict qui mappe checksum -> entry. Lorsque vous insérez les entrées, vérifiez si la somme de contrôle existe déjà, si c'est le cas, l'entrée est un doublon.

Ou vous utilisez simplement votre base de données, ils aiment l'indexation.

Answer 4

Enfin, grâce à toutes les réponses, j'ai trouvé que la cartographie dict est incroyablement rapide! C'est beaucoup plus rapide que les requêtes SQL.

Voici mon test de requête SQL (cela semblera gênant, mais c'est la syntaxe des requêtes de Web2pyDAL).

J'ai testé à la fois pour 3500 enregistrements et seulement mappage dict contre plus de 250000 enregistrements.

print "de_duping started at %s" % str(datetime.datetime.now()) 

dupe_n = 0 
l_dupe_n = 0 
for em_hash in n_emails: 
    dup_ids=casesdb(casesdb.email_data.MD5Hash==em_hash[1]).select(casesdb.email_data.id) 
    if dup_ids>1: 
     dupe_n+=1 

print "Email Dupes %s" % (dupe_n) 
print "Local de_duping ended at %s" % str(datetime.datetime.now()) 

Resullts dans:

de_duping started at 2010-12-02 03:39:24.610888 
Email Dupes 3067 
Local de_duping ended at 2010-12-02 03:39:52.669849 

environ 28 secondes Heres la carte d'indexation basée dict basé sur Dan D

print "de_duping started at %s" % str(datetime.datetime.now()) 
    for id, hash in em_hash: 

      if hash not in dedupe_emails: 

       dedupe_emails[hash] = [id] 
      else: 

       dedupe_emails[hash].append(id) 
       dupe_n += 1 
       casesdb(casesdb.email_data.id == id).update(duplicated = True) 

    print "Email Dupes %s" % (dupe_n) 
    print "Local de_duping ended at %s" % str(datetime.datetime.now()) 

résultats dans:

de_duping started at 2010-12-02 03:41:21.505235 
Email Dupes 2591 # this is accurate as selecting from database regards first match as duplicate too 
Local de_duping ended at 2010-12-02 03:41:21.531899 

seulement ce ? 30 ms!

et laisse voir ce qu'il a fait contre les enregistrements 250k de-duper!

de_duping at 2010-12-02 03:44:20.120880 
Email Dupes 93567 
Local de_duping ended at 2010-12-02 03:45:12.612449 

Moins d'un min !!

Merci à toutes les réponses, je voudrais sélectionner tous ceux qui m'ont indiqué la bonne façon, mais Dan D me donner la réponse la plus détaillée! Merci Dan!