Оптимизация циклов с большими наборами данных Python

Question

Это первый раз, когда я так сильно разбираюсь в Python, поэтому мне нужна помощь.

У меня есть MongoDB (или питона Dict) со следующей структурой:

{ 
    "_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 фотографий.

Есть ли более эффективный способ создания вышеуказанных циклов? Может быть, Multithreads, JIT, больше индексов? Потому что, если я запустил выше в одной нити, можно получить до 20000^2 * 2000 * 10 результатов ...

Так как же я могу более эффективно справиться с вышеуказанной проблемой? Благодаря

Answer 1

@YuchenXie и предлагаемые микрооптимизации PaulMcGuire, вероятно, не являются вашей основной проблемой, а именно, что вы зацикливаете более 20 000 x 20 000 = 400 000 000 пар записей, а затем имеете внутренний цикл из 2000 x 2000 пар пользователей. Это будет медленно.

К счастью, внутренняя петля может быть выполнена намного быстрее путем предварительного кэширования set с идентификаторов пользователя в i['users'] и замены внутреннего контура простым пересечением. Это изменяет операцию O(num_users^2), которая происходит в интерпретаторе Python, на операцию O(num_users), происходящую на C, что должно помочь. (Я просто приурочил его к списку целых чисел размером 2000, на моем компьютере он прошел с 156 мс, как вы делаете это до 41 мкс таким образом, для ускорения в 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 
     ]) 

Надеется, что это должно быть достаточным количеством ускорения. Если нет, возможно, что предложение @ YuchenXie поможет, хотя я сомневаюсь, потому что stdlib/OS достаточно хороша для буферизации такого рода вещей. (Вы можете играть с настройками буферизации в файловых объектах.)

В противном случае это может привести к попытке получить циклы ядра из Python (в Cython или рукописный C) или дать PyPy выстрел. Я сомневаюсь, что теперь вы получите огромные ускорения.

Вы также можете подтолкнуть вычисления тяжелых весов к Монго, что может быть разумнее в этом; Я никогда не использовал его, поэтому не знаю.

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

Шея бутылки - диск ввода-вывода.

Это должно быть намного быстрее, когда вы объединяете результаты и используете один или несколько вызовов writerows вместо многих writerow.