时间戳

首页 > 解决方案 > 哪个对象用于在内存中对有间隙的查找数据进行排序

c# - 哪个对象用于在内存中对有间隙的查找数据进行排序

问题描述

我可以在 C# net 5.0 中使用哪个对象将以下信息存储在内存中以获得最快的数据检索？

输入：一个数字（长）

示例简化查找数据：

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

列表继续（大约 300 万行查找数据）

在上面的示例数据中：

Input -> output

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

标签： c#.netdata-structures.net-5

解决方案

正如 Llama 提到的，正确的方法是使用二进制搜索。即使对于数以百万计的范围，这也应该提供足够的性能，因为它以 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 && 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));
}

如果您有重叠的范围，您可能需要搜索所有较小的索引，或者使用一些更高级的搜索结构。

推荐阅读