使用大數據集優化循環Python

Question

這是我第一次用Python做這麼大的工作，所以我需要一些幫助。

我有一個MongoDB的（或Python字典）結構如下：

{ 
    "_id": { "$oid" : "521b1fabc36b440cbe3a6009" }, 
    "country": "Brazil", 
    "id": "96371952", 
    "latitude": -23.815124482000001649, 
    "longitude": -45.532670811999999216, 
    "name": "coffee", 
    "users": [ 
    { 
     "id": 277659258, 
     "photos": [ 
     { 
      "created_time": 1376857433, 
      "photo_id": "525440696606428630_277659258", 
     }, 
     { 
      "created_time": 1377483144, 
      "photo_id": "530689541585769912_10733844", 
     } 
     ], 
     "username": "foo" 
    }, 
    { 
     "id": 232745390, 
     "photos": [ 
     { 
      "created_time": 1369422344, 
      "photo_id": "463070647967686017_232745390", 
     } 
     ], 
     "username": "bar" 
    } 
    ] 
} 

現在，我要創建兩個文件，一個與摘要和其他與每個連接的權重。我的環路，適用於小型數據集如下：

#a is the dataset 
data = db.collection.find() 
a =[i for i in data] 

#here go the connections between the locations 
edges = csv.writer(open("edges.csv", "wb")) 
#and here the location data 
nodes = csv.writer(open("nodes.csv", "wb")) 

for i in a: 

    #find the users that match 
    for q in a: 
     if i['_id'] <> q['_id'] and q.get('users') : 
      weight = 0 
      for user_i in i['users']: 
       for user_q in q['users']: 
        if user_i['id'] == user_q['id']: 
         weight +=1 
      if weight>0: 
       edges.writerow([ i['id'], q['id'], weight]) 


    #find the number of photos 
    photos_number =0 
    for p in i['users']: 
     photos_number += len(p['photos']) 


    nodes.writerow([ i['id'], 
        i['name'], 
        i['latitude'], 
        i['longitude'], 
        len(i['users']), 
        photos_number 
       ]) 

的結垢問題：我有20000點的位置，每個位置最多可以有2000個用戶，每個用戶可能有大約10張照片。

有沒有更有效的方法來創建上述循環？也許多線程，JIT，更多的索引？ 因爲如果我在單線程中運行以上可以達到20000^2 * 2000 * 10的結果...

那麼我怎樣才能更有效地處理上述問題呢？ 感謝

Answer 1

@YuchenXie和@ PaulMcGuire建議的微優化可能不是您的主要問題，即您循環使用20,000 x 20,000 = 400,000,000對條目，然後有一個2,000 x 2000用戶對的內部循環。這會很慢。

幸運的是，通過對i['users']中的用戶id進行預緩存set s，並用一個簡單的集合交點替換您的內部循環，可以使內部循環快得多。這會將在Python解釋器中發生的O(num_users^2)操作更改爲發生在C中的O(num_users)操作，這應該有所幫助。 （我只是用2000的整數列表對它進行計時;在我的計算機上，它從你做這件事的方式從156ms到41μs，對於4000倍的加速時間。）

你也可以切掉一半你注意到這個關係是對稱的，因此你可以在i = a[1],q = a[2]和i = a[2],q = a[1]這兩個點都沒有意義。

考慮到這些，並@ PaulMcGuire的建議綜合考慮，與其他文體的改動，你的代碼變得（警告：今後未經測試的代碼）：

from itertools import combinations, izip 

data = db.collection.find() 
a = list(data) 

user_ids = [{user['id'] for user in i['users']} if 'users' in i else set() 
      for i in a] 

with open("edges.csv", "wb") as f: 
    edges = csv.writer(f) 
    for (i, i_ids), (q, q_ids) in combinations(izip(a, user_ids), 2): 
     weight = len(i_ids & q_ids) 
     if weight > 0: 
      edges.writerow([i['id'], q['id'], weight]) 
      edges.writerow([q['id'], i['id'], weight]) 

with open("nodes.csv", "wb") as f: 
    nodes = csv.writer(f) 
    for i in a: 
     nodes.writerow([ 
      i['id'], 
      i['name'], 
      i['latitude'], 
      i['longitude'], 
      len(i['users']), 
      sum(len(p['photos']) for p in i['users']), # total number of photos 
     ]) 

希望這應該是足夠的加速的。如果沒有，那麼@雨辰謝的建議可能會有所幫助，儘管我很懷疑，因爲stdlib/OS在緩衝這種事情方面相當不錯。 （你可以使用文件對象上的緩衝設置。）

否則，它可能會歸結爲嘗試從Python（在Cython或手寫的C）中獲取核心循環，或給PyPy一個鏡頭。儘管如此，我懷疑這會給你帶來什麼巨大的加速。

您也可以將重量計算推入Mongo，這可能會更聰明;我從來沒有真正使用它，所以我不知道。

Answer 2

是否崩潰這個循環：

photos_number =0 
for p in i['users']: 
    photos_number += len(p['photos']) 

到：

photos_number = sum(len(p['photos']) for p in i['users']) 

幫助呢？

你的體重計算：

 weight = 0 
     for user_i in i['users']: 
      for user_q in q['users']: 
       if user_i['id'] == user_q['id']: 
        weight +=1 

也應該是可摺疊到：

 weight = sum(user_i['id'] == user_q['id'] 
         for user_i,user_q in product([i['users'],q['users'])) 

由於真等同於1，彙總所有的布爾條件是一樣的計數所有的值真正。

Answer 3

瓶頸是磁盤I/O。

當您合併結果並使用一個或多個writerows而不是多個writerow時，它應該快得多。