Find matching KVP from Dictionary,string> where search key is List and return reverse partial matches

Question

I have a Dictionary where the key is a list of enum values, and the value is a simple string.

What I need to do is using another list of enum values find the match KVP.

The curveball and reason for posting here is I also need it to return KVP if the list from my test or search list contains all the items (or enum objects) in any key in the dictionary.

example excerpt of code:

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

I need to search the dictionary for SearchList and return "Basket 1".

Note that the matching may be backwards than what you would expect for such an example as I need the key to match agains the search list and not vice versa, so extra items in the search list that are not in the key are ok.

I know I could simply iterate the dict and check one by one but I also need this to be as fast as possible as it resides in a loop that is running fairly fast.

What I am currently using is;

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

Wondering if there is a better/faster way.

brz · Accepted Answer · 2014-10-19T18:24:54.237

You need to rethink about you choice of Keys in dictionary. There are some major problem with List keys, such as:

You can't use O(1) key lookup with List
Your keys aren't immutable

You can have identical lists as keys without receiving errors, for example you can have:

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

But is this dictionary valid? I guess not but it depends on your requirements.

You can change Dictionary keys!

For this reasons, you need to change your dictionary key type. You can use combined Enum values instead of using a List with bitwise operators. For this to work, you need to assign powers of 2 to each enum value:

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

You have to combine these enum values to get the desired multi-value enum dictionary key effect:

For [Fruit.Orange, Fruit.Apple] you use Fruit.Orange | Fruit.Apple.

Here's a sample code for combining and decomposing values:

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

Now you need a function to get all combinaions (power set) of the 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));
    }

Using these combinations, you can lookup values from dictionary using O(1) time.

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

score 0 · Answer 2 · edited May 23 '17 at 11:52

Consider storing your data in a different way:

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

Each entry contains elements that match at least one fruit. Conversion from your structure is as follows:

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

Now, the search would look like this: For a composed key searchList you first calculate results for single keys:

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

Now, what is left is to compose all possible search results. This is the hardest part, which I believe is inherent to your approach: for a key with n elements you have 2ⁿ - 1 possible subkeys. You can use one of subset generating approaches from answers to this question and generate your final result:

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

I've changed string to List<string> in result's value part. If there is some invariant in your approach that guarantees there will be always only one result, then it should be easy to fix that.

I think you understand what I am asking, but I'm having trouble believing that restructuring my data like that would not result in a performance impact, as the values in the search List are constantly changing and this all happens inside a loop. — Wobbles, Oct 18 '14 at 13:11
@Wobbles Honestly, I'm not sure either. Guess it depends on `Except` complexity - for good hashing it may approach `O(n)`, but otherwise it's `O(n^2)` - and how many elements can you have in your search term. 99.99999% of the time the only reasonable way to know is to measure :) Another idea to make things faster a bit, is to encode enum values in binary, and use bit operations to compare keys. — BartoszKP, Oct 18 '14 at 13:18
You may be on to something with using byte type enums, ill have to play around with it. — Wobbles, Oct 18 '14 at 13:45
You can mark enums with a `flag` attribute, in order to use bitwise operators against them http://msdn.microsoft.com/en-us/library/system.flagsattribute(v=vs.110).aspx — Jason, Oct 18 '14 at 13:50
@Jason coincidentally my enums are already of the byte type, its just a matter of seeing if a iterating byte comparer is any faster than my above Except list comparer, I suspect the comparer for the byte type is more efficient. — Wobbles, Oct 18 '14 at 13:57

Mehdi Khademloo · Answer 3 · 2014-10-18T13:41:05.680

if you create a Dictionary from a Reference Type, you stored just the Reference (Not value), then you can't use simply FruitBaskets[XXX] (except you use the same key that you create the node of dictionary), you must iterate whole of Keys in your dictionary.

I think this function is easy and good for you:

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

and this,

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

But if you want to consider the permutation of members, you can use this function:

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

and here's the output:

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

But would this also return true for `Contain(new List { fruit.apple, fruit.orange, fruit.grapes });` ? thats the difficult part and what I ultimately need. — Wobbles, Oct 18 '14 at 13:52

Find matching KVP from Dictionary,string> where search key is List and return reverse partial matches

3 Answers3