What data structure am I looking for?

Question

Dictionary<List<string>, string> myDictionary = new Dictionary<List<string>, string>
{
    { new List<string> { "blackberries", "orange", "watermelon", "apple" }, "fruits" },
    { new List<string> { "spinach", "kale", "celery", "tomato", "red onion" }, "veggies" },
    { new List<string> { "almonds", "walnuts", "fish oil", "nut butter" }, "fats" },
    { new List<string> { "oatmeal", "brown rice", "beans", "lentils" }, "carbs" },
    { new List<string> { "beef", "chicken", "eggs", "salmon", "mackerel" }, "proteins" },
};

Use case is punching in a string and seeing which key it exists in and spitting out its correct value. Ex:

var temp = myDictionary[new List<string> { "beans" }];

temp returns carbs.

Though the way this is currently structured, this does not work as "beans" does not exist as a key it exists as part of a key.

What structure is best for this type of data usage?

You should probably reverse the order, and then use linq `.GroupBy()` to reverse the order of the array for lookup. — Blue, Aug 22 '18 at 22:29
`var value = myDictionary.FirstOrDefault(kvp => kvp.Key.Contains("beans")).Value ?? "undefined";` this returns the value of the first item whose key contains the string you're searching for, or "undefined" if it doesn't exist. — Rufus L, Aug 22 '18 at 23:27
This is a job for a relationship structure, class called `category`, class called `food`, Many-to-many you would usually stick this in a Database, however you could use A dictionary of list of food, or a mapping list (many to many), or a dictionary of list of category. Or you food could just have a sub list of category , or many options. choose your favorite — TheGeneral, Aug 22 '18 at 23:43

Jim Berg · Answer 1 · 2018-08-22T23:41:41.170

"beans" should be a key with "carb" being the value. Key's should be simple types with the value possibly being complex. It should be neither in your case. Just use a Dictionary where the food is the key and the type of food is the value. You shouldn't have to search within a key to find what value it's associated with. In your example, you'd have to iterate though all of the keys and then search which key matches and then get the value. That defeats the purpose of having a key.

Flip it so that the food type is the key to find what food list it goes with and then build a Dictionary where you can lookup the food type based on the food.

Yes, LINQ can do all sorts of wonderous things, but it will be slow to get there unless you structure things correctly. This is the fastest way you can lookup what you want in either direction.

    var myDictionary = new Dictionary<string, List<string>>
    {
        { "fruits", new List<string> { "raspberries", "blackberries", "blueberries", "orange", "watermelon", "apple", "strawberries" } },
        { "veggies", new List<string> { "spinach", "kale", "carrots", "celery", "tomato", "red onion" } },
        { "fats", new List<string> { "almonds", "walnuts", "fish oil", "nut butter" } },
        { "carbs",new List<string> { "oatmeal", "brown rice", "beans", "lentils" } },
        { "proteins", new List<string> { "beef", "chicken", "eggs", "salmon", "mackerel" } },
    };
        var myFoodIndex = new Dictionary<string, string>();
        foreach(var key in myDictionary.Keys)
        {
            foreach (var foodType in myDictionary[key])
                myFoodIndex.Add(foodType, key);
        }
        Console.WriteLine(myFoodIndex.ContainsKey("beans") ? myFoodIndex["beans"] : "Not Found");
        Console.ReadKey();

I should add that if you want to order the list, use an SortedDictionary or a SortedList. Read more here about the advantages and disadvantages of each.

score 0 · Answer 2 · answered Aug 22 '18 at 22:43

var myItems = new Tuple<List<string>, string>[]
{
    new Tuple<List<string>, string>(new List<string> { "raspberries", "blackberries", "blueberries", "orange", "watermelon", "apple", "strawberries" }, "fruits" ),
    new Tuple<List<string>, string>(new List<string> { "spinach", "kale", "carrots", "celery", "tomato", "red onion" }, "veggies" ),
    new Tuple<List<string>, string>(new List<string> { "almonds", "walnuts", "fish oil", "nut butter" }, "fats" ),
    new Tuple<List<string>, string>(new List<string> { "oatmeal", "brown rice", "beans", "lentils" }, "carbs" ),
    new Tuple<List<string>, string>(new List<string> { "beef", "chicken", "eggs", "salmon", "mackerel" }, "proteins" ),
};

var myDictionary = myItems.SelectMany(t => t.Item1.Select(item => new {item, type = t.Item2}))
    .ToDictionary(a => a.item, a => a.type);

Console.WriteLine(myDictionary["spinach"]);

Umm... yes, but why? And what happens when you try `myDictionary["radish"]`? — Corey, Aug 22 '18 at 22:59

score 0 · Answer 3 · answered Aug 22 '18 at 22:54

Since Dictionary<TKey, TValue> implements IEnumerable<KeyValuePair<TKey, TValue>> you can use LINQ to operate on the data.

In this case your keys are List<string>, and List.Contains will let you check if a string is in the list. Once you find the entry that matches you just need to grab the Value member of the pair. Since KeyValuePair<> is a value type you won't have to worry about null returns from FirstOrDefault so let's use that:

var value = myDictionary.FirstOrDefault(kv => kv.Key.Contains("beans")).Value;

If the string you're searching for ("beans" in this case) isn't found the output will be null.

As to the data structure...

Dictionary<List<string>, string> is an odd choice. You get almost nothing from the object except overheads. You can't use the Dictionary<> methods to get at the data, your 'keys' aren't readily searchable, etc.

For plain storage with a little decoration for easy reading you can use an array of the new ValueTuple<> class like this:

(string Category, string[] Items)[] foods = new[] {
    ("fruits", new[] { "raspberries", "blackberries", "blueberries", "orange", "watermelon", "apple", "strawberries" }),
    ( "veggies", new[] { "spinach", "kale", "carrots", "celery", "tomato", "red onion" }),
    ( "fats", new[] { "almonds", "walnuts", "fish oil", "nut butter" }),
    ( "carbs", new[] { "oatmeal", "brown rice", "beans", "lentils" }),
    ( "proteins", new[] { "beef", "chicken", "eggs", "salmon", "mackerel" }),
};

This is an array with some compile-time stuff to make it simpler to access. The lookup is fundamentally the same:

var value = foods.FirstOrDefault(_ => _.Items.Contains("beans")).Category;

Only one of many, many ways to do it. Without more information on your actual use case there are way too many ways you could go.

The data structure he's looking for is clearly not close to what it needs to be. Getting it to work is one thing, getting it to work well is another. Any answer that involves a linear search isn't likely the best one, especially if this is a smaller example of a much larger database. Your LINQ recommendation is that he does a linear search for the first array which has his value in it which is also searched linearly. — Jim Berg, Aug 23 '18 at 00:05
@JimBerg I answered the question as posed. With a small number of items in the list the search time is less than a millisecond. And with the proposed use - looking up items entered by the user - we're not talking about doing a million lookups over the lifespan of the program. If the question was about *efficient* structures I would answer differently. — Corey, Aug 23 '18 at 22:56
@Correy The OP asked "What structure is best for this type of data usage?" Efficient structures *are* the best structures. We don't know how many eventual users the OP will have for the app or how much data will be contained within it. The worst case search for "mackerel" is 30 times faster using a dictionary vs an array. Think about 30 users getting an answer back in the same time it would take 1 user to get an answer. It only gets worse as the database expands. The most important thing for the OP to learn is using proper indexing to find data vs. brute force methods. — Jim Berg, Aug 25 '18 at 12:06

What data structure am I looking for?

3 Answers3