Какова наиболее эффективная структура данных графа в Python? [закрытый]
Мне нужно уметь манипулировать большим (10^7 узлов) графом в python. Данные, соответствующие каждому узлу / краю, минимальны, скажем, небольшое количество строк. Что является наиболее эффективным, с точки зрения память и скорость, как это сделать?
дикт диктов является более гибким и простым в реализации, но я интуитивно ожидаю, что список списков будет быстрее. Опция списка также потребует, чтобы я хранил данные отдельно от структуры, в то время как диктанты допускали бы что-то вроде:
graph[I][J]["Property"]="value"
что бы вы предложили?
Да, я должен был быть немного яснее, что я имею в виду под эффективностью. В данном конкретном случае я имею в виду его с точки зрения поиска произвольного доступа.
загрузка данных в память не является огромной проблемой. Это делается раз и навсегда. Трудоемкая часть посещает узлы, поэтому я могу извлечь информацию и измерить интересующие меня показатели в.
Я не рассматривал возможность сделать каждый узел классом (свойства одинаковы для всех узлов), но похоже, что это добавит дополнительный уровень накладных расходов? Я надеялся, что у кого-то будет какой-то прямой опыт с подобным случаем, который они могли бы поделиться. В конце концов, графики являются одной из самых распространенных абстракций в CS.
7 ответов:
Я бы настоятельно рекомендовал вам посмотреть на NetworkX. Это испытанный в бою Боевой конь и первый инструмент, который большинство типов "исследований" достигают, когда им нужно сделать анализ сетевых данных. Я без проблем манипулировал графиками с 100 тысячами ребер на ноутбуке. Его особенность богата и очень проста в использовании. Вы обнаружите, что больше фокусируетесь на текущей проблеме, а не на деталях в базовой реализации.
пример 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 (hagberg@lanl.gov)""" __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
хотя этот вопрос теперь довольно старый, я думаю, что стоит упомянуть мой собственный модуль python для манипуляций с графами под названием graph-tool. Это очень эффективно, так как структуры данных и алгоритмы реализованы в C++, с шаблонным метапрограммированием, с использованием библиотеки графов Boost. Поэтому его производительность (как в использовании памяти, так и во время выполнения) сопоставима с чистой библиотекой C++ и может быть на порядок лучше, чем типичный код python, без ущерба для простота использования. Я сам постоянно использую его для работы с очень большими графиками.
Как уже упоминалось, NetworkX очень хорош, с другим вариантомigraph. Оба модуля будут иметь большинство (если не все) инструментов анализа, которые вам, вероятно, понадобятся, и обе библиотеки обычно используются с большими сетями.
словарь может также содержать накладные расходы, в зависимости от фактической реализации. Хэш-таблица обычно содержит некоторое простое число доступных узлов для начала, хотя вы можете использовать только несколько узлов.
судя по вашему примеру, "свойство", было бы лучше с классовым подходом для конечного уровня и реальных свойств? Или имена свойств сильно меняются от узла к узлу?
Я бы сказал, что то, что означает "эффективный", зависит от a много чего, например:
- скорость обновления (вставка, обновление, удаление)
- скорость поиска произвольного доступа
- скорость последовательного поиска
- память используется
Я думаю, что вы обнаружите, что структура данных, которая является быстрой, обычно потребляет больше памяти, чем медленная. Это не всегда так, но большинство структур данных, похоже, следуют этому.
словарь может быть простым в использовании, и дать вам относительно равномерно быстрый доступ, он, скорее всего, будет использовать больше памяти, чем, как вы предлагаете, списки. Списки, однако, как правило, содержат больше накладных расходов при вставке данных в него, если они предварительно не выделяют узлы X, в которых они снова будут использовать больше памяти.
мое предложение, в общем, было бы просто использовать метод, который кажется вам наиболее естественным, а затем сделать "стресс-тест" системы, добавив к нему значительное количество данных и посмотреть, станет ли он проблема.
вы также можете рассмотреть возможность добавления уровня абстракции в вашу систему, так что вам не придется менять интерфейс программирования, если вам позже понадобится изменить внутреннюю структуру данных.
насколько я понимаю, произвольный доступ находится в постоянном времени как для диктовок, так и для списков Python, разница в том, что вы можете делать только произвольный доступ к целочисленным индексам со списками. Я предполагаю, что вам нужно искать узел по его метке, поэтому вам нужен дикт диктов.
однако на фронте производительности загрузка его в память может не быть проблемой, но если вы используете слишком много, вы в конечном итоге замените диск, что убьет производительность даже высокоэффективных диктовок Python. Старайтесь как можно меньше использовать память. Кроме того, ОЗУ удивительно дешево прямо сейчас; если вы делаете такие вещи много, нет причин не иметь по крайней мере 4 ГБ.
Если вы хотите получить совет по снижению использования памяти, дайте дополнительную информацию о том, какую информацию вы отслеживаете для каждого узла.
создание структуры на основе классов, вероятно, будет иметь больше накладных расходов, чем структура на основе dict, поскольку в классах python фактически используются dicts при их реализации.
без сомнения NetworkX является лучшей структурой данных до сих пор для графика. Он поставляется с такими утилитами, как вспомогательные функции, структуры данных и алгоритмы, генераторы случайных последовательностей, декораторы, заказ Cuthill-Mckee, контекстные менеджеры
NetworkX отлично подходит, потому что он wowrs для графиков, орграфов и мультиграфов. Он может писать график несколькими способами: список смежности, многострочный список смежности, Список краев, GEXF, GML. Он работает с рассолом, GraphML, JSON, SparseGraph6 и т. д.
Он имеет реализация различных алгоритмов radimade в том числе: Аппроксимация, Двудольная, Граничная, Центральная, Клика, Кластеризация, Окраска, Компоненты, Связность, Циклы, Направленные Ациклические Графы, Меры Расстояния, Доминирующие Множества, Эйлеровы, Изоморфизм, Анализ Связей, Предсказание Связей, Сопоставление, Минимальное Связующее Дерево, Богатый Клуб, Кратчайший Путь, Обход, Дерево.