C# Dictionary高效查找与指定目标匹配的Value并返回Key

夜雨闻笛

问题描述：
        有一个已知长度2000的字典【上限字典】，Dictionary<uint, uint>。
        其中key依次为1～2000，value一定是key越大就越大，但没有规律可寻。
        如 [1,5]  [2,8],  [3,9]  [4,15]  [5,21]……
        含义为：key1的上限为5，只要目标数不超过5，方法就要返回1；key2的上限为8，只要目标数不超过8，方法就要返回2
                ……类推……key5的上限为21，只要目标数不超过21，方法就要返回5

        现在需要一个方法，传递一个目标数，匹配字典中符合条件的value并返回这个value对应的key（大于前一个key的value并小于本key的value就算符合条件）
        
        举例：
        指定一个数字12，可得出结果：这个数字比字典的key3的value大，但比key4的value小，则返回4
        指定一个数字11，可得出结果同上，也是返回4
        指定一个数字10，可得出结果还是同上，返回4
        指定一个数字9， 可得出结果：这个数字刚好等于key3的value，返回3
        
        我目前用的二分查找，跑一遍20万次的循环需要耗时700毫秒左右。
        for (uint i = 1; i < 200000; i++)
        {二分找目标(i);}

[C#] 纯文本查看 复制代码

Dictionary<uint, uint> 上限字典 = new(2000);
uint 二分找目标(uint 目标数)
{
    uint 左边界 = 0;
    uint 右边界 = (uint)上限字典.Count - 1;
    uint 中分点 = (左边界 + 右边界) / 2;
    uint 中分点值 = 上限字典[中分点];
    while (左边界 <= 右边界)
    {
        if (中分点值 > 目标数)
        {
            if (上限字典[中分点 - 1] < 目标数)//如果比中分点对应的value小但比中分点-1对应的value多
            {
                return 上限字典.ElementAt((int)中分点 - 1).Key;
            }
            else if (上限字典[中分点 - 1] == 目标数)//如果刚好等于中分点-1的value
            {
                return 上限字典.ElementAt((int)中分点 - 2).Key;
            }
            else//否则更新右边界
            {
                右边界 = 中分点 - 1;
            }
        }
        else if (中分点值 < 目标数)
        {
            if (上限字典[中分点 + 1] > 目标数)//如果比中分点对应的value大但比中分点+1对应的value小
            {
                return 上限字典.ElementAt((int)中分点).Key;
            }
            else if (上限字典[中分点 + 1] == 目标数)//如果刚好等于中分点+1的value
            {
                return 上限字典.ElementAt((int)中分点).Key;
            }
            else//否则更新左边界
            {
                左边界 = 中分点 + 1;
            }
        }
        else//中分点对应的value刚好等于目标数
        {
            return 上限字典.ElementAt((int)中分点 - 1).Key;
        }

        中分点 = (左边界 + 右边界) / 2;
        中分点值 = 上限字典[中分点];
    }

    return 1;}

需求：
        现有方法效率太低，如何更高效率的完成这个查找方法（传递一个目标数，匹配字典中符合条件的value并返回这个value对应的key）。
        任何C#语言写的高效方法都可以，不要求过程，只要足够高效并且能够正确获取结果就行。

con-walk

[C#] 纯文本查看 复制代码

Dictionary<uint, uint> 上限字典 = new(2000) { [1] = 5, [2] = 8, [3] = 9, [4] = 15 };
Dictionary<uint, List<uint>> 倒置字典 = null;

void 准备()
{
    if (倒置字典 is null)
    {
        倒置字典 = [];
        foreach (var 项 in 上限字典)
        {
            if (倒置字典.TryGetValue(项.Value, out var 索引))
            {
                索引.Add(项.Key);
            }
            else
            {
                倒置字典[项.Value] = [项.Key];
            }
        }
    }
}

uint 二分找目标(uint 目标数)
{
    准备();
    if (倒置字典!.TryGetValue(目标数, out var 索引))
    {
        return 索引[0];
    }
    return 0;
}

System.Diagnostics.Stopwatch stopwatch = new();
stopwatch.Start();
for (uint i = 1; i < 200000; i++)
{
    二分找目标(i);
}
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);

DDenry

或许有些答非所问，但如果可以简化问题等同于“双向字典”：一种是依赖第三方开源库实现;另一种就是同时构建两个字典，<key,value>和<value,key>。

夜雨闻笛

con-walk 发表于 2024-7-9 09:48

[C#] 纯文本查看 复制代码

Dictionary 上限字典 = new(2000) { [1] = 5, [2] = 8, [3] = 9, [4] = 15 };
D ...[/quote]
[mw_shl_code=csharp,true]Dictionary<uint, List<uint>> 倒置字典 = null!;
Dictionary<uint, uint> 上限字典 = new() { { 1, 5 }, { 2, 8 }, { 3, 9 }, { 4, 15 }, { 5, 21 } };
uint 结果;
for (uint i = 1; i <= 21; i++)
{
    结果 = 二分找目标(i);
    Console.WriteLine($"当前要找的值：{i}，找到的结果为：{结果}");
}

//结果预览：
//当前要找的值：1，找到的结果为：0
//当前要找的值：2，找到的结果为：0
//当前要找的值：3，找到的结果为：0
//当前要找的值：4，找到的结果为：0
//当前要找的值：5，找到的结果为：1
//当前要找的值：6，找到的结果为：0
//当前要找的值：7，找到的结果为：0
//当前要找的值：8，找到的结果为：2
//当前要找的值：9，找到的结果为：3
//当前要找的值：10，找到的结果为：0
//当前要找的值：11，找到的结果为：0
//当前要找的值：12，找到的结果为：0
//当前要找的值：13，找到的结果为：0
//当前要找的值：14，找到的结果为：0
//当前要找的值：15，找到的结果为：4
//当前要找的值：16，找到的结果为：0
//当前要找的值：17，找到的结果为：0
//当前要找的值：18，找到的结果为：0
//当前要找的值：19，找到的结果为：0
//当前要找的值：20，找到的结果为：0
//当前要找的值：21，找到的结果为：5


大佬你好，非常感蟹大佬的回复。
不过我在实测您的代码时遇到了一个问题：

本次求值的循环中，只有彩色标记的是求值成功了的，其他都是返回的0。也就是说，您的方法只有在value刚好等于所求目标的时候，才能返回对应的key。
而我需求的效果是：（举例说明）
假定 Dictionary<uint, uint> 上限字典 = new() { { 1, 5 }, { 2, 8 }, { 3, 9 }, { 4, 15 }, { 5, 21 } };
还是按照上面的循环来操作：
当所求目标=21的时候，刚好返回了5，这是正确的。
但我想要的结果是：当所求目标大于key4的值（15）且小于等于key5的值（21）的时候，都要返回5。
也就是说上面循环结果中  16  17  18  19  20的返回结果都是0，但我需要他们都返回5。
同理，10  11  12  13  14  这几个都大于 key3的值（9）且小于等于key4的值（15），那么他们都要返回4。


表达能力有限，大佬您要是不嫌我啰嗦，我换个方式来说：
Dictionary<uint, uint> 上限字典 = new() { { 1, 5 }, { 2, 8 }, { 3, 9 }, { 4, 15 }, { 5, 21 } };
这个字典中，每一组元素代表的含义是：1的上限是5，但只有不超过5的，都返回1。  2的上限是8，只要不超过8的，都返回2。  3的上限是9，只要不超过9的，都返回3……类推，5的上限是21，只要不超过21的，都返回5

不知道您还能否对刚才的代码进行一下改进？

夜雨闻笛

夜雨闻笛 发表于 2024-7-9 10:37
[mw_shl_code=csharp,true]Dictionary 倒置字典 = null!;
Dictionary 上限字典 = new() { { 1, 5 }, { 2 ...

代码块好像乱了，我插入代码的时候可能拍了一下版导致了一些莫名其妙的乱入。
现在不让编辑了。

womaromar

这个时间复杂度已经是log n的级别了，也不好再快了吧，不知道开多个线程按照不同区间计算有没有用

con-walk

没有你的数据集, 你自己试试吧.

[C#] 纯文本查看 复制代码

const int Length = 2000;

Dictionary<uint, uint> 上限字典 = new(Length) { [1] = 5, [2] = 8, [3] = 9, [4] = 15 };
List<取值项> 列表 = new(Length);

for (int h = 0; h < Length; h++)
{
    列表.Add(new());
}

int i = 0;
uint 最后一个上限项的键 = 0;
foreach (var 上限项 in 上限字典)
{
    列表[i].索引.Add(上限项.Key);
    列表[i].范围.结束 = 上限项.Value;
    列表[i + 1].范围.起始 = 上限项.Value;
    最后一个上限项的键 = 上限项.Key;
    i++;
}
列表[i] = 列表[i] with
{
    范围 = 列表[i].范围 with { 结束 = uint.MaxValue },
    索引 = [.. 列表[i].索引, 最后一个上限项的键]
};

uint 查找(uint 值)
{
    var 查找结果 = 列表.Find(p => p.范围.范围内(值));
    if (查找结果 is not null)
    {
        return 查找结果.索引[0];
    }
    return default;
}

System.Diagnostics.Stopwatch stopwatch = new();
stopwatch.Start();
uint 结果;
for (uint k = 1; k <= 200000; k++)
{
    结果 = 查找(k);
    Console.WriteLine($"当前要找的值：{k}，找到的结果为：{结果}");
}
stopwatch.Stop();
Console.WriteLine(stopwatch.ElapsedMilliseconds);

record 范围键()
{
    public uint 起始;
    public uint 结束;
    public bool 范围内(uint 值) => 值 >= 起始 && 值 < 结束;
}
record 取值项()
{
    public 范围键 范围 = new();
    public List<uint> 索引 = [];
}

夜雨闻笛

con-walk 发表于 2024-7-9 21:46
没有你的数据集, 你自己试试吧.
[mw_shl_code=csharp,true]const int Length = 2000;

大佬你好，我找到了二分查找效率低的原因了，不是二分法自身不行，而是【上限字典.ElementAt((int)中分点).Key;】这行代码的问题。
字典调用ElementAt方法获取key的效率非常低，所以我根据你的代码提供的思路生成了倒置字典后，再依据倒置字典进行二分法查找，这样就省去了ElementAt方法，效率就从700毫秒提升到30毫秒，达到了我的预期。
再次感谢大佬。
祝生活顺心

con-walk

夜雨闻笛 发表于 2024-7-9 23:53
大佬你好，我找到了二分查找效率低的原因了，不是二分法自身不行，而是【上限字典.ElementAt((int)中分点 ...

麻烦你试一下后来我给出的那个方式, 帮我看看效率如何, 我也想知道这个方式是否能提高效率. 谢谢.