2009-08-19 34 views
3

添加類型的字典列表說我有一堆字典以最快的方式鍵明智一起蟒蛇

a = {'x': 1.0, 'y': 0.5, 'z': 0.25 } 
b = {'w': 0.5, 'x': 0.2 } 

的有隻有兩個都有,但問題是關於一個arbitary量。

找到每個鍵的平均值的最快方法是什麼?這些字典非常稀少,所以會有很多情況下很多密鑰不存在於各種字典中。

我正在尋找的結果是一個新的字典,其中包含所有的鍵和每個的平均值。這些值總是浮動的,我很樂意蘸入ctypes。我的方法比我想要的要慢,可能是因爲在我的情況下,我使用的是defaultdicts,這意味着我實際上正在初始化值,即使它們不在那裏。如果這是緩慢的原因,我很樂意重構,只是想確保我沒有錯過任何明顯的東西。

編輯:我覺得我爲這個結果應該是什麼樣的誤導,如果該值不存在,它應該爲0.0行事,所以上面例子中的結果將是:

{'w':0.25,'x':0.6,'y':0.25,'z':0.125} 

所以除以唯一鍵的總數。

我想知道的主要是如果有一種偷偷摸摸的方式來按照一個步驟的長度來分割整個字典,或者在一個步驟中添加。基本上是一個非常快的矢量加法和除法。我簡單地看過numpy數組,但它們似乎不適用於字典,如果將字典轉換爲列表,我必須刪除稀疏屬性(通過將缺省值明確設置爲0)。

+0

對於那些迄今爲止已經回答的人們,我要感謝一下,我正在調查哪種方法對我來說性能最好。 – 2009-08-20 15:28:07

回答

2

它可以通過分析可以證明,這是不太最快的,但...

import collections 

a = {'x': 1.0, 'y': 0.5, 'z': 0.25 } 
b = {'w': 0.5, 'x': 0.2 } 
dicts = [a,b] 

totals = collections.defaultdict(list) 
avg = {} 

for D in dicts: 
    for key,value in D.iteritems(): 
     totals[key].append(value) 

for key,values in totals.iteritems(): 
    avg[key] = sum(values)/len(values) 

猜測,允許Python的使用內建sum()len()打算在計算平均值時獲得一些性能,因爲您會看到新的值,但我肯定會錯的。

2

這工作:

import collections 

data= [ 
    {'x': 1.0, 'y': 0.5, 'z': 0.25 }, 
    {'w': 0.5, 'x': 0.2 } 
    ] 

tally = collections.defaultdict(lambda: (0.0, 0)) 

for d in data: 
    for k,v in d.items(): 
     sum, count = tally[k] 
     tally[k] = (sum+v, count+1) 

results = {} 
for k, v in tally.items(): 
    t = tally[k] 
    results[k] = t[0]/t[1] 

print results 

我不知道這是否是比你更快,因爲你還沒有貼出你的代碼。

{'y': 0.5, 'x': 0.59999999999999998, 'z': 0.25, 'w': 0.5} 

我在理貨試圖避免再次存儲所有的值,簡單地累加之和計算我需要計算平均值的結尾。通常情況下,Python程序中的時間瓶頸在內存分配器中,而使用較少的內存可以提高速度。

+0

我已經編輯了這個問題來澄清結果*應該是什麼 – 2009-08-19 17:58:52

1
>>> def avg(items): 
...  return sum(items)/len(items) 
... 
>>> hashes = [a, b] 
>>> dict([(k, avg([h.get(k) or 0 for h in hashes])) for k in set(sum((h.keys() for h in hashes), []))]) 
{'y': 0.25, 'x': 0.59999999999999998, 'z': 0.125, 'w': 0.25} 

說明:

  1. 在所有的哈希,沒有重複的組鍵。

    set(sum((h.keys() for h in hashes), [])) 
    
  2. 用於上述集合中的每個密鑰,使用0,如果值不特定的散列存在的平均值。

    (k, avg([h.get(k) or 0 for h in hashes])) 
    
+0

使用'item is not None'而不是'item!= None',這會快很多。 – balpha 2009-08-19 17:47:28

+0

我編輯了這個問題,以澄清結果*應該* – 2009-08-19 17:54:29

+0

編輯答案匹配。 – 2009-08-19 18:32:37

0

這可能是你的瓶頸可能是由於過多的內存使用。考慮使用iteritems來利用發電機的功率。

既然你說你的數據很稀疏,那可能不是最有效的。考慮迭代器的這個交替使用:

dicts = ... #Assume this is your dataset 
totals = {} 
lengths = {} 
means = {} 
for d in dicts: 
    for key,value in d.iteritems(): 
     totals.setdefault(key,0) 
     lengths.setdefault(key,0) 
     totals[key] += value 
     length[key] += 1 
for key,value in totals.iteritems(): 
    means[key] = value/lengths[key] 

這裏總計,長度和手段是你創建的唯一數據結構。這應該相當迅速,因爲它避免了創建輔助列表,並且每個字典只包含一次密鑰就只循環一次。

下面是我懷疑將是性能的改進在第一第二的辦法,但它理論上可以,取決於你的數據和機器,因爲它需要較少的內存分配:

dicts = ... #Assume this is your dataset 
key_set = Set([]) 
for d in dicts: key_set.update(d.keys()) 
means = {} 
def get_total(dicts, key): 
    vals = (dict[key] for dict in dicts if dict.has_key(key)) 
    return sum(vals) 
def get_length(dicts, key): 
    vals = (1 for dict in dicts if dict.has_key(key)) 
    return sum(vals) 
def get_mean(dicts,key): 
    return get_total(dicts,key)/get_length(dicts,key) 
for key in key_set: 
    means[key] = get_mean(dicts,key) 

你做最終循環遍歷每個鍵的所有字典兩次,但不需要key_set以外的中間數據結構。

0

scipy.sparse支持稀疏矩陣 - dok_matrix表格似乎比較適合您的需要(但您必須使用整數座標,因此需要單獨的通道來收集並放入任意但明確的字符串你目前擁有的鑰匙)。如果您擁有大量非常龐大而稀疏的「陣列」,性能提升可能會值得複雜化。

0

這很簡單,但是這可能是工作:

a = { 'x': 1.0, 'y': 0.5, 'z': 0.25 } 
b = { 'w': 0.5, 'x': 0.2 } 

ds = [a, b] 
result = {} 

for d in ds: 
    for k, v in d.iteritems(): 
     result[k] = v + result.get(k, 0) 

n = len(ds) 
result = dict((k, amt/n) for k, amt in result.iteritems()) 

print result 

我不知道如何比較你的方法,因爲你沒有張貼任何代碼。