Соответствующая структура данных для быстрого поиска «между» парами длинных

Question

я в настоящее время (концептуально) имеем:

IEnumerable<Tuple<long, long, Guid>> 

дал long, мне нужно найти «соответствующий» GUID.

пары long с никогда не должны перекрываться, хотя могут быть промежутки между парами, например:

1, 10, 366586BD-3980-4BD6-AFEB-45C19E8FC989 
11, 15, 920EA34B-246B-41B0-92AF-D03E0AAA2692 
20, 30, 07F9ED50-4FC7-431F-A9E6-783B87B78D0C 

Для каждого входа long, должно быть точно 0 или 1GUID соответствие с.

так что вход 7, должен вернуть 366586BD-3980-4BD6-AFEB-45C19E8FC989

ввод 16 должен возвращать null

Update: У меня есть около 90K пар

Как я должен хранить это в памяти для быстрый поиск?

Благодаря

Answer 1

До тех пор, как они хранятся в порядке, вы можете просто сделать бинарный поиск, основанный на «начала диапазона» против кандидата. Когда вы найдете запись с наивысшим «стартом диапазона», который меньше или равен вашему целевому номеру, либо вы нашли запись с правильным GUID, либо вы доказали, что вы попали в (потому что вход с наименьшим стартом дальности имеет более низкий конец дальности, чем ваша цель).

Вы можете немного упростить логику, сделав ее Dictionary<long, Guid?> и просто запишите начальные точки, добавив запись с нулевым значением для каждого пробела. Затем вам просто нужно найти запись с наивысшим ключом, который меньше или равен вашему целевому номеру, и вернуть значение.

Answer 2

A B-tree на самом деле довольно хорош в этом. В частности, B + -tree, где каждый указатель ветки имеет начало вашего диапазона в качестве ключа. Данные листа могут содержать верхнюю границу, поэтому вы правильно обрабатываете пробелы. Я не уверен, что это лучшее, что вы можете найти где угодно, и вам нужно будет его самостоятельно спроектировать, но, безусловно, он должен иметь очень хорошую производительность.

Answer 3

Попробуйте это (я извиняюсь, а не решение для IEnumerable):

public static Guid? Search(List<Tuple<long, long, Guid>> list, long input) 
{ 
    Tuple<long, long, Guid> item = new Tuple<long,long,Guid> { Item1 = input }; 
    int index = list.BinarySearch(item, Comparer.Instance); 
    if (index >= 0) // Exact match found. 
     return list[index].Item3; 
    index = ~index; 
    if (index == 0) 
     return null; 
    item = list[index - 1]; 
    if ((input >= item.Item1) && (input <= item.Item2)) 
     return item.Item3; 
    return null; 
} 

public class Comparer : IComparer<Tuple<long, long, Guid>> 
{ 
    static public readonly Comparer Instance = new Comparer(); 

    private Comparer() 
    { 
    } 

    public int Compare(Tuple<long,long,Guid> x, Tuple<long,long,Guid> y) 
    { 
     return x.Item1.CompareTo(y.Item1); 
    } 
}