Информация об изменениях

Сообщение Re: Как более быстро искать подходящий диапазон в списке? от 26.09.2017 7:24

Изменено 26.09.2017 7:38 VladCore

Старый текст
Новый текст
Разница

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>Спасибо

https://msdn.microsoft.com/ru-ru/library/a1s5syxa(v=vs.110).aspx

public int BinarySearch(
    int index,
    int count,
    T item,
    IComparer<T> comparer
)

В компарере сравниваете только FirstNumber. Сможете написать его сами?
Метод вернет или индекс элемента у которого some == FirstNumber, или индекс ближайшего элемента.
Если второе то проверте ближайший элемент списка.

P.S. Это если апдейтов нет между поисками. Если апдейты есть, то тут уже написали — ищите реализацию B-дерева про которое Sinix выше написал.

Re: Как более быстро искать подходящий диапазон в списке?

D>internal class Range
D>{
D>    internal ulong FirstNumber;
D>    internal ulong EndNumber;
D>    internal string Data;
D>|
D>

public int BinarySearch(
    int index,
    int count,
    T item,
    IComparer<T> comparer
)