Эффективное отображение диапазонов на группы значений
Я пытаюсь определить подходящий способ сделать следующее.
Я хотел бы иметь диапазон -> установить поиск в пределах определенного диапазона (скажем, [0x0 — 0xffffffff]).
Значения вставляются в диапазон в диапазонах (поэтому, если мы работаем с T = уникальными строками), я мог бы вставить («beef3490», [0x1234, 0xFFFF]); и один идентификатор может иметь несколько вставок, которые могут или не могут перекрываться. Кроме того, могут быть вставлены другие значения, которые перекрываются и где они перекрываются. В результате я должен получить набор уникальных строк.
Наконец, значения также могут быть удалены из диапазонов (не обязательно совпадающих, но обычно содержащихся в их начальном диапазоне вставки).
Вот упрощенный пример использования:
insert("beef3490", [0x1234, 0xFFFF])
insert("beef3490", [0x11111, 0x22222])
insert("flam1456", [0x8000, 0xA0000])
remove("beef3490", [0x21000, 0x22000])
lookup(0x0) -> set<>
lookup(0x2000) -> set<beef3490>
lookup(0x9456) -> set<beef3490, flam1456>
lookup(0x21212) -> set<flam1456>
lookup(0x99789) -> set<flam1456>
Это приводит к ряду вопросов для меня:
Есть ли обобщенное название для такого рода проблемы или проблемы подобного типа, из которой я мог бы понять?
Что является идеальной реализацией с учетом следующих ограничений:
- Быстрое / очень быстрое время поиска
- Использование памяти не увеличивается (т. Е. Следующие операции имеют одинаковую площадь)
- Вставить [10,20], Вставить [20,30], Удалить [14,24]
- Вставить [10,15], Вставить [25,30]
- Как и в прошлом, структура данных должна иметь стабильность в долго работающей системе
- Время вставки / удаления не является абсолютно ужасным (они не должны быть такими же быстрыми, как поиск)
Учитывая идеальную реализацию, у вас есть совет для использования в C ++
Спасибо за все ответы и помощь.
Решение
Есть ли обобщенное название для такого рода проблемы или проблемы подобного типа, из которой я мог бы понять?
Эта проблема является проблемой дерева интервалов или дерева сегментов.
В частности, дерево / структура данных должна выполнять совокупность в перекрытии операции.
Это означает, что когда в структуру вставляются два пересекающихся диапазона, значение поиска для точки в обоих диапазонах эквивалентно val (диапазон A) + val (диапазон B). Операция «+» может быть добавлением, если значения являются целыми числами, или в случае множеств это будет операция объединения.
Что такое идеальная реализация с учетом ограничений
Самобалансирующееся дерево двоичного поиска (например, красно-черное дерево или дерево козла отпущения), созданное для оптимизации поиска на основе диапазонов. Операции вставки дополнительно пересекают диапазоны по мере необходимости для получения правильных возвращаемых значений. Способы разделения диапазонов варьируются в зависимости от ваших требований, но обычно это либо «объединение», которое отбрасывает информацию об исходных диапазонах, но имеет меньшую занимаемую площадь, либо «разделение», из которого все еще можно вывести исходные диапазоны.
Учитывая идеальную реализацию, у вас есть совет для использования в C ++
Увидеть повышение :: ICL. (Увеличить интервальную библиотеку контейнеров)
Другие решения
Других решений пока нет …