Огромная структура графика

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

Я сомневаюсь, что вы сможете использовать структуру памяти, если в вашем распоряжении ОЧЕНЬ много памяти:

Предположим, вы говорите о 600 направленные ребра от каждого узла, причем узел имеет 4 байта (целочисленный ключ), а направленное ребро является ТОЛЬКО ключами узла назначения (по 4 байта каждый).

Тогда необработанные данные о каждом узле составляют 4 + 600 * 4 = 2404 байта x 6 000 000 = более 14,4 ГБ

Это без каких-либо дополнительных служебных данных или каких-либо дополнительных данных в узлах (или ребрах).

1. Если это 100-600 ребер на узел, то вы говорите о 3,6 миллиардах ребер.
2. Почему все это должно быть в памяти?
3. Можете ли вы показать нам структуры, которые вы используете в настоящее время?
4. Сколько памяти нам разрешено (какой предел памяти вы используете?)

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

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

• Neo4j - утверждает, что легко обрабатывает миллиарды узлов и давно находится в разработке.
• FlockDB - недавно выпущенная Twitter, это база данных с распределенными графами.

С тех пор, как вы начали использовать Python, смотрели ли вы на Networkx ? Насколько далеко вы продвинулись при загрузке графика такого размера, если посмотрели на него из интереса?

Предполагая, что вы имеете в виду 600 на узел, вы можете попробовать что-то вроде этого:

import os.path
import cPickle
class LazyGraph:
    def __init__(self,folder):
        self.folder = folder

    def get_node(self,id):
        f = open(os.path.join(self.folder,str(id)),'rb')
        node = cPickle.load(f)
        f.close() # just being paranoid
        return node

    def set_node(self,id,node):
        f = open(os.path.join(self.folder,str(id)),'wb')
        cPickle.dump(node,f,-1) # use highest protocol
        f.close() # just being paranoid

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

Обратите внимание, это будет очень-очень медленно.

Вы можете использовать потоки для предварительной выборки узлов (при условии, что вы знаете, в каком порядке вы их обрабатываете), но это будет неинтересно.

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

Края могут быть сохранены с помощью списка adjacency на узлах.

Конечно, это применимо только в том случае, если вы действительно имеете в виду 100-600 узлов в общей сложности. Если вы имеете в виду на узел, это совершенно другая история.

Если вы все же решите использовать какую-то базу данных, я предлагаю взглянуть на neo4j и его привязки к Python. . Это база данных графов, способная обрабатывать большие графы. Вот презентация с PyCon этого года.