Самая эффективная реализация списка смежности?

Question

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

Какая реализация лучше всего подходит для этого сценария?

Список списков или, может быть, карта? Мне также нужно где-то спасти веса. Я не мог понять, как это сделать, поскольку сам список смежности, по-видимому, просто отслеживает связанные узлы, но не вес края.

Answer 1

Одно решение, которое вы можете создать, создает класс Node, который содержит данные и вес. этот вес будет весом края, через который он соединен с узлом.

Предположим, у вас есть список для узла I, которая соединена с узлом A B C с ребром веса а б с. И Node J подключен к ABC с А веса, так что список прил из я буду содержит объект Node в

I -> <A, a>,<B b>,<C c> 

Списка J воля содержит объект Node как

J -> <A, x>,<B y>,<C z> 

Answer 2

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

Списки аджакции - один из самых неудобных классов структур данных для оптимизации, главным образом потому, что они различаются по размеру от одной вершины к следующей. На каком-то широком концептуальном уровне, если вы включаете данные смежности как часть определения Vertex или Node, то это делает размер переменной Vertex/Node . Данные с переменным размером и вид соприкосновения с памятью, необходимые для удобства кэширования, как правило, сражаются друг с другом на большинстве языков программирования.

Большинство объектно-ориентированных языков не предназначалось для работы с объектами, которые могут фактически различаться по размеру. Они решают это, заставляя их указывать на/ссылаться на память в другом месте, но это приводит к гораздо более высоким промахам в кэше.

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

Так оно перестает стать вопрос о том, какие структурыданных, чтобы использовать так много, как то, что макеты памяти использовать. Массивы - ваш друг здесь, но не массивы узлов. Вы хотите, чтобы массив из байтов упаковывал данные узла в соприкосновение.Что-то вроде этого:

[node1_data num_adj adj1 adj2 adj3 (possibly some padding for alignment and to avoid straddling) node2_data num_adj adj1 adj2 adj3 ...]

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

Теперь это только в том случае, если вы хотите получить самое быстрое решение, и при условии, что ваши варианты использования сильно взвешены в направлении операций чтения (оценка, обход), а не записи (связывание краев, вставка узлов, удаление узлов). Это в полной мере избыточно, и полная PITA, так как вы потеряете всю эту красивую объектно-ориентированную структуру, которая поможет сохранить код в удобном для использования, повторном использовании и т. Д. Это позволит вам уничтожить всю эту структуру в пользу работы с вещами на битах и уровень байтов, и это стоит делать только в том случае, если ваше программное обеспечение находится в сфере, где его качество как-то очень пропорционально эффективности этого графика.