Какая структура данных графа наиболее эффективна в Python? [закрыто]

Мне нужно иметь возможность манипулировать большим (10 ^ 7 узлов) графом в python. Данные, соответствующие каждому узлу /ребру, минимальны, скажем, небольшое количество строк. Каков наиболее эффективный способ сделать это память и скорость ?

Диктовка диктов является более гибкой и простой в реализации, но я интуитивно ожидаю, что список списков будет быстрее. Опция list также потребует, чтобы я держал данные отдельно от структуры, в то время как dicts допускает что-то в этом роде:

graph[I][J]["Property"]="value"

Что бы вы предложили?


Да, мне следовало бы прояснить, что я имею в виду под эффективностью. В данном конкретном случае я имею в виду поиск с произвольным доступом.

Загрузка данных в память не является большой проблемой. Это сделано раз и навсегда. Часть времени занимает посещение узлов, поэтому я могу извлечь информацию и измерить интересующие меня метрики.

Я не думал о том, чтобы сделать каждый узел классом (свойства одинаковы для всех узлов), но кажется, что это добавило бы дополнительный уровень издержек? Я надеялся, что у кого-то будет прямой опыт с подобным случаем, которым они могли бы поделиться. В конце концов, графы являются одной из самых распространенных абстракций в CS.

64 голоса | спросил bgoncalves 4 PM00000040000005731 2008, 16:00:57

7 ответов


0

Я бы настоятельно рекомендовал вам взглянуть на NetworkX . Это боевой конь, испытанный в бою, и первый инструмент, доступный большинству «исследовательских» типов для анализа сетевых данных. Я без проблем манипулировал графиками с сотнями тысяч ребер на ноутбуке. Его функция богата и очень проста в использовании. Вы обнаружите, что больше внимания уделяете проблеме, а не деталям базовой реализации.

Пример Erdős-Rényi генерация и анализ случайных графов


"""
Create an G{n,m} random graph with n nodes and m edges
and report some properties.

This graph is sometimes called the Erd##[m~Qs-Rényi graph
but is different from G{n,p} or binomial_graph which is also
sometimes called the Erd##[m~Qs-Rényi graph.
"""
__author__ = """Aric Hagberg ([email protected])"""
__credits__ = """"""
#    Copyright (C) 2004-2006 by 
#    Aric Hagberg 
#    Dan Schult 
#    Pieter Swart 
#    Distributed under the terms of the GNU Lesser General Public License
#    http://www.gnu.org/copyleft/lesser.html

from networkx import *
import sys

n=10 # 10 nodes
m=20 # 20 edges

G=gnm_random_graph(n,m)

# some properties
print "node degree clustering"
for v in nodes(G):
    print v,degree(G,v),clustering(G,v)

# print the adjacency list to terminal 
write_adjlist(G,sys.stdout)

Визуализации также просты:

введите описание изображения здесь

Дополнительная визуализация: http://jonschull.blogspot.com/2008/08 /graph-visualization.html

ответил Ryan Cox 26 PM00000090000000631 2008, 21:43:06
0

Несмотря на то, что этот вопрос сейчас довольно старый, я думаю, что стоит упомянуть мой собственный модуль python для работы с графами, который называется граф-инструмент . Это очень эффективно, поскольку структуры данных и алгоритмы реализованы на C ++ с метапрограммированием шаблонов с использованием библиотеки графов ускорения. Поэтому его производительность (как в использовании памяти, так и во время выполнения) сравнима с чистой библиотекой C ++ и может быть на несколько порядков лучше, чем в обычном коде Python, без ущерба для простоты использования. Я сам использую его для работы с очень большими графиками.

ответил Tiago Peixoto 27 62010vEurope/Moscow11bEurope/MoscowSat, 27 Nov 2010 17:10:33 +0300 2010, 17:10:33
0

Как уже упоминалось, NetworkX очень хорош, а другой вариант - igraph . Оба модуля будут иметь большинство (если не все) инструменты анализа, которые вам могут понадобиться, и обе библиотеки обычно используются в больших сетях.

ответил Kai 27 PM00000020000002131 2008, 14:01:21
0

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

Судя по вашему примеру, «Недвижимость», вам лучше классный подход к финальному уровню и реальным свойствам? Или имена свойств сильно меняются от узла к узлу?

Я бы сказал, что то, что означает «эффективный», зависит от многих вещей, например:

  • скорость обновления (вставка, обновление, удаление)
  • скорость поиска в произвольном доступе
  • скорость последовательного поиска
  • используемая память

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

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

В общем, я бы предложил использовать метод, который кажется вам наиболее естественным, а затем провести «стресс-тест» системы, добавив к ней значительный объем данных и посмотреть, станет ли он проблема.

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

ответил Lasse Vågsæther Karlsen 4 PM00000040000005531 2008, 16:09:55
0

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

Однако, с точки зрения производительности, загрузка его в память может не быть проблемой, но если вы будете использовать слишком много, вы в конечном итоге перейдете на диск, что снизит производительность даже высокоэффективных кодов Python. Постарайтесь максимально сократить использование памяти. Кроме того, оперативная память сейчас удивительно дешева; если вы много делаете такого рода вещи, нет причин не иметь по крайней мере 4 ГБ.

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

ответил Peter Burns 6 AM00000090000003331 2008, 09:37:33
0

Создание структуры на основе классов, вероятно, будет иметь больше накладных расходов, чем структура на основе dict, поскольку в классах python фактически используются dicts, когда они реализованы.

ответил Matthew Schinckel 4 PM00000040000001531 2008, 16:41:15
0

Без сомнения, NetworkX - лучшая структура данных для графа до сих пор. Он поставляется с такими утилитами, как вспомогательные функции, структуры данных и алгоритмы, генераторы случайных последовательностей, декораторы, упорядочивание Кутхилла-Макки, контекстные менеджеры

NetworkX великолепен, потому что он хорош для графиков, орграфов и мультиграфов. Он может написать график несколькими способами: Список смежности, Многострочный список смежности, Edge List, GEXF, GML. Работает с Pickle, GraphML, JSON, SparseGraph6 и т. Д.

В нем реализованы различные радиопрограммы, в том числе: Аппроксимация, Двухсторонний, Граница, Центральность, Клика, Кластеризация, Раскраска, Компоненты, Связь, Циклы, Направленные ациклические графы Измерения расстояний, доминирующие множества, эйлерово уравнение, изоморфизм, анализ связей, предсказание связей, сопоставление, минимальное остовное дерево, богатый клуб, кратчайшие пути, обход, дерево.

ответил Pranav Waila 18 Jpm1000000pmMon, 18 Jan 2016 12:08:03 +030016 2016, 12:08:03

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132