4

我目前（概念上）有：

IEnumerable<Tuple<long, long, Guid>>

给定 a long，我需要找到“对应的” GUID。

s对long不应重叠，尽管对之间可能存在间隙，例如：

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

对于每个 input long，应该有完全0或1匹配GUID的 s。

所以 , 的输入7应该返回366586BD-3980-4BD6-AFEB-45C19E8FC989

16应该返回的输入null

更新：我有大约 90K 双

我应该如何将此存储在内存中以进行快速搜索？

谢谢

4

3 回答 3

6

只要它们按顺序存储，您就可以根据“范围开始”与候选者进行二进制搜索。一旦您找到具有小于或等于您的目标数字的最高“范围开始”的条目，那么您要么找到了具有正确 GUID 的条目，要么您已经证明您已经达到了差距（因为具有最高较小范围起点的条目具有比您的目标更低的范围终点）。

Dictionary<long, Guid?>您可以通过将其设置为 a并仅记录起点，为每个间隙添加一个具有空值的条目，从而可能会稍微简化逻辑。然后你只需要找到最大键小于或等于你的目标数的条目，并返回值。

于 2013-04-26T10:56:15.883 回答
2

试试这个（对不起，不是您的 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);
    }
}
于 2013-04-26T11:16:12.147 回答
1

B-tree实际上很擅长这一点。具体来说，一个 B+-树，其中每个分支指针都以范围的开头作为键。叶数据可以包含上限，因此您可以正确处理间隙。我不确定它是否是你能在任何地方找到的最好的，你需要自己设计它，但它肯定有非常好的性能。

于 2013-04-26T10:59:49.297 回答