Python сравнивает каждую строку в файле со всеми остальными

Question

Я реализую статистическую программу и создал узкое место производительности, и надеялся, что я смогу получить некоторую помощь от сообщества, чтобы, возможно, указать мне направление оптимизации.

Я создаю набор для каждой строки в файле и нахожу пересечение этого набора путем сравнения заданных данных каждой строки в одном файле. Затем я использую размер этого пересечения для фильтрации определенных наборов с выхода. Проблема в том, что у меня есть вложенный цикл (O (n)), а стандартный размер файлов, входящих в программу, составляет чуть более 20 000 строк. Я приурочил алгоритм и до 500 строк, он работает примерно через 20 минут, но для больших файлов требуется около 8 часов.

У меня есть 16 ГБ оперативной памяти и значительно быстрый 4-ядерный процессор Intel i7. Я не заметил существенных различий в использовании памяти, скопировав список1 и используя второй список для сравнения, вместо того, чтобы снова открывать файл (возможно, это потому, что у меня SSD?). Я думал, что механизм «с открытым» читает/записывает непосредственно на жесткий диск, который медленнее, но не заметил разницы при использовании двух списков. Фактически, программа редко использует более 1 ГБ ОЗУ во время работы.

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

import ast, sys, os, shutil 
list1 = [] 
end = 0 
filterValue = 3 

# creates output file with filterValue appended to name 
with open(arg2 + arg1 + "/filteredSets" + str(filterValue) , "w") as outfile: 
    with open(arg2 + arg1 + "/file", "r") as infile: 
     # create a list of sets of rows in file 
     for row in infile: 
      list1.append(set(ast.literal_eval(row))) 

      infile.seek(0) 
      for row in infile: 
       # if file only has one row, no comparisons need to be made 
       if not(len(list1) == 1): 
       # get the first set from the list and... 
        set1 = set(ast.literal_eval(row)) 
        # ...find the intersection of every other set in the file 
        for i in range(0, len(list1)): 
         # don't compare the set with itself 
         if not(pos == i): 
          set2 = list1[i] 
          set3 = set1.intersection(set2) 
          # if the two sets have less than 3 items in common 
          if(len(set3) < filterValue): 
           # and you've reached the end of the file 
           if(i == len(list1)): 
            # append the row in outfile 
            outfile.write(row) 
            # increase position in infile 
            pos += 1 
          else: 
           break 
         else: 
          outfile.write(row) 

ввода образца будет файл с этим форматом:

[userID1, userID2, userID3] 
[userID5, userID3, userID9] 
[userID10, userID2, userID3, userID1] 
[userID8, userID20, userID11, userID1] 

Выходной файл, если это было входной файл будет:

[userID5, userID3, userID9] 
[userID8, userID20, userID11, userID1] 

... потому что два снятых набора содержали три или более одинаковых идентификатора пользователя.

Answer 1

Прежде всего, пожалуйста, упаковать ваш код в функции, которые делают одну вещь хорошо.

def get_data(*args): 
    # get the data. 

def find_intersections_sets(list1, list2): 
    # do the intersections part. 

def loop_over_some_result(result): 
    # insert assertions so that you don't end up looping in infinity: 
    assert result is not None 
    ... 

def myfunc(*args): 
    source1, source2 = args 
    L1, L2 = get_data(source1), get_data(source2) 
    intersects = find_intersections_sets(L1,L2) 
    ... 

if __name__ == "__main__": 
    myfunc() 

, то вы можете легко профилировать код с помощью:

if __name__ == "__main__": 
    import cProfile 
    cProfile.run('myfunc()') 

, которая дает неоценимый понимание вашего поведения кода и позволяет отследить логические ошибки. Более подробную информацию о Cprofile см How can you profile a python script?

вариант для того чтобы отследить логический изъян (все мы люди, не так ли?) Является пользователем функция тайм-аута в украсьте как this (python2) или this (python3):

Настоящим myfunc может быть изменено на:

def get_data(*args): 
    # get the data. 

def find_intersections_sets(list1, list2): 
    # do the intersections part. 

def myfunc(*args): 
    source1, source2 = args 
    L1, L2 = get_data(source1), get_data(source2) 

    @timeout(10) # seconds <---- the clever bit! 
    intersects = find_intersections_sets(L1,L2) 
    ... 

... где операция таймаута вызовет ошибку, если она занимает слишком много времени.

Вот моя догадка:

import ast 

def get_data(filename): 
    with open(filename, 'r') as fi: 
     data = fi.readlines() 
    return data 

def get_ast_set(line): 
    return set(ast.literal_eval(line)) 

def less_than_x_in_common(set1, set2, limit=3): 
    if len(set1.intersection(set2)) < limit: 
     return True 
    else: 
     return False 

def check_infile(datafile, savefile, filtervalue=3): 
    list1 = [get_ast_set(row) for row in get_data(datafile)] 
    outlist = [] 
    for row in list1: 
     if any([less_than_x_in_common(set(row), set(i), limit=filtervalue) for i in outlist]): 
      outlist.append(row) 
    with open(savefile, 'w') as fo: 
     fo.writelines(outlist) 

if __name__ == "__main__": 
    datafile = str(arg2 + arg1 + "/file") 
    savefile = str(arg2 + arg1 + "/filteredSets" + str(filterValue)) 
    check_infile(datafile, savefile) 

Answer 2

Этот ответ не о том, как разделить код в функции, переменные имя и т.д. Речь идет о более быстрый алгоритм с точки зрения сложности.

---

Я бы использовал словарь. Не будет писать точный код, вы можете сделать это сами.

Sets = dict() 
for rowID, row in enumerate(Rows): 
    for userID in row: 
    if Sets.get(userID) is None: 
     Sets[userID] = set() 
    Sets[userID].add(rowID) 

Итак, теперь у нас есть словарь, который можно использовать для быстрого получения рядов строк, содержащих заданный идентификатор пользователя.

BadRows = set() 
for rowID, row in enumerate(Rows): 
    Intersections = dict() 
    for userID in row: 
    for rowID_cmp in Sets[userID]: 
     if rowID_cmp != rowID: 
     Intersections[rowID_cmp] = Intersections.get(rowID_cmp, 0) + 1 
    # Now Intersections contains info about how many "times" 
    # row numbered rowID_cmp intersectcs current row 
    filteredOut = False 
    for rowID_cmp in Intersections: 
    if Intersections[rowID_cmp] >= filterValue: 
     BadRows.add(rowID_cmp) 
     filteredOut = True 
    if filteredOut: 
    BadRows.add(rowID) 

Наличие rownumbers всех отфильтрованных строк, сохраненных в BadRows, теперь мы делаем итерации один последний раз:

for rowID, row in enumerate(Rows): 
    if rowID not in BadRows: 
    # output row 

Это работает в 3 сканирований и в O (NlogN) времени. Возможно, вам придется переработать итерации массива Rows, потому что это файл в вашем случае, но на самом деле он сильно не меняется.

Не уверен в синтаксисе и деталях python, но вы получаете идею моего кода.