Performance improvement for Lambda using Array.Contains?

Question

I have this function and I want to improve the performance. The bottleneck is at the end when selection is created and has probably to do with the Contains() function. I don't know a more efficient way to do that selection:

public static Dictionary<string, SubItem> SubItemCache = new Dictionary<string, SubItem>();
public static Dictionary<string, Item> ItemCache = new Dictionary<string, Item>();

private static IEnumerable<Item> GetSimilarItems(int days, string type, 
    float counterOne, float counterTwo)
{
    string[] similarSubItems;

    if (days > 180)
    {
        similarSubItems = SubItemCache.Values
            .Where(p => p.CounterOne >= counterOne * 0.9 
                && p.CounterOne <= counterOne * 1.1)
            .Select(o => o.ID).ToArray();
    }
    else
    {
        similarSubItems = SubItemCache.Values
            .Where(p => p.CounterTwo >= counterTwo * 0.9 
                && p.CounterTwo <= counterTwo * 1.1)
            .Select(o => o.ID).ToArray();
    }

    var selection = ItemCache.Values.Where(p => p.days >= days - 5 && p.days <= days + 5
                                          && p.Type == type
                                          && similarSubItems.Contains(p.Key));

    return selection;
}

Is there a way to improve the function performance wise?

If the result of the function is enumerated more than once, return list or array instead of the differed execution IEnumerable — Slai, May 05 '17 at 21:34
Thanks for the hint. If I understood correctly, by "enumerated more than once" it is meant that if I would do e.g. more than one foreach over the result, or e.g. do further filtering with .Where clauses...? At the moment I only use the result to do a single foreach over it. — flo, May 06 '17 at 06:20
LINQ extensions that return IEnumerable are not executed when defined, but when the result is needed in `foreach`, `.Count()`, `.ToArray`, etc. http://stackoverflow.com/questions/3894490/linq-what-is-the-quickest-way-to-find-out-deferred-execution-or-not. You can leave it as it is if you are using the result only in a `foreach` — Slai, May 06 '17 at 13:06

Scott Chamberlain · Accepted Answer · 2017-05-05T21:21:13.087

Depending on it's size, swap out the string[] with a HashSet<string> and use the .Contains method on that. It will have significantly faster lookup times.

Last time I tested, i found that around 15 items in the collection is when you had faster lookup times with a Hash Set if you compared a straight lookup vs the overhead of building the Hash Set + the lookup.

public static Dictionary<string, SubItem> SubItemCache = new Dictionary<string, SubItem>();
public static Dictionary<string, Item> ItemCache = new Dictionary<string, Item>();

private static IEnumerable<Item> GetSimilarItems(int days, string type, 
    float counterOne, float counterTwo)
{
    HashSet<string> similarSubItems;

    if (days > 180)
    {
        similarSubItems = new HashSet<string>(SubItemCache.Values
            .Where(p => p.CounterOne >= counterOne * 0.9 
                && p.CounterOne <= counterOne * 1.1)
            .Select(o => o.ID));
    }
    else
    {
        similarSubItems = new HashSet<string>(SubItemCache.Values
            .Where(p => p.CounterTwo >= counterTwo * 0.9 
                && p.CounterTwo <= counterTwo * 1.1)
            .Select(o => o.ID));
    }

    var selection = ItemCache.Values.Where(p => p.days >= days - 5 && p.days <= days + 5
                                          && p.Type == type
                                          && similarSubItems.Contains(p.Key));

    return selection;
}

Many thanks. It seems that improved the performance around 20%! — flo, May 06 '17 at 06:21

score 0 · Answer 2 · answered May 06 '17 at 23:40

I can't think of anything simple, but as a final resort you should be able to save another about 20% by avoiding the LINQ and lambda overhead:

private static IEnumerable<Item> GetSimilarItems(int days, string type, 
                                                 float counterOne, float counterTwo)
{
    var similarSubItems = new HashSet<string>();
    var c9 = counterOne * 0.9;
    var c1 = counterOne * 1.1;

    if (days > 180)
    {
        foreach (var p in SubItemCache.Values)
            if (p.CounterOne >= c9 && p.CounterOne <= c1)
                similarSubItems.Add(p.ID);
    }
    else
    {
        foreach (var p in SubItemCache.Values)
            if (p.CounterTwo >= c9 && p.CounterTwo <= c1)
                similarSubItems.Add(p.ID);
    }

    var days0 = days - 5;
    var days1 = days + 5;

    foreach (var p in ItemCache.Values) 
        if (p.days >= days0 && p.days <= days1 
                            && p.Type == type && similarSubItems.Contains(p.Key))
            yield return p;
}

Many thanks! Like you said, it improved the performance even more. — flo, May 07 '17 at 17:05

Performance improvement for Lambda using Array.Contains?

2 Answers2