Быстрая реализация корзины

Question

В графовом классе мне нужно обрабатывать узлы с целочисленными значениями (в основном 1-1000). На каждом этапе я хочу удалить узел и всех его соседей из графа. Также я хочу всегда начинать с узла минимального значения. Я долго думал о том, как сделать это как можно быстрее, и решил сделать следующее:

• График хранится с использованием списков смежности
• Существует огромный массив std::vector<Node*> bucket[1000] для хранения узлов по его значению
• Индекс самого нижнего непустого сегмента всегда сохраняется и отслеживается
• Я могу очень быстро найти узел минимального значения, выбрав случайный элемент этого индекса или, если корзина уже пуста, увеличить индекс
• Удаление выбранного узла из сегмента может быть явно сделано в O (1), проблема в том, что для удаления соседей мне нужно сначала выполнить поиск в сегменте сегмента [значение соседа] для всех соседних узлов, что не очень быстро ,

Есть ли более эффективный подход к этому?

Я подумал об использовании чего-то вроде std::list<Node*> bucket[1000] и назначить каждому узлу указатель на его «элемент списка», чтобы я мог удалить узел из списка в O (1). Возможно ли это с помощью списков stl, ясно, что это можно сделать с помощью обычного двойного связанного списка, который я мог бы реализовать вручную?

Answer 1

Вот что я бы сделал. Структура узла:

struct Node {
    std::vector<Node*>::const_iterator first_neighbor;
    std::vector<Node*>::const_iterator last_neighbor;
    int value;
    bool deleted;
};

Объединить списки смежности и поместить их в один std::vector<Node*>, чтобы снизить накладные расходы на управление памятью. Я использую мягкие удаления, поэтому скорость обновления не важна.

Сортировка указателей на узлы по значению в другой std::vector<Node*> с сортировкой . Отметить все узлы как не удаленные.

Итерация по узлам в отсортированном порядке. Если рассматриваемый узел был удален, переходите к следующему. В противном случае пометьте его как удаленный, выполните итерацию по соседям и пометьте его как удаленный.

Если ваши узлы хранятся в памяти непрерывно, то вы можете опустить last_neighbor за счет дополнительного дозорного узла в конце структуры, поскольку last_neighbor узла - это first_neighbor последующего узла.

Answer 2

Недавно я сделал нечто подобное для реализации очереди с приоритетами с использованием сегментов.

Я использовал хеш-таблицы (unordered_map), поэтому вам не нужно хранить 1000 пустых векторов, и вы по-прежнему получаете O (1) произвольный доступ (общий случай, не гарантируется).Теперь, если вам нужно только один раз сохранить / создать этот графовый класс, это, вероятно, не имеет значения.В моем случае мне нужно было создавать приоритетную очередь десятки / сотни раз в секунду, и использование хэш-карты имело огромное значение (из-за того, что я создал unordered_sets только тогда, когда у меня действительно был элемент с таким приоритетом, поэтому нет необходимостиинициализировать 1000 пустых хеш-наборов).Хэш-наборы и карты являются новыми в C ++ 11, но уже некоторое время доступны в std :: tr1, или вы можете использовать библиотеки Boost.

Единственное отличие, которое я вижу между вашими &Мой пример использования заключается в том, что вы также должны иметь возможность удалять соседние узлы.Я предполагаю, что каждый узел содержит список указателей на его соседей.Если это так, удаление соседей должно занять k * O(1) с k количеством соседей (опять же, O (1) в общем случае, не гарантировано, наихудший случай - O (n) в unordered_map / set).Вы просто просматриваете каждый соседний узел, получаете его приоритет, что дает вам правильный индекс в хэш-карте.Затем вы найдете указатель в хэш-наборе, которому соответствует приоритет, этот поиск в общем случае будет O (1), а удаление элемента снова будет O (1) в общем.

В целом, я думаюу вас есть довольно хорошее представление о том, что делать, но я считаю, что использование хеш-карт / наборов значительно ускорит ваш код (конечно, зависит от точного использования).Для меня улучшение скорости реализации с unordered_map<int, unordered_set> против vector<set> составило около 50х.