Привет всем.

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

Например, словарь такой:

[ 5, 15] -> Царь
[35, 50] -> Медведь
[25, 40] -> Чурка

Подаем на вход [10, 30], получаем

[ 5, 15] -> Царь
[25, 40] -> Чурка

Производительность критична, хотелось бы чтоб она была сопоставима с таковой у SCG.Dictionary, то есть
почти всегда константа для поиска одиночного вхождения.

Идеальным был бы вариант, при котором метод поиска возвращал бы итератор, а не копировал результат в промежуточный контейнер.

В общем, хочу что-то схожее с тем, как устроен индекс в рсубд.
Может есть что-то готовое?

Здравствуйте, SergASh, Вы писали:

SAS>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.

Двоичное дерево поиска. Или отсортированный массив, если данные не надо часто добавлять и удалять.

SAS>Идеальным был бы вариант, при котором метод поиска возвращал бы итератор, а не копировал результат в промежуточный контейнер.
SortedSet.GetViewBetween
https://msdn.microsoft.com/en-us/library/dd381801(v=vs.110).aspx

Здравствуйте, Pzz, Вы писали:

SAS>>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.

Pzz>Двоичное дерево поиска. Или отсортированный массив, если данные не надо часто добавлять и удалять.

Если речь идет о SortedList или SortedSet, то там ключи это одиночные значения, на которых задано отношение порядка через Comparer.
В моем случае ключи — это пары, точнее диапазоны. Отношения порядка на них нет, или по крайней мере я не вижу как его ввести, чтобы
передав методу поиска на вход диапазон я получил набор пересекающихся диапазонов. Пример в исходном посте показывает что нужно от поиска.

SAS>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.
Сделать из диапазона одно значение — никак?
По примеру даты: год*10000+месяц*100+день
Если знаешь пределы чисел диапазона, то какие проблемы?

Здравствуйте, SergASh, Вы писали:

Дерево отрезков — http://code.google.com/p/intervaltree/

Здравствуйте, SergASh, Вы писали:

SAS>Если речь идет о SortedList или SortedSet, то там ключи это одиночные значения, на которых задано отношение порядка через Comparer.
SAS>В моем случае ключи — это пары, точнее диапазоны. Отношения порядка на них нет, или по крайней мере я не вижу как его ввести, чтобы
SAS>передав методу поиска на вход диапазон я получил набор пересекающихся диапазонов. Пример в исходном посте показывает что нужно от поиска.

Упорядочивать по началам диапазонов. Если начала совпадают, упорядочивать по концам. Если совпадают и начала и концы, и это допустимо, упорядочиваыь по какому-нибудь произвольному, но при этом стабильному признаку. Например, по порядку добавления элемента.

Здравствуйте, SergASh, Вы писали:

SAS>Идеальным был бы вариант, при котором метод поиска возвращал бы итератор, а не копировал результат в промежуточный контейнер.
SAS>В общем, хочу что-то схожее с тем, как устроен индекс в рсубд.

Индекс в РСУБД устроен не так. И оптимизирован под эффективное добавление.
Тебе в общем случае нужно что то вроде interval tree. Но, вполне возможно, достаточно просто отсортированного непересекающегося списка диапазонов и бинарного поиска по нему. А может вообще простейшая таблица подойдет, если общий диапазон дискретный и небольшой по размеру. Или вообще надо будет комбинированный вариант делать. Все очень сильно зависит от рода данных.

SAS>Может есть что-то готовое?

Есть диапазоны и алгоримы приведения их к нужному виду в CodeJam. Не покрывается, емнип, только честное интервальное дерево.

Здравствуйте, AndrewVK, Вы писали:

AVK>Есть диапазоны и алгоримы приведения их к нужному виду в CodeJam. Не покрывается, емнип, только честное интервальное дерево.
Они есть, но составные диапазоны по производительности не блещут, получение пересечений O(N) там. Чисто исторически заточены на диапазоны из десятков, ну максимум сотен поддиапазонов и смысла как-то ухищряться никогда не было.

Здравствуйте, SergASh, Вы писали:

SAS>Например, словарь такой:
SAS>

SAS>[ 5, 15] -> Царь
SAS>[35, 50] -> Медведь
SAS>[25, 40] -> Чурка
SAS>

SAS>Подаем на вход [10, 30], получаем
SAS>

SAS>[ 5, 15] -> Царь
SAS>[25, 40] -> Чурка
SAS>

у нас в Nitra

Автор: VladD2
Дата: 18.12.15

похожим образом хранятся позиции в тексте. Для каждого элемента дерева разбора (или АСТ) хранится позиция его начала и позиция его конца. Так как дерево разбора и АСТ получаются по исходникам, то выдерживается правило, что диапазоны не пересекаются, а более мелкие диапазоны вложены в более крупные.

При этом поиск тупым обходом такого дерева получается очень эффективным. Мы просто проверяем пересекается ли позиция с диапазоном и входим в эту ветку, если пересекается. Далее проделываем тоже самое рекурсивно пока не находим самую листовую ветку.

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

Если диапазоны не строго вложены (как с позициями у нас) можно ввести фиктивные узлы хранящие пересекающиеся подузлы. Твой вариант можно представить так:

[ 5, 15] -> Царь
[25, 50]
  [25, 40] -> Чурка
  [35, 50] -> Медведь

Здесь отступ описывает вложенность узлов.

Теперь поиск выливается в банальный перебор корневых веток с заходом в те подветки которые пересекаются с искомым диапазоном.

За счет сортировки вложенных веток можно получить логарифмическую сложность.

Кода будет не мало, но часа за 3 он пишется без проблем.

Здравствуйте, SergASh, Вы писали:


SAS>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.

Если требуется, то в CodeJam залита пробная версия augmented interval tree. Пока альфа, руки дойдут — добью.

Если не хочется тащить за собой всю библиотеку, то можно взять исходники по ссылке и заменить Range<T, Key> на свою структуру с полями From, To, Key. Больше там ничего не надо, емнип. Только тестами тщательно покройте, мало ли

NB: interval tree хорош для составных диапазонов размером от нескольких сотен элементов. Для меньших он может оказаться оверкиллом, CompositeRange<T> внезапно оказался не так уж и ужасен в плане производительности.