Нужно было написать программу, работающую с большими и при этом достаточно разреженными (~млн вершин и ~10млн ребер, например) графами, поэтому возникла необходимость серьезно оптимизировать код как по памяти, так и по времени.
Реализуется моделирование бассейнов, интерфейс поддерживает функционал: добавить воду, получить информацию об объеме воды в бассейне, соединить два бассейна трубой. Работа над кодом иногда возобновляется, возможно, периодически будут выходить обновления
Основную вопрос состоит в реализации структуры данных для хранения бассейнов. В программе бассейны интерпретируются как вершины графа, а трубы - как соединяющие их ребра. Понятно, что хранить матрицу смежности не получится, поскольку уже для 100тыс бассейнов размер матрицы составлял бы 10Гб. Поэтому проводится модификация матрицы смежности - каждый бассейн хранит собственный индекс и индексы присоединенных бассейнов. Поскольку граф разреженный, такой способ хранения кажется наиболее эффективным.
В первую очередь, стоит упомянуть, что код написан без использования STL. Основная сложность состоит в том, что в наивной реализации нужно обходить компоненту связности бассейна при каждом добавлении воды или трубы. Таким образом, время работы O(NM), где N - число бассейнов, M - число операций добавления. Это самое слабое место наивной реализации, нуждающееся в ускорении. Идея состоит в том, что перераспределение воды по компонентам связности имеет смысл только когда нужно вывести данные об объеме воды в бассейнах. Поэтому для графа реализован приватный метод _merge(), осуществляющий быстрое перераспределение воды.
Число бассейнов; число труб; число добавлений воды: время работы 1k; 14k; 35k: 0.050s 10k; 140k; 350k: 0.476s 100k; 1.4kk; 3.5kk: 5.526s numberOfPools ~ 150k: segfault (превышение глубины рекурсии)