Эффективный способ чтения и записи графика Networkx - PullRequest
Новая
       47

Эффективный способ чтения и записи графика Networkx

0 голосов
/ 04 мая 2020

В проекте с открытым исходным кодом я пытаюсь использовать NetworkX, чтобы найти аттракторы Graph (называемые State Transition Graph). Дело в том, что для почти 2 ** 33 циклов функция с различными входами возвращает список кортежей (почти 5000 кортежей), в которых каждый кортеж содержит ребра, которые необходимо подать на график networkx. Это выглядит следующим образом: 

def BigGraph:
    #Do some computations
    G = nx.DiGraph()
    for i in range(2**33):
        #Do some computations
        edges = func(different initial conditions)
        G.add_edges_from(edges)

Как уже упоминалось ранее, поскольку число ребер растет быстрее, а также тот факт, что график NetworkX занимает много памяти в оперативной памяти, я пытался непрерывно читать и записывать в Файл маринада выглядит следующим образом: 

def BigGraph:
    #Do some computations
    G = nx.DiGraph()
    nx.write_gpickle(G, 'graph.gpickle')
    for i in range(2**33):
        #Do some computations
        edges = func(different initial conditions)
        G = nx.read_gpickle('graph.gpickle')
        G.add_edges_from(edges)
        nx.write_gpickle(G, 'graph.gpickle')

После этого я осознал, что при экспоненциальном ребре go чтение и запись в маринаде отразится на мне много времени и памяти. Я попробовал то, что было предложено здесь , но, как уже упоминалось в этом вопросе, мне не нужно часто работать с Graph. В конечном счете, все, что мне нужно сделать, это добавить МНОЖЕСТВО ребер в граф networkx со сложностью O (1), если это возможно.

Есть ли в любом случае, в котором я могу сделать это, чтобы сэкономить много времени, а также не будет проблемой для моей памяти (у меня 8 ГБ ОЗУ). Я открыт для использования любых внешних библиотек, если они бесплатны и могут эффективно выполнять то, что я намеревался сделать.

РЕДАКТИРОВАТЬ : я хотел знать, есть ли способ в котором мы можем использовать что-то вроде memmap, чтобы хранить мой график на моем жестком диске и находить привлекающие компоненты графика. Использование NetworkX является обязательным для меня.

1 Ответ

0 голосов
/ 04 мая 2020

У вас меньше оперативной памяти, чем вам нужно для этой проблемы. 2 ** 33 *5000* 2 = 85 899 345 920 000 и в зависимости от количества узлов / ребер, я не уверен, что это будет работать для вас. Но есть надежда. Это зависит от повторяющихся элементов, если их много, то ... здорово. В противном случае это может оказаться невозможным только на вашей машине (начните думать о AWS как о платформе, на которой можно решить эту проблему).

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

При первом проходе я получу пары кортежей с генератором, который отслеживает, какие из них он отправил (пример ниже). Поскольку вы используете орграф вместо мульти-орграфа, вы можете взять все ребра как кортежи и добавить их в set () в генераторе. Это даст только уникальные края. Если есть способ l oop по узлам, начинающимся со всех ребер, которые начинаются с Node1, тогда вы можете разделить задачу еще дальше, поместив все узлы в a для l oop и стирая set () при каждом новом узел. (Я не знаю, на что способен этот забавный c (различные начальные условия)) 

from pathlib import Path
def filter_edges():
    unique_edges = set()
    #Do some computations
    for i in range(2**33):
        #Do some computations
        edges = func(different initial conditions)
        for edge in edges:
            if edge not in unique_edges:
                 yield edge
                 unique_edges.add(edge)

def write_unique_values():
    for edge in filter_edges(): # it's easier on the machine to batch 10,000 or so rather than every line
        Path('edgelist.txt').write_text(edge)

def load_edgelist_to_graph():
    edges = Path('edgelist.txt').read_text().split('\n')
    G = nx.DiGraph()
    G.parse_edges(edges, ...)
    return G

write_unique_values()
G = load_edgelist_to_graph()

Сохраните полученное ребро из генератора в файл. Или, что еще лучше, делайте это партиями по 10000 или около того (я оставлю это домашней работе).

Тогда у вас будет файл с уникальными ребрами, который вы сможете загрузить в свой график.

Вы можете проанализировать края, используя parse_edges

...