Как оптимизировать использование памяти и времени для следующего алгоритма в python

Question

Я пытаюсь выполнить следующую логическую операцию в Python, но получаю проблемы с памятью и временем. Поскольку, я очень новичок в python, руководство по тому, как и где оптимизировать проблему, будет оценено! (Я понимаю, что следующий вопрос несколько абстрактный)

import networkx as nx 
    dic_score = {} 
    G = nx.watts_strogatz_graph(10000,10,.01) # Generate 2 graphs with 10,000 nodes using Networkx 
    H = nx.watts_strogatz_graph(10000,10,.01) 
    for Gnodes in G.nodes() 
     for Hnodes in H.nodes() # i.e. For all the pair of nodes in both the graphs 
      score = SomeOperation on (Gnodes,Hnodes) # Calculate a metric 
      dic_score.setdefault(Gnodes,[]).append([Hnodes, score, -1 ]) # Store the metric in the form a Key: value, where value become a list of lists, pair in a dictionary 

Тогда Сортировка списков в сгенерированном словаре в соответствии с критерием, упомянутой здесь sorting_criterion

Мои проблемы/вопросы:

1) Есть ли лучший способ приблизиться к этому, чем использовать циклы for для итерации?

2) Какой должен быть самый оптимизированный (самый быстрый) способ приближения к вышеупомянутой проблеме? Должен ли я использовать другую структуру данных, чем словарь? или, возможно, файловые операции?

3) Поскольку мне нужно сортировать списки внутри этого словаря, который имеет 10 000 ключей, каждый из которых соответствует списку из 10 000 значений, требования к памяти становятся огромными довольно быстро, и у меня заканчивается.

3) Есть ли способ интегрировать процесс сортировки при вычислении самого словаря, т. Е. Избегать выполнения отдельного цикла для сортировки?

Любые входы будут оценены! Благодаря !

Answer 1

1) Вы можете использовать один функций от itertools модуль для этого. Позвольте мне говорить об этом, вы можете прочитать руководство или по телефону:

from itertools import product 
help(product) 

Вот пример:

for item1, item2 in product(list1, list2): 
    pass 

2) Если результат слишком велик, чтобы поместиться в памяти, попытайтесь сохранить их где-нибудь.Вы можете вывести его в файл CSV, например:

with open('result.csv') as outfile: 
    writer = csv.writer(outfile, dialect='excel') 
    for ... 
     writer.write(...) 

Это освободит вашу память.

3) Я думаю, что лучше отсортировать данные результата после этого (потому что функция sort довольно быстро), а не усложняет вопросы и сортирует данные на лету.

Вы можете использовать NumPy операции arroy/matrix (суммы, продукты или даже сопоставить функцию с каждой матричной строкой). Они настолько быстры, что иногда фильтрация данных стоит больше, чем вычисление всего.

Если ваше приложение по-прежнему очень медленно, попробуйте профилирование его, чтобы увидеть именно то, что операция происходит медленно или делается слишком много раз:

from cProfile import Profile 
p = Profile() 

p.runctx('my_function(args)', {'my_function': my_function, 'args': my_data}, {}) 
p.print_stats() 

Вы увидите таблицу:

 2706 function calls (2004 primitive calls) in 4.504 CPU seconds 

Ordered by: standard name 

ncalls tottime percall cumtime percall filename:lineno(function) 
    2 0.006 0.003 0.953 0.477 pobject.py:75(save_objects) 
    43/3 0.533 0.012 0.749 0.250 pobject.py:99(evaluate) 
... 

Answer 2

При работе с функциями, которые возвращают список, проверьте функцию, которая возвращает итератор.

Это улучшит использование памяти.

В вашем случае nx.nodes возвращает полный список. См.: nodes

Используйте nodes_iter, так как он возвращает итератор. Это должно гарантировать, что у вас нет полного списка узлов в памяти, итерации на узлах вашего цикла for.

См: nodes_iter

Некоторое улучшение:

import networkx as nx 
    dic_score = {} 
    G = nx.watts_strogatz_graph(10000,10,.01) 
    H = nx.watts_strogatz_graph(10000,10,.01) 
    for Gnodes in G.nodes_iter() ----------------> changed from G.nodes() 
     for Hnodes in H.nodes_iter() -----------> changed from H.nodes() 
      score = SomeOperation on (Gnodes,Hnodes) 
      dic_score.setdefault(Gnodes,[]).append([Hnodes, score, -1 ]) 

Вы также можете использовать другие идиомы, так как теперь у вас есть два итератора: использовать itertools.products

product(A, B) returns the same as ((x,y) for x in A for y in B). 

Answer 3

Другие упомянули itertools.product. Это хорошо, но в вашем случае есть еще одна возможность: выражение генератора для внутреннего цикла и функция sorted. (Разумеется, код непроверен.)

import networkx as nx 
from operator import itemgetter 
dic_score = {} 
G = nx.watts_strogatz_graph(10000,10,.01) # Generate 2 graphs with 10,000 nodes using Networkx 
H = nx.watts_strogatz_graph(10000,10,.01) 
for Gnodes in G.nodes(): 
    dic_score[Gnodes] = sorted([Hnodes, score(Gnodes, Hnodes), -1] for Hnodes in H.nodes(), key=operator.itemgetter(1)) # sort on score 

Внутренний цикл заменен выражением генератора. Он также сортируется «на лету» (при условии, что вы хотите отсортировать каждый внутренний список на score). Вместо того, чтобы хранить в словаре, вы можете легко записать каждый внутренний список в файл, что поможет с памятью.