通過迭代Python字典非常緩慢

我試圖計算基於被分配給他們的項目的值對用戶之間的距離。但是，當兩個用戶沒有任何相交項目時，距離計算應該爲空。我也只計算距離矩陣的下半部分（例如，UserA-UserB等同於UserB-UserA，因此只計算一個）。通過迭代Python字典非常緩慢

所以我有這個以下Python腳本作品，但它真正開始的時候我給它超過幾百個用戶的隆隆。下面的示例腳本顯示了輸入結構，但我試圖做成千上萬，而不僅僅是我在這裏顯示的四個。

線s = {k:v for k,v in data.items() if k in (user1,user2)}似乎添加最開銷

import math 
from decimal import * 

def has_matching_product(data,user1,user2): 
    c1=set(data[user1].keys()) 
    c2=[k for k in data[user2].keys()] 
    return any([x in c1 for x in c2]) 

def get_euclidean_dist(data,user1,user2): 
    #Tried subsetting to run quicker? 
    s = {k:v for k,v in data.items() if k in (user1,user2)} 

    #Ignore users with no overlapping items 
    if has_matching_product(s,user1,user2): 
     items=set() 
     for k,v in s.items(): 
      for ki in v.keys(): 
       items.add(ki) 

     rs=Decimal(0) 
     for i in items: 
      p1 = s.get(user1).get(i) 
      p2 = s.get(user2).get(i) 
      v1 = p1 or 0 
      v2 = p2 or 0 

      rs+= Decimal((v1-v2)**2) 
     return math.sqrt(rs) 
    else: 
     return None 

#User/Product/Value 
raw_data = { 
    'U1': { 
     'I1':5, 
     'I4':2 
    }, 
    'U2': { 
     'I1':1, 
     'I3':6 
    }, 
    'U3': { 
     'I3':11 
    }, 
    'U4': { 
     'I4':9 
    } 
} 

users = sorted(raw_data.keys()) 
l = len(users) 

data_out = set() 
#Compute lower half of a distance matrix (unique pairs only) 
for u1 in range(0,l-1): 
    for u2 in range(1+u1,l): 
     dist = get_euclidean_dist(raw_data,users[u1],users[u2]) 
     print('{x} | {y} | {d}'.format(x=users[u1],y=users[u2],d=dist)) #Sample output

正確的輸出應該是什麼樣子：

U1 | U2 | 7.483314773547883 
U1 | U3 | None 
U1 | U4 | 8.602325267042627 
U2 | U3 | 5.0990195135927845 
U2 | U4 | None 
U3 | U4 | None

來源

2016-01-07 ElPresidente

爲什麼你需要'sqrt'？ –

距離函數是這樣https://en.wikipedia.org/wiki/Euclidean_distance – ElPresidente

'S = {K：數據[K]對於k在（用戶1，用戶2）如果k在數據}' –

的問題是，你走了整個字典每一次，只是找到你想要的兩個項目。而從外觀上來看，你拉出user s，然後花所有的時間試圖在data再次去找到它們。 @Peter伍德的建議將有助於一堆 - 只有抓住你首先希望兩個user S，但是這有點失蹤樹不見林 - 你不需要瘦下來你的字典擺在首位的。將它們放在一起：

import itertools 
for kv1, kv2 in itertools.combinations(data.items(), 2): 
    ## calculate distance directly here

來源

2016-01-07 14:17:15 dwanderson

是的，我建議的詞典理解是一種改進，但仍然需要爲每個用戶搜索鍵。您的解決方案完全解決了問題。 –

您正在使用十進制，它不是很快。字典已經是一組密鑰，因此創建額外的集合並不是必需的。您創建any一個列表，它必須計算所有值，使用發電機來代替。您正在使用get，因此您可以提供默認值。所以我得到這個：

import math 

def get_euclidean_dist(data,user1,user2): 
    c1 = data[user1] 
    c2 = data[user2] 
    #Ignore users with no overlapping items 
    if any(x in c1 for x in c2): 
     items = set(c1) 
     items.update(c2) 
     rs = sum((c1.get(i, 0)-c2.get(i, 0))**2 for i in items) 
     return math.sqrt(rs) 
    else: 
     return None

來源

2016-01-07 14:22:13 Daniel

通過迭代Python字典非常緩慢

回答

相關問題