从Dictionary<；列表<；enum>；，字符串>；其中搜索关键字是List<；enum>

本文关键字：lt gt enum 搜索 关键字 List 字符串 列表 Dictionary | 更新日期: 2023-09-27 18:27:08

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

我需要做的是使用另一个枚举值列表来查找匹配的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);
}

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

从Dictionary<；列表<；enum>；，字符串>；其中搜索关键字是List<；enum>

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

  1. 您不能在列表中使用O（1）键查找

  2. 你的钥匙不是一成不变的

  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 | Fruit.Apple。

以下是用于组合和分解值的示例代码：

    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]);
}

考虑以不同的方式存储数据：

var FruitBaskets = Dictionary<fruit, List<string>>();

每个条目都包含与至少一种水果匹配的元素。从您的结构转换如下：

foreach (var kvp in WobblesFruitBaskets)
{
    foreach (var f in kvp.Key)
    {
        List<string> value;
        if (!FruitBaskets.TryGetValue(f, out value))
        {
            value = new List<string>();
            FruitBaskets.Add(f, value);
        }
        value.Add(kvp.Value);
    }
}

现在，搜索看起来是这样的：对于组合密钥searchList，您首先计算单个密钥的结果：

var partialResults = new Dictionary<fruit, List<string>>();
foreach (var key in searchList)
{
    List<string> r;
    if (FruitBaskets.TryGetValue(key, out r))
    {
        partialResults.Add(key, r);
    }
}

现在，剩下的就是组合所有可能的搜索结果。这是最难的部分，我认为这是您的方法固有的：对于具有n元素的键，您有2n-1可能的子键。您可以使用从这个问题的答案生成子集的方法之一，并生成您的最终结果：

var finalResults = new Dictionary<List<fruit>, List<string>>();
foreach (var subkey in GetAllSubsetsOf(searchList))
{
    if (!subkey.Any())
    {
        continue; //I assume you don't want results for an empty key (hence "-1" above)
    }
    var conjunction = new HashSet<string>(partialResults[subkey.First()]);
    foreach (var e in subkey.Skip(1))
    {
        conjunction.IntersectWith(partialResults[e]);
    }
    finalResults.Add(subkey, conjunction.ToList());
}

我已经在结果的值部分将string更改为List<string>。如果你的方法中有一些不变量可以保证总是只有一个结果，那么修复它应该很容易。

如果您从Reference Type创建Dictionary，您只存储了Reference（Not值），那么您不能简单地使用FruitBaskets[XXX]（除非您使用与创建字典节点相同的键），您必须在字典中迭代整个Keys。

我认为这个功能很简单，对你有好处：

bool Contain(List<fruit> KEY)
{
    foreach (var item in FruitBaskets.Keys)
    {
        if (Enumerable.SequenceEqual<fruit>(KEY,item))
            return true;
    }
    return false;
}

这个，

bool B = Contain(new List<fruit> { fruit.apple, fruit.orange }); //this is True

但如果你想考虑成员的排列，你可以使用这个函数：

bool Contain(List<fruit> KEY)
{
    foreach (var item in FruitBaskets.Keys)
    {
        HashSet<fruit> Hkey= new HashSet<fruit>(KEY);
        if (Hkey.SetEquals(item))
            return true;
    }
    return false;
}

这是输出：

bool B1 = Contain(new List<fruit> { fruit.orange, fruit.grapes }); // = False
bool B2 = Contain(new List<fruit> { fruit.orange, fruit.apple }); // = True
bool B3 = Contain(new List<fruit> { fruit.apple, fruit.orange }); // = True
相关文章：