Блог

Какой объект я могу использовать в C# net 5.0 для хранения следующей информации в памяти, чтобы получить самый быстрый поиск данных?

Ввод : число (длинное)

Пример упрощенных данных поиска:

 1 -> 10          : ResultA
300 -> 300       : ResultB
500 -> 10000     : ResultC
235015 -> 235820 : ResultD
...
 

Список можно продолжить (около 3 миллионов строк данных поиска)

В приведенном выше примере данных:

 Input -> output

5 -> ResultA
300 -> ResultB
400 -> Not found/null
9999 -> ResultC
1000000 -> Not found/null
 

Как упоминает Лама, правильным подходом было бы использовать двоичный поиск. Это должно обеспечить достаточную производительность даже для многих миллионов диапазонов, поскольку оно масштабируется с помощью O(log n) для достаточно хорошо распределенных данных.

Если диапазоны не перекрываются, должно сработать что-то подобное:

     // Assume sorted
        var rangesArray = new[]
        {
            (1, 10, "A"),
            (300, 300, "B"),
            (500, 10000, "C"),
            (235015, 235820, "D")
        };
        var rangesList = rangesArray.ToList();
        var toSearchFor = 9999;

        var comparer = new KeyComparer<(int, int, string), int>(p => p.Item1);
        var index = rangesList.BinarySearch((toSearchFor, 0, ""), comparer);
        if (index < 0) // negative values mean a exact match could not be found, 
        {
            // Take bitwise complement to get index of the element larger than the toSearchFor
            // remove one get the actual range to check
            index = ~index -1; 
            if (index > 0 amp;amp; toSearchFor < rangesList[index].Item2 )
            {
                Console.WriteLine($"Found Range {index}");
            }
            else
            {
                Console.WriteLine($"Not Found");
            }
        }
        else
        {
            Console.WriteLine($"Found Exact Range {index}");
        }
 

Как написать универсальный IComparer

 public class KeyComparer<T, TKey> : IComparer<T> where TKey : IComparable<TKey>
{
    private readonly Func<T, TKey> selector;
    public KeyComparer(Func<T, TKey> selector) => this.selector = selector;
    public int Compare(T x, T y) => selector(x).CompareTo(selector(y));
}
 

Если у вас есть перекрывающиеся диапазоны, вам, возможно, потребуется выполнить поиск по всем меньшим индексам или использовать более продвинутую структуру поиска.

Как насчет такого подхода? Имейте в виду, что при этом учитывается только начальное значение, потому что вы сказали, что у вас есть только пробелы, но нет перекрытия. В этом случае все стало бы еще сложнее.

 public static class Program
{
    static void Main(string[] args)
    {
        var random = new Random();
        // Create a list with random items.
        var source = Enumerable.Range(0, 1000)
            .Select(_ => new SortableObject { Start = random.Next(100000) })
            .ToList();

        // Sort the list by using a dedicated comparer
        source.Sort(SortableObjectComparer.Default);
        // Define an element to search for
        var searchElement = new SortableObject { Start = 17432 };
        // Get the index of the best matching item
        var found = source.BinarySearch(searchElement, SortableObjectComparer.Default);

        if(found < 0)
        {
            // No exact match, get the best candidates.
            var nextElement = source[~found];
            var beforeElement = source[~found - 1];

            Console.WriteLine($"Element with lower start value: {beforeElement.Value}");
            Console.WriteLine($"Element to search {searchElement.Value}");
            Console.WriteLine($"Element with higher start value: {nextElement.Value}");
        }
        else
        {
            // Exact match
            var matchingElement = source[found];
            Console.WriteLine($"Element matching: {matchingElement.Value}");
            Console.WriteLine($"Element to search {searchElement.Value}");
        }
    }
}

public class SortableObjectComparer : IComparer<SortableObject>
{
    public static readonly IComparer<SortableObject> Default = new SortableObjectComparer();
    public int Compare(SortableObject x, SortableObject y)
    {
        if (ReferenceEquals(x, y))
            return 0;

        if (ReferenceEquals(x, null))
            return -1;

        if (ReferenceEquals(y, null))
            return 1;

        return x.Start.CompareTo(y.Start);
    }
}

public class SortableObject
{
    public long Start { get; set; }
    public long End { get; set; }
    public string Value => $"Result {Start}";
}