алгоритм сохранения связей

DSU, adjacency list? Какая инфа тебе в итоге нужна? Соеденины ли ноды, или надо пути искать?

На первый взгляд у тебя два варианта:
- Хранить связи ноды внутри нее самой (std::set/std::unordered_set)
- Хранить все связи вообще в отдельном словаре (std::map/std::unordered_map)

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

Разреженная матрица связности.

На жава:

class Node { 
 Set<Node> nodeSet; или 
 List<Node> nodeList;
}

boost::graph?

Тут чего-то не хватает. Если просто нужно хранить, то вполне достаточно таплов связей (A, B), дублирования не будет. Если нужно не только хранить, но ещё и совершать какие-то переходы по связям за недорого, то будет некое дублирование данных связей.

Есть-ли способ лучше/экономичнее?

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

ребята, тут не зря тег C++ присутствует.

Я бы замутил битовый масив связей для каждой ноды. Причем бы хранил эти массивы в отдельном объекте (как набор строк в матрице связей). Делаем расщет на 16000 нод. Получаем 16000 строк, каждая строка 2000 байт и того для матрицы связей нужно 30M RAM - в принципе не много, для 64000 нод нужно будет 488М. Связи леко удалять/добовлять/искать. Если при запуске создать матрицу на максимально расщетное к-во нод (N) то легко добовлять/удалять ноды тоже (нужно будет только создать пул индексов от 0 до N-1).

Но вообще наверное хранить список нод в каждой ноде и при добавлении/удалении ноды делать обход и модифецировать 30 списков возможно и более рационально (все зависит от того как часто это нужно делать, и есть ли многопоточность).

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

Разреженная матрица требует O(n) памяти для хранения n ненулевых элементов. Плюс по сравнению с наколенными решениями: для разреженных матриц есть годные либы.

Впрочем, т.к. ОП не назвал задачу, отвечать что-то серьёзно невозможно. Так что я просто сболтнул что-то для скора.

Разве она по памяти меньше чем список будет в среднем случае?

Так её внутреннее представление может быть и списком в т.ч. При совсем тупой реализации.

Допустим, мы индексируем ноды int32_t. Сложность по памяти списка смежности <Колво нод> + <Колво связей>, пусть каждая нода связанна с 30ю другими. Получается 16000 * 31 * 4 + 16000 * 8 = 1984000 (~2.0 Мб) ну или в 2раза больше если не использовать индекс а только указатели. Расти память будет линейно.

Мило, киньсо ссылкой на годную либу, хоть мну пользу принесёшь. Автор надеется на либастрал :)

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

Reset, расскажешь что-нибудь на эту тему? Спасибо.

Да ладно, это по большому счёту было праздное любопытсво, чего людей то тревожить :)

Я бы замутил битовый масив

спасибо, я думал об этом, но не хочется в 2015ом обмазываться битами... Ну и см. ниже, не взлетит.

Но вообще наверное хранить список нод в каждой ноде и при добавлении/удалении ноды делать обход и модифецировать 30 списков возможно и более рационально (все зависит от того как часто это нужно делать, и есть ли многопоточность).

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

Там должно быть много ищущих потоков, и немного (1 или вообще нет) вставляющих. А останавливать поиск на время вставки очень не хотелось бы.

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

Плюс судя по упоминанию 30 связей на ноду, там скорее сильно связанный граф выходит, или я чего то не догоняю?

ну да, сильно связанный граф. Что-то вроде дерева, но сеть, а не иерархия.

Разреженная матрица требует O(n) памяти для хранения n ненулевых элементов. Плюс по сравнению с наколенными решениями: для разреженных матриц есть годные либы.

это мне не подходит, т.к. общее число узлов не известно, ну и постоянно меняется. Причём узлы непосредственно не связанные с «новорожденными» и «умершими» не знают о факте рождения/смерти.

Впрочем, т.к. ОП не назвал задачу

одноранговая сеть узлов.

Ну тогда и не стоит замарачиваться, возьми обыкновенный RW мутекс и вектор (только не STL а лутчше свой) с быстрым удалением из середины (последний элемент переносим на место удаленного - и транкейтим вектор). Лоч мутекс отдельно для каждой ноды (при поиске на R, при изменении на W). Лок мутекса операция дорогая только если мутекс занят - в твоем случае я так понял модификации не сильно частые.

При данной организации списка (вектор с удалением в середине) - второй список нафиг не нужен поскольку операция удаления/вставки будет занимать столько-же времени как и переключение списков в двухсписочном варианте.

Кнута читай, там всё есть. (Том 4B).

второй список нафиг не нужен

второй список нужен для продолжения операций поиска во время операции вставки.

в твоем случае я так понял модификации не сильно частые.

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

ну я ещё подумаю над этим.

с быстрым удалением из середины (последний элемент переносим на место удаленного - и транкейтим вектор).

та просто список односвязный. Мне всё равно нужно все элементы просматривать. Потому быстрый доступ не нужен(т.е. достаточно O(n)).

да? Ладно, почитаю. У меня только три первых.

template <int n=1> struct Links {Node * link[n];};
std::unordered_multimap<Node*,size_t> map;
std::vector<Links<10>> links;
std::vector<size_t> unused_links;

добавление ссылки: берешь ноду, идёшь в multimap, получаешь там equal_range. ищешь в этом range индекс, по которому в векторе найдется структура с со, в котором есть свободное место и туда суешь указатель. если не нашел, берешь из unused_links либо создаешь новый элемент в векторе links.

удаление связи: берешь ноду, идёшь в multimap, получаешь там equal_range, ищешь в списке блоков тот где есть указатель на другую ноду и нулишь его. Если в ноде больше нет ненулевых указателей, удаляешь соотв итератор из map, и индекс заносишь в unused_links.

делать надо в обе стороны чтоб не было висячих ссылок(т.е. А->B и B->A)

еще можно links заменить на std::list, подпертый boost::pool_allocator, тогда unused_links не нужно, можно прям так deletить из этого списка, а в map хранить не size_t а std::list<Links<n>>::iterator

не учёл многопоточность. погоди, есть решение почти готовое.

вообще не фрагментирует память но с недостатком: читатели не сразу видят изменения а только после переключения буферов(как в видео)

второй список нужен для продолжения операций поиска во время операции вставки.

А в чем выигрыш при втором списке?, тебе хоть с 1 хоть с 2 списками нужен будет мутекс (в первом слечае для синхронизации модификации списка, во втором для синхронизации операции swap списков). А организация списка вектором удобна тем что операция вставки/удаления по времени будет индентична операции swap с двумя списками + не будет оверхеда по памяти (при линкованом списке каждый элемент это по сути отдельный объект в куче + у него оверхед по указателям на соседей). Вот смотрите:

// add
m.lock();
links[links_len++] = new_node_id;
m.unlock();
// remove
m.lock();
links[remove_idx] = links[--links_len];
m.unlock();
// swap 2 lists
m.lock();
tmpLinks = m_links;
m_links = new_links;
m.unlock();

да я сам сделаю реализацию, это для меня не проблема. Я про алгоритмы, а уж список я сам напишу.

А в чем выигрыш при втором списке?

ну потому-что вставляемая нода может полчаса вставляться. Потому лочить это не вариант.

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

потому мне не нравится две сущности на _одну_ связь: у меня есть связь А-Б, а мне нужно хранить указатель А→Б и указатель Б→А. Проблема не в памяти и не во времени обработке. Проблема в том, что мне их оба надо лочить. А лочить 30 соседних нод мне не хочется.