Эффективное интервальное хранение с использованием стандартной библиотеки C++
Я работаю над проблемой, где каждая пара представляет собой закрытый интервал, и мне нужна структура данных для хранения коллекции этих пар. Эта структура данных должна поддерживать две операции: вставку(пара) и удаление(idx). Операция вставки должна проверить, не перекрывается ли вставляемый интервал с какими-либо существующими интервалами в коллекции; если есть перекрытие, вставка должна завершиться неудачно и вернуть -1. Операция удаления должна удалить самую большую пару idx в коллекции.
Моя цель — реализовать это, используя только стандартную библиотеку C++, сохраняя при этом минимальный код. Кроме того, крайне важно, чтобы временная сложность методов вставки и удаления была меньше O(log n).
Я был бы очень признателен за любые ваши предложения или идеи о том, как добиться этого эффективно, без необходимости кодирования. Большое спасибо за вашу помощь! Пока что единственное решение, которое я придумал, — это использование дерева B+, но для этого требуется немного больше кода.
class CustomDataStructure {
// some underlying private data structures
public:
bool insert(pair<int ,int> interval);
bool delete(unsigned int idx);
}
Спасибо за указание на проблему, прошу прощения за путаницу. Я пересмотрел вопрос!
это все еще немного расплывчато. иногда вы можете добиться прогресса, показав свой код и спросив об одной конкретной детали. Если вам повезет, это поможет вам увидеть более широкую картину. А если нет, то вы решили хотя бы еще одну деталь и можете переходить к следующей.
до сих пор неясно, что вы имеете в виду под «но для этого требуется немного больше кода» или почему это проблема. Чтобы что-то сделать в программировании, вам нужен код.
@trincot Это часть онлайн-конкурса по программированию, завершившегося несколько дней назад, и я пока не нашел простого решения. просто нужно, чтобы алгоритм был максимально простым
Вы можете просмотреть все доступные stl-контейнеры в Интернете, выбрать тот, который больше всего соответствует вашим потребностям, а затем обернуть его своими ограничениями. Из-за требований к массиву O(log n) контейнеры выходят из игры, и если удаление происходит довольно часто, его следует отсортировать.
Хотите ли вы, чтобы исходный код был минимальным, или вы хотите, чтобы скомпилированный код был минимальным. (вы можете использовать std::vector и немного переместить интервалы, чтобы сохранить их отсортированными, это не так уж и много кода, но, возможно, недостаточно производительно?)
Что вы подразумеваете под «idx-й по величине парой»?
@Pepijn Kramer спасибо за ваш комментарий! Мне просто нужно, чтобы исходный код был минимальным
Примечание: НЕ используйте std::pair для представления интервала, просто добавьте новую структуру с двумя членами. std::pair следует использовать в программировании шаблонов, где пара не имеет семантического значения (пока).
@kiner_shah спасибо за ваш комментарий! Поскольку ни один из интервалов не перекрывается, «idx-я по величине пара» относится к положению интервала на числовой прямой.
@ b39b332d b39b332d И почему, по вашему мнению, важен минимальный исходный код? Вы по-прежнему можете создать собственную структуру данных и затем использовать ее в конечном коде.
Лучше привести пример для «idx-й по величине пары».
@Pepijn Kramer спасибо за ответ! потому что единственный источник, который я могу включить, - это stl и некоторая стандартная библиотека C++ 11, такая как <algorithm> и <math> и т. д.
@kiner_shah спасибо за ответ! Я постараюсь включить диаграмму в конце вопроса.
«Мне просто нужно, чтобы исходный код был минимальным»: укажите показатель для этого. Что такое минимальное? Самый короткий код? Это оффтоп. Тогда насколько короткий? У вас есть ограничение на количество символов?
@trincot Извините за путаницу, это сложно описать. Во-первых, для этого потребуется меньше кода, чем для реализации дерева B+, и кроме того, чем меньше кода, тем лучше.
То есть вы имеете в виду AVL, красно-черный, пропуск и т. д.? Вы пробовали?
Позвольте мне спросить по-другому: насколько велика была ваша реализация B+дерева (#lines) и какой максимум для вас приемлем? Вы уверены, что вашу реализацию B+ нельзя написать с меньшим количеством кода?
Не могли бы вы сохранить интервалы в виде упорядоченного набора целых чисел, в котором целых чисел в два раза больше, чем интервалов? Четные индексированные целые числа начинаются, а нечетные индексированные целые числа являются концами интервалов. Тогда удаление i-го интервала будет означать удаление из набора как 2i, так и 2i+1-го элементов?
Ответы 4
На практике:
- Используйте отсортированный вектор и убедитесь, что isert сохраняет его отсортированным.
- сортировать по началу интервала
- Вставка использует
std::lower_bound, сравнивая начало интервала, чтобы найти позицию вставки (O log N). - Проверьте совпадение найденного элемента и последующего. (О 1)
Вставьте в заданную позицию, если нет конфликта (O(1) для списка, O(N) для вектора, но во многих практических ситуациях последний все же может быть быстрее.)
Теоретически: вместо этого используйте std::map. Удовлетворяет Big-O, но для этого размера элемента он, вероятно, будет медленнее, когда Big-O начнет иметь значение.
Вы можете «удешевить» удаление, пометив интервалы как «неиспользуемые»; например, сделав их эквивалентными длине 0. Это означает, что вставка должна проверять не только непосредственного преемника, но она все еще находится где-то в районе амортизированного O (1), за исключением рабочих нагрузок в худшем случае.
вставка в середину вектора, массива или дека равна O(N). Вы не можете выполнять двоичный поиск по списку или вперед_списку.
Спасибо за ваше предложение! однако метод удаления вектора и списка имеет временную сложность O (N)
@ b39b332d, конечно, правильно (я не знаю, почему я прочитал O(N log N) в вашем запросе, это не имеет смысла, но это прижилось)
В std нет контейнера, который мог бы удовлетворить ваши требования.
Ни один из контейнеров последовательностей не может вставляться в произвольные позиции менее чем за O(size()). vector, deque и inplace_vector имеют O(размер) insert. list и forward_list имеют поиск O(размер).
Ни один из ассоциативных или неупорядоченных ассоциативных контейнеров не может найти i-й индекс менее чем за O(i). std::advance и др. являются O(i), если только итератор не удовлетворяет RandomAccessIterator, что не относится к этим контейнерам.
Ни один из адаптеров контейнера не помогает, поскольку они по-прежнему имеют характеристики вставки базового контейнера.
Вам потребуется реализовать собственный контейнер, чтобы удовлетворить ваши требования к сложности. Что-то вроде Индексируемого списка пропуска подойдёт.
Вы когда-нибудь рассматривали стандартные ассоциативные классы как семью?
@Red.Wave да, см. пункт 3
Это частично похоже на ответ Петерхена:
Лучшее, о чем я могу думать, это
std::setдля реализации двоичного поиска- с настраиваемой функцией сравнения «меньше» с
left.second < right.first
Пользовательское сравнение рассматривает все пары с одинаковыми или перекрывающимися диапазонами как равные. «А» не меньше, чем «Б», и «Б» меньше, чем «А», означает, что «А» и «В» одинаковы.
Тогда вам нужно только проверить результат std::set::insert, чтобы узнать, существует ли диапазон.
Для удаления вы можете использовать std::set::reverse_iterator и цикл for. Это делает удаление O(N), но N зависит только от индекса, а не от размера std::set (если только индекс не зависит от размера std::set).
Давайте изучим теорию отношений баз данных.
Используйте std::vector для хранения данных. Это будет основной стол.
Используйте std::map<key, vector-index> в качестве индексной таблицы.
Вы ищете векторный индекс с помощью индексной таблицы, а затем используете векторный индекс для прямого доступа к данным.
«но для этого требуется слишком много кода».: у вас есть ограничение на размер кода? Почему? И что это такое?