Сообщение Re: Посоветуйте структуру данных от 11.01.2017 21:22
Изменено 12.01.2017 7:16 Sinix
Re: Посоветуйте структуру данных
Здравствуйте, SergASh, Вы писали:
SAS>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.
Если требуется, то в CodeJam залита пробная версия augmented interval tree. Это совсем-совсем альфа, практически без тестов и проверок. Весь функционал — отбор интервалов, пересекающихся с заданным. Руки дойдут — добью.
Если не хочется тащить за собой всю библиотеку, то можно взять исходники по ссылке и заменить Range<T, Key> на свою структуру с полями From, To, Key. Больше там ничего не надо, емнип. Только тестами тщательно покройте, мало ли
NB: interval tree хорош для составных диапазонов размером от нескольких сотен элементов. Для меньших он может оказаться оверкиллом, CompositeRange<T> внезапно оказался не так уж и ужасен в плане производительности.
SAS>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.
Если требуется, то в CodeJam залита пробная версия augmented interval tree. Это совсем-совсем альфа, практически без тестов и проверок. Весь функционал — отбор интервалов, пересекающихся с заданным. Руки дойдут — добью.
Если не хочется тащить за собой всю библиотеку, то можно взять исходники по ссылке и заменить Range<T, Key> на свою структуру с полями From, To, Key. Больше там ничего не надо, емнип. Только тестами тщательно покройте, мало ли
NB: interval tree хорош для составных диапазонов размером от нескольких сотен элементов. Для меньших он может оказаться оверкиллом, CompositeRange<T> внезапно оказался не так уж и ужасен в плане производительности.
Re: Посоветуйте структуру данных
Здравствуйте, SergASh, Вы писали:
SAS>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.
Если требуется, то в CodeJam залита пробная версия augmented interval tree. Пока альфа, руки дойдут — добью.
Если не хочется тащить за собой всю библиотеку, то можно взять исходники по ссылке и заменить Range<T, Key> на свою структуру с полями From, To, Key. Больше там ничего не надо, емнип. Только тестами тщательно покройте, мало ли
NB: interval tree хорош для составных диапазонов размером от нескольких сотен элементов. Для меньших он может оказаться оверкиллом, CompositeRange<T> внезапно оказался не так уж и ужасен в плане производительности.
SAS>Нужна структура данных, работающая как словарь, только чтобы ключ был не одиночным значением, а диапазоном.
SAS>Основная операция будет поиск всех вхождений, ключи которых пересекаются с заданным диапазоном.
Если требуется, то в CodeJam залита пробная версия augmented interval tree. Пока альфа, руки дойдут — добью.
Если не хочется тащить за собой всю библиотеку, то можно взять исходники по ссылке и заменить Range<T, Key> на свою структуру с полями From, To, Key. Больше там ничего не надо, емнип. Только тестами тщательно покройте, мало ли
NB: interval tree хорош для составных диапазонов размером от нескольких сотен элементов. Для меньших он может оказаться оверкиллом, CompositeRange<T> внезапно оказался не так уж и ужасен в плане производительности.