Есть таблица с записями такой структуры (числовые диапазоны [FirstNumber..EndNumber] не пересекаются):
internal class Range
{
internal ulong FirstNumber;
internal ulong EndNumber;
internal string Data;
|
Записей несколько сотен тысяч
Надо загнать ее в память (в какую-нибудь структуру) и быстро по числу найти запись с диапазоном, в который входит это число
Что посоветуете в смысле алгоритма поиска? Нужен быстрый, перебором не пойдет...
Спасибо
Re: Как более быстро искать подходящий диапазон в списке?
Здравствуйте, mDmitriy, Вы писали:
D>Есть таблица с записями такой структуры (числовые диапазоны [FirstNumber..EndNumber] не пересекаются): D>Записей несколько сотен тысяч D>Надо загнать ее в память (в какую-нибудь структуру) и быстро по числу найти запись с диапазоном, в который входит это число D>Что посоветуете в смысле алгоритма поиска? Нужен быстрый, перебором не пойдет...
Отсортировать записи по диапазонам и искать методом половинного деления.
Re: Как более быстро искать подходящий диапазон в списке?
Здравствуйте, mDmitriy, Вы писали:
D>Всем привет!
D>Есть таблица с записями такой структуры (числовые диапазоны [FirstNumber..EndNumber] не пересекаются): D>
D>internal class Range
D>{
D> internal ulong FirstNumber;
D> internal ulong EndNumber;
D> internal string Data;
D>|
D>
D>Записей несколько сотен тысяч D>Надо загнать ее в память (в какую-нибудь структуру) и быстро по числу найти запись с диапазоном, в который входит это число D>Что посоветуете в смысле алгоритма поиска? Нужен быстрый, перебором не пойдет... D>Спасибо
Смотри interval tree
Программа – это мысли спрессованные в код
Re: Как более быстро искать подходящий диапазон в списке?
Здравствуйте, mDmitriy, Вы писали:
D>Всем привет!
D>Есть таблица с записями такой структуры (числовые диапазоны [FirstNumber..EndNumber] не пересекаются): D>
D>internal class Range
D>{
D> internal ulong FirstNumber;
D> internal ulong EndNumber;
D> internal string Data;
D>|
D>
D>Записей несколько сотен тысяч D>Надо загнать ее в память (в какую-нибудь структуру) и быстро по числу найти запись с диапазоном, в который входит это число D>Что посоветуете в смысле алгоритма поиска? Нужен быстрый, перебором не пойдет... D>Спасибо
Посмотри CompositeRange в библиотеке CodeJam.
Там же экстеншин GetIntersection должен выдать пересечнеие.
Я не пользовался, может и перформанс на таких обьемах не дать. Но алгоритмы пересечнений сравнений и тд. там присутствуют.
Re: Как более быстро искать подходящий диапазон в списке?
Здравствуйте, mDmitriy, Вы писали:
D>Всем привет! D>Что посоветуете в смысле алгоритма поиска? Нужен быстрый, перебором не пойдет... D>Спасибо
В CodeJam действительно есть класс для работы с диапазонами, CompositeRange, но он недоделан в плане производительности, руки не доходят.
Зато в CodeJam.Experimental есть то, что тебе нужно — IntervalTree.
Можно не тащить библиотеку, а просто допилить код под твою структуру данных. Всё, что требуется — чтобы входные данные были отсортированы по левой границе, затем по правой.
В плане перфоманса в принципе норм, но можно и ускорить, если заморочиться, перфтесты:
// 10k ranges
Method | Mean | StdDev | Scaled | Scaled-StdDev | GcAllocations |
---------------- |----------:|----------:|-------:|--------------:|--------------:|
Intersect | 38.232 us | 5.2904 us | 1.00 | 0.00 | 208 B |
IntersectTree | 3.665 us | 0.2707 us | 0.097 | 0.0162 | 176 B |
IntersectCostin | 9.058 us | 0.9607 us | 0.24 | 0.044 | 5.36 KB |
// 100k ranges
Method | Mean | StdDev | Scaled | Scaled-StdDev | GcAllocations |
---------------- |-------------:|-----------:|-------:|--------------:|--------------:|
Intersect | 3,740.194 us | 87.1295 us | 1.00 | 0.00 | 208 B |
IntersectTree | 8.625 us | 0.3551 us | 0.0023 | 0.000109 | 176 B |
IntersectCostin | 20.239 us | 1.7635 us | 0.0054 | 0.00048 | 11.05 KB |
us — микросекунды
Intersect — CompositeRange<T>, там O(n) со всеми вытекающими.
IntersectTree — тот самый IntervalTree
IntersectCostin — типовой код из интернета aka "не умею в перфоманс", взят отсюда: https://code.google.com/archive/p/intervaltree/
См на аллокации. 5-10kb на каждый вызов — ну ппц же
Re[2]: Как более быстро искать подходящий диапазон в списке?
Здравствуйте, mDmitriy, Вы писали:
D>Всем привет!
D>Есть таблица с записями такой структуры (числовые диапазоны [FirstNumber..EndNumber] не пересекаются): D>
D>internal class Range
D>{
D> internal ulong FirstNumber;
D> internal ulong EndNumber;
D> internal string Data;
D>|
D>
D>Записей несколько сотен тысяч D>Надо загнать ее в память (в какую-нибудь структуру) и быстро по числу найти запись с диапазоном, в который входит это число D>Что посоветуете в смысле алгоритма поиска? Нужен быстрый, перебором не пойдет... D>Спасибо
public int BinarySearch(
int index,
int count,
T item,
IComparer<T> comparer
)
В компарере сравниваете только FirstNumber. Сможете написать его сами?
Метод вернет или индекс элемента у которого some == FirstNumber, или индекс ближайшего элемента.
Если второе то проверте ближайший элемент списка.
P.S. Это если апдейтов нет между поисками. Если апдейты есть, то тут уже написали — ищите реализацию B-дерева про которое Sinix выше написал.
P.P.S. по моему сначала вам надо бы хотя бы википедию прочитать про бинарный поиск и бинарные деревья.
Здравствуйте, AndrewVK, Вы писали:
S>>Зато в CodeJam.Experimental есть то, что тебе нужно — IntervalTree.
AVK>А чего оно в experimental?
Дакакобычно, руки не доходят.
На неделе дойдёт, надеюсь)
Здравствуйте, mDmitriy, Вы писали:
D>Всем привет!
D>Есть таблица с записями такой структуры (числовые диапазоны [FirstNumber..EndNumber] не пересекаются): D>
D>internal class Range
D>{
D> internal ulong FirstNumber;
D> internal ulong EndNumber;
D> internal string Data;
D>|
D>
D>Записей несколько сотен тысяч D>Надо загнать ее в память (в какую-нибудь структуру) и быстро по числу найти запись с диапазоном, в который входит это число D>Что посоветуете в смысле алгоритма поиска? Нужен быстрый, перебором не пойдет... D>Спасибо
Судя по косвенным признакам, ищем бины. В целом делается как : массив бьется на несколько десятков партишнов, у которых задается минимальный/максимальный диапазон. Поиск в два этапа — сначала находим нужный партишн, потом ищем в нем прямым перебором.
Здравствуйте, Codechanger, Вы писали:
C>Судя по косвенным признакам, ищем бины. В целом делается как : массив бьется на несколько десятков партишнов, у которых задается минимальный/максимальный диапазон. Поиск в два этапа — сначала находим нужный партишн, потом ищем в нем прямым перебором.
Ну то есть interval tree врукопашную. Советовать подобное хардкодное решение можно только зная распределение диапазонов в реальной задаче.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, mDmitriy, Вы писали:
D>числовые диапазоны [FirstNumber..EndNumber] не пересекаются
Достаточно SortedSet с ключем по EndNumber.
Для поиска GetViewBetween + FirstOrDefault.
Re[2]: Как более быстро искать подходящий диапазон в списке?
Здравствуйте, Sinix, Вы писали:
S>В CodeJam действительно есть класс для работы с диапазонами, CompositeRange, но он недоделан в плане производительности, руки не доходят. S>Зато в CodeJam.Experimental есть то, что тебе нужно — IntervalTree.
Здравствуйте, AndrewVK, Вы писали:
AVK>Ну то есть interval tree врукопашную. Советовать подобное хардкодное решение можно только зная распределение диапазонов в реальной задаче.
Если это то, о чем я думаю, то там распределение более-менее известно.
Здравствуйте, Codechanger, Вы писали: C>Если это то, о чем я думаю, то там распределение более-менее известно.
нет, это не бины
это ip-адреса в ulong
распределение неизвестно совсем, так как диапазоны приходят снаружи
Re[2]: Как более быстро искать подходящий диапазон в списке?
Здравствуйте, artelk, Вы писали: A>Достаточно SortedSet с ключем по EndNumber. A>Для поиска GetViewBetween + FirstOrDefault.
отсюда можно подробнее?
аргументом поиска является число, результатом — одна запись, в диапазон которой это число входит
Здравствуйте, mDmitriy, Вы писали:
D>это ip-адреса в ulong
А почему в ulong?
Вобщем, два варианта:
1) Если диапазоны пересекающиеся и изменять их нельзя — interval tree
2) Если непересекающиеся (пересекающиеся можно нормализовать к такому виду, в алгоритмах обсуждали алгоритм, Кодт посоветовал вполне годный с небольшими доработками вариант) — количество вариантов расширяется, банальный табличный вариант с О(1) но ужором памяти, binary search и хеш-таблицы.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали: AVK>А почему в ulong?
ну пока в ulong
там еще про IP6 надо думать в перспективе AVK>Вобщем, два варианта: AVK>2) Если непересекающиеся (пересекающиеся можно нормализовать к такому виду, в алгоритмах обсуждали алгоритм, Кодт посоветовал вполне годный с небольшими доработками вариант) — количество вариантов расширяется, банальный табличный вариант с О(1) но ужором памяти, binary search и хеш-таблицы.
непересекающиеся
склоняюсь к binary search и кешированию найденного
память да, пожрет
Здравствуйте, mDmitriy, Вы писали:
D>Здравствуйте, artelk, Вы писали: A>>Достаточно SortedSet с ключем по EndNumber. A>>Для поиска GetViewBetween + FirstOrDefault. D>отсюда можно подробнее? D>аргументом поиска является число, результатом — одна запись, в диапазон которой это число входит
Пример:
Отсортированные по EndNumber (и одновременно по FirstNumber, т.к. непересекающиеся) интервалы:
[1..5], [7..13], [14..25], [30..42]
Ищем интервал, включающий точку 20.
intervals.GetViewBetween(new Range{EndNumber=20}, intervals.Max) == [14..25], [30..42]
Смотрим только первый [14..25]. Подходит, возвращаем.
Ищем интервал, включающий точку 6.
intervals.GetViewBetween(new Range{EndNumber=6}, intervals.Max) == [7..13], [14..25], [30..42]
Смотрим только первый [7..13]. Не подходит, т.к. FirstNumber у него больше 6.
Т.е.
var intervals = new SortedSet<Range>(Comparer<Range>.Create((x,y) => x.EndNumber.CompareTo(y.EndNumber)));
Range Find(int n)
{
if(intervals.Count == 0) return null;
var range = intervals.GetViewBetween(new Range{EndNumber=n}, intervals.Max).FirstOrDefault();
return range != null && range.FirstNumber <= n ? range = null;
}
