比較龐大的python字典列表

Question

我從來沒有想到我會遇到python的速度問題，但我有。我試圖根據字典值來比較真正的大字典列表。我比較兩個列表，第一個像這樣

biglist1=[{'transaction':'somevalue', 'id':'somevalue', 'date':'somevalue' ...}, {'transactio':'somevalue', 'id':'somevalue', 'date':'somevalue' ...}, ...] 

隨着「someValue中」長期爲用戶生成的字符串，整數或小數點。現在，第二個列表非常相似，除了id值始終爲空，因爲它們尚未分配。

biglist2=[{'transaction':'somevalue', 'id':'', 'date':'somevalue' ...}, {'transactio':'somevalue', 'id':'', 'date':'somevalue' ...}, ...] 

所以我想在biglist2匹配字典中biglist1所有其他鍵除了 ID的詞典列表。

我一直在做

for item in biglist2: 
    for transaction in biglist1: 
     if item['transaction'] == transaction['transaction']: 
      list_transactionnamematches.append(transaction) 

for item in biglist2: 
    for transaction in list_transactionnamematches: 
     if item['date'] == transaction['date']: 
      list_transactionnamematches.append(transaction) 

...等等，而不是比較ID值，直到我獲得比賽的最終名單。由於列表可能非常大（每個列表大約有3000+項），因此Python需要一段時間來循環。

我猜這不是真的如何進行這種比較。有任何想法嗎？

Answer 1

您想要用於查找的字段的索引。 O（n + m）

matches = [] 
biglist1_indexed = {} 

for item in biglist1: 
    biglist1_indexed[(item["transaction"], item["date"])] = item 

for item in biglist2: 
    if (item["transaction"], item["date"]) in biglist1_indexed: 
     matches.append(item) 

這可能比你現在做的要快上千倍。

Answer 2

你想要做的就是用正確的數據結構：

1. 創建其他值的元組的映射的字典在第一字典其ID。

2. 在兩個字典中創建兩組值。然後使用set操作來獲取你想要的元組。

3. 使用從點1的字典爲這些元組分配id。

Answer 3

在O（m * n個）...

for item in biglist2: 
    for transaction in biglist1: 
     if (item['transaction'] == transaction['transaction'] && 
      item['date'] == transaction['date'] && 
      item['foo'] == transaction['foo']) : 

      list_transactionnamematches.append(transaction) 

Answer 4

請原諒我的生鏽的Python語法，它已經有一段時間，所以認爲這部分僞

import operator 
biglist1.sort(key=(operator.itemgetter(2),operator.itemgetter(0))) 
biglist2.sort(key=(operator.itemgetter(2),operator.itemgetter(0))) 
i1=0; 
i2=0; 
while i1 < len(biglist1) and i2 < len(biglist2): 
    if (biglist1[i1]['date'],biglist1[i1]['transaction']) == (biglist2[i2]['date'],biglist2[i2]['transaction']): 
     biglist3.append(biglist1[i1]) 
     i1++ 
     i2++ 
    elif (biglist1[i1]['date'],biglist1[i1]['transaction']) < (biglist2[i2]['date'],biglist2[i2]['transaction']): 
     i1++ 
    elif (biglist1[i1]['date'],biglist1[i1]['transaction']) > (biglist2[i2]['date'],biglist2[i2]['transaction']): 
     i2++ 
    else: 
     print "this wont happen if i did the tuple comparison correctly" 

這兩種排序按（日期，交易）列出相同的順序。然後，它們並排走過它們，逐步尋找相對相鄰的比賽。它假定（日期，交易）是獨一無二的，並且我不完全偏離我的搖桿，關於元組的排序和比較。

Answer 5

我可能會採取這種做法是做一個非常非常輕量級的類與一個實例變量和一個方法。實例變量是一個指向字典的指針;該方法將覆蓋內置的特殊方法__hash__(self)，返回除id之外的字典中的所有值計算得出的值。

從那裏的解決方案似乎相當明顯：創建兩個初始爲空的字典：在每個列表N和M（用於無匹配和比賽）循環只有一次，併爲每一個代表一個交易這些字典（我們稱之爲Tx_dict），創建一個新類的實例（一個Tx_ptr）。然後測試Tx_ptr與Tx_ptr中N和M的匹配項：如果N中沒有匹配項，則將當前的Tx_ptr插入到N中;如果N中有匹配的項目但M中沒有匹配的項目，請將當前的Tx_ptr插入M，將Tx_ptr本身作爲關鍵字，並將包含Tx_ptr的列表作爲值插入;如果N和M中存在匹配的項目，請將當前的Tx_ptr附加到與M中該密鑰關聯的值。

在您完成每個項目一次後，您的字典M將包含指向與其他交易相匹配的所有交易的指針，所有這些交易都整齊地分組到列表中。

編輯：糟糕！顯然，正確的動作，如果有一個在M匹配NTx_ptr但並非是插入一個鍵值對到M與當前Tx_ptr爲關鍵和價值，當前Tx_ptr和的Tx_ptr名單那已經在N。

Answer 6

看看Psyco。它是一個Python編譯器，可以從源代碼創建非常快速，優化的機器代碼。

http://sourceforge.net/projects/psyco/

雖然這不是直接的解決方案，你的代碼的效率問題，它仍然可以提高執行速度，而無需編寫任何新的代碼。也就是說，我仍然強烈建議儘可能優化您的代碼，並使用Psyco儘可能多地減少速度。

他們的指南的一部分特別談論使用它來加快列表，字符串和數字計算繁重的功能。

http://psyco.sourceforge.net/psycoguide/node8.html

Answer 7

我也是新手。我的代碼的結構與他的方式非常相似。

for A in biglist: 
    for B in biglist: 
     if (A.get('somekey') <> B.get('somekey') and #don't match to itself 
      len(set(A.get('list')) - set(B.get('list'))) > 10: 
      [do stuff...] 

這需要數小時才能運行10000個字典的列表。每個字典都包含很多東西，但是我可能只需ids（'somekey'）和列表（'list'）並將其重寫爲10000個鍵：值對的單個字典。

問題：那會多快？我認爲這比使用列表清單快，對嗎？