c# - 从 Dictionary,string> 中查找匹配的 KVP，其中搜索键是 List 并返回反向部分匹配

Question

我有一个字典，其中键是一个枚举值列表，值是一个简单的字符串。

我需要做的是使用另一个枚举值列表找到匹配的 KVP。

曲线球和在这里发布的原因是如果我的测试或搜索列表中的列表包含字典中任何键中的所有项目(或枚举对象)，我还需要它返回 KVP。

示例代码摘录:

public enum fruit{ apple , orange , banana , grapes };
public class MyClass
{
    public Dictionary<List<fruit>, string> FruitBaskets = new Dictionary<List<fruit>, string>;
    FruitBaskets.Add(new List<fruit>{apple,orange},"Basket 1");

    List<fruit> SearchList = new List<fruit>{orange,apple,grapes};
}

我需要在字典中搜索 SearchList 并返回“Basket 1”。

请注意，对于这样的示例，匹配可能会比您预期的要倒退，因为我需要键与搜索列表再次匹配，而不是相反，所以搜索列表中不在键中的额外项目是可以的.

我知道我可以简单地迭代 dict 并逐一检查，但我还需要它尽可能快，因为它驻留在运行速度相当快的循环中。

我目前使用的是；

public Dictionary<List<fruit>, string> SearchResults;
foreach (KeyValuePair<List<fruit>, string> FruitBasket in FruitBaskets)
{
    if (FruitBasket.Key.Except(SearchList).Count() == 0)
        SearchResults.Add(FruitBasket);
}

想知道是否有更好/更快的方法。

Answer 1

您需要重新考虑您在字典中选择的键。列表键存在一些主要问题，例如:

1. 不能对 List 使用 O(1) 键查找

2. 您的 key 不是不可变的

3. 您可以将相同的列表作为键而不会收到错误，例如您可以:

   var a = new[] { fruit.organge }.ToList();
   var b = new[] { fruit.organge }.ToList();
   fruitBasket.Add(a, "1");
   fruitBasket.Add(b, "2");
   

但这本词典有效吗？我想不是，但这取决于您的要求。

1. 您可以更改字典键!

因此，您需要更改字典键类型。您可以使用组合的枚举值，而不是使用带按位运算符的列表。为此，您需要为每个枚举值分配 2 的幂:

[Flags]
public Enum Fruit
{
   Orange = 1,
   Apple = 2,
   Banana = 4,
   Grape = 8
}

您必须组合这些枚举值以获得所需的多值枚举字典键效果:

对于 [Fruit.Orange, Fruit.Apple] 你使用 Fruit.Orange |水果.苹果.

下面是合并和分解值的示例代码:

    private static fruit GetKey(IEnumerable<fruit> fruits)
    {
        return fruits.Aggregate((x, y) => x |= y);
    }

    private static IEnumerable<fruit> GetFruits(fruit combo)
    {
        return Enum.GetValues(typeof(fruit)).Cast<int>().Where(x => ((int)combo & x) > 0).Cast<fruit>();
    }

现在您需要一个函数来获取 SearchList 的所有组合(幂集):

    private static IEnumerable<fruit> GetCombinations(IEnumerable<fruit> fruits)
    {
        return Enumerable.Range(0, 1 << fruits.Count())
            .Select(mask => fruits.Where((x, i) => (mask & (1 << i)) > 0))
            .Where(x=>x.Any())
            .Select(x=> GetKey(x));
    }

使用这些组合，您可以使用 O(1) 时间从字典中查找值。

var fruitBaskets = new Dictionary<fruit, string>();

fruitBaskets.Add(GetKey(new List<fruit> { fruit.apple, fruit.orange }), "Basket 1");

List<fruit> SearchList = new List<fruit> { fruit.orange, fruit.apple, fruit.grapes };

foreach (var f in GetCombinations(SearchList))
{
    if (fruitBaskets.ContainsKey(f))
        Console.WriteLine(fruitBaskets[f]);
}