比較python中Gigant Two Dimen列表中的一個列表的值，最快的方法是什麼？

Question

我想比較一個列表的值是否存在於其他列表的值中。它們是巨大的（來自數據庫的50k +項目）。

編輯：

我也想標記，是複製爲複製=真記錄並保存在表中供以後refrence。

這裏列出瞭如何：

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 

但似乎太長，在較大的列表（50K VS 50K記錄+），它跑了超過5000秒，從來沒有做過，似乎永無止境的循環？ 我運行的服務器有4 GB的ram和4個內核。顯然我做錯了什麼。

請幫助..非常感謝！

解決：

快譯通指數映射方法是快了很多！ （當mysql表未被索引時，請注意我沒有對索引表進行測試）。

它的20秒對30毫秒= 20 * 1000/30 = 666次！ LOL

Answer 1

的最快方法就是用這樣的字典：

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 

這幾乎是算法散列連接

---

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 

將是在此的SQL /蟒溶液I採取重複的列，並用它來存儲這一個被認爲是其消息是

一個重複的郵件表。將至少：

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

Answer 2

你最好用SQL查找重複項。例如，請參閱this page describing how to find duplicates。

將所有這些結果爲Python和處理它們永遠不會是非常快的，但如果你一定要，你最好的選擇是有校驗，以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

你在做什麼錯的是：

• 你或許可以直接從數據庫中獲取結果。它比Python快得多。
• 您正在對校驗和進行線性搜索，這意味着每個50k條目都與相比較，其他每個50k條目的 ......這是大量的比較。

你應該做的是在校驗和上建立一個索引。做一個字典，地圖checksum -> entry。當您插入條目時，請檢查校驗和是否已經存在，如果是，則條目是重複的。

或者你只是使用你的數據庫，他們喜歡索引。

Answer 4

最後，感謝所有答案，我發現字典映射非常快！比SQL查詢快很多。

這是我的SQL查詢測試（它看起來很尷尬，但它是Web2pyDAL查詢的語法）。

我測試了兩條3500條記錄，並且只測試了超過250000條記錄的字典映射。

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在：

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 

約28秒 繼承人的字典基於索引地圖根據丹·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()) 

結果：

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 

只什麼？ 30毫秒！

並且讓我們看看它是如何對重複刪除250k記錄做的！

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 

不到一分鐘！

感謝所有的答案，我想選擇所有那些指出我正確的方式，但丹D給我最詳細的答案！謝謝丹！