Как эффективно хранить эквивалентности (из алгоритма маркировки связанных компонентов)?

Question

Я хотел бы сохранить эквиваленты из Алгоритм маркировки подключенных компонентов .Это в основном создание вида карты от одного значения (идентификатора одной метки) до нескольких значений (идентификаторы от меток, которые эквивалентны предыдущему.)

Я уже сделал что-то подобное, но это не очень хорошо работает:

std::map<unsigned short, std::list<unsigned int>> equivalences;
for(int i = 0; i < MAX_NUMBER_OF_LABELS; ++i )
{
    std::list<unsigned int> temp;
    temp.push_back(i);
    // note that a label is equivalent to itself
    equivalences.insert( std::pair< int, std::list<unsigned int>>(i, temp) );
}

Затем я добавляю правильную эквивалентность следующим образом:

equivalences.at( i ).push_back( equivalent_labels_int );

Основным недостатком этого метода является то, что я должен заранее объявить размер map (он долженбыть достаточно большим), а затем для больших размеров (например, 9999) время инициализации составляет приблизительно 2,5 с.

У кого-нибудь есть идея получше?

Answer 1

Вам не нужно заранее определять размер map в C ++ (или в большинстве языков).map s могут динамически расти, добавляя в них новые элементы, поэтому, если вы найдете новый ключ, вы всегда можете добавить его на карту.Например:

equivalences[i].push_back(equivalent_labels_int);

Это работает, потому что оператор квадратных скобок * map (operator[]) автоматически добавит новую пару ключ / значение в map с указанным ключом и значением по умолчанию.значение, если оно еще не существует.

Кроме того, я бы посоветовал не использовать list в качестве контейнера для хранения последовательности связанных BLOB-объектов.list хорошо, когда вам не нужен произвольный доступ, и вы часто удаляете элементы в середине последовательности, что, я думаю, вы на самом деле здесь не делаете.Вместо этого я бы предложил использовать vector или deque, поскольку эти структуры более компактны и имеют лучшую локальность.

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

Надеюсь, это поможет!

Answer 2

Я думаю, что Несвязанные множественные леса - это то, что вы ищете.Вот лучшее описание этой структуры данных: