Python：總結三層詞典的價值

給定一個包含三層鍵的詞典，總結這些值的最快方法是什麼？這是我目前的做法：Python：總結三層詞典的價值

from collections import defaultdict 

dicts = [ {'a':{'b':{'c':1}}}, {'a':{'b':{'c':4, 'e':3}}} ] 

def sum_three_deep_dict_values(dicts): 
    '''Read in two dicts and return a dictionary that contains their outer-joined keys and value sums''' 
    combined = defaultdict(lambda: defaultdict(lambda: defaultdict(int))) 
    for d in dicts: 
     for w1, val_dict in d.iteritems():   
      for w2 in val_dict.iterkeys():    
       for w3 in val_dict[w2].iterkeys(): 
        combined[w1][w2][w3] += d[w1][w2][w3] 
    return combined 

print sum_three_deep_dict_values(dicts)

這裏預期的輸出是{'a': {'b': {'c': 5, 'e': 3}}}的目標是要總結爲這兩個詞典都具有相同的鍵（如d[a][b][c]這裏），包括無論從字典中剩餘的鍵值對的值輸出字典。

有一些關於SO的問題似乎回答了這樣的問題：「如何總結嵌套字典的價值」？但是，我發現每個人都會遇到一些奇怪的特殊情況或參數，比如「合併/忽略第n層密鑰」或「在特定位置應用if條件」。因此，我想提出一個簡單的問題：在Python中彙總雙嵌套字典的值的最佳方法是什麼？

來源

2015-05-19 duhaime

你可以在第一層和第二層有多個鍵嗎？ –

哦，是的。我的實際密鑰大小約爲100,000; 1,000,000;第一層，第二層和第三層分別爲100,000,000。 – duhaime

並且期望的輸出是一個兩層深的字典，其中兩層的鍵與原始字典的鍵相同，但最後一個值是第三層中的值的總和？ –

我認爲你目前的方法總的來說是一個很好的方法。我的建議是儘可能消除字典查找。迭代鍵和值一起應該像遍歷鍵一樣快，所以你可以把它們組合起來。如果你這樣做，那麼最後調用d[w1][w2][w3]並不是必需的，也不是臨時密鑰查找。所以像這樣：

def sum_three_deep_dict_values(dicts): 
    '''Read in two dicts and return a dictionary that contains 
     their outer-joined keys and value sums''' 
    combined = defaultdict(lambda: defaultdict(lambda: defaultdict(int))) 
    for layer0 in dicts: 
     for k1, layer1 in layer0.iteritems(): 
      for k2, layer2 in layer1.iteritems(): 
       for k3, count in layer2.iteritems(): 
        combined[k1][k2][k3] += count 
    return combined

我冒昧地改變你的名字計劃咯。

如果您在測試上述內容後仍然擔心速度，則可能需要查看其他數據結構或第三方庫。但在你這樣做之前，試試PyPy - 我發現它通常給予vanilla for循環至少4倍的加速。

此外，請對照您的原始代碼進行測試。我認爲我上面的推理是成立的，但它仍然有點推測。我也很好奇別人的建議。在你工作的規模上，這可能是一個挑戰！（出於好奇，怎麼長這樣走你當前的代碼嗎？）

更新：我測試了這一點，它的確是更快，雖然只是由頭髮：

>>> %timeit sum_three_deep_original(dicts) 
1000 loops, best of 3: 1.38 ms per loop 
>>> %timeit sum_three_deep_edited(dicts) 
1000 loops, best of 3: 1.26 ms per loop

我猜你需要更多速度爲您的應用程序。我用PyPy嘗試過，我也用cython編譯它（但沒有任何修改或鍵入註釋）。 PyPy以66％的速度獲勝。再普通的Python（略有不同的參數，這一次）：

:~ $ python -c 'from tdsum import test; test()' 
1.63905096054

編譯時用Cython：

:~ $ python -c 'from tdsum import test; test()' 
1.224848032

而且使用PyPy：

:~ $ pypy -c 'from tdsum import test; test()' 
0.427165031433

我會用期待一個真正的用Cython版本定製的數據結構顯着優於PyPy。問題是你不能使用dict s，並且仍然會得到你想要的迭代加速，因爲cython不得不使用Python對象開銷。所以你必須實現你自己的哈希表！

我經常想知道爲什麼cython不能解決這個問題;也許有一個numpy類型可用。我會繼續尋找！

來源

2015-05-19 12:42:30 senderle

很好的解決方案和建議。 – erip

下面是一個解決方案，它針對任意深度嵌套的問題使用展平函數和展開函數。適合你的輸入，但沒有測試更多：

from collections import Counter 

def flatten(d, parent=None): 
    for k, v in d.items(): 
     keys = (k,) if parent is None else parent + (k,) 
     if isinstance(v, dict): 
      yield from flatten(v, keys) 
     else: 
      yield keys, v 

def puffup(c): 
    top = {} 
    for k, v in c.items(): 
     current = top # reset walk 
     for ki in k[:-1]: 
      if ki not in current: 
       current[ki] = {} 
     current[k[-1]] = v 
    return top 

dicts = [ {'a':{'b':{'c':1}}}, {'a':{'b':{'c':4, 'e':3}}} ] 
c = Counter() 
for d in dicts: 
    c += dict(flatten(d)) 
print(puffup(c)) 
# {'a': {'b': {'c': 5, 'e': 3}}}

我剛剛看到你正在尋找最快的。雖然靈活得多，但這比上面的答案慢了2.5倍，而且根本不需要調整輸入。

來源

2015-05-19 13:54:15 RodericDay

Python：總結三層詞典的價值

回答

相關問題