How to do this multi-dimension collection comparison (with or w/o LINQ)

user_3521178 0
Viewed 42

I currently have two collections: a Dictionary<Type,Func<int,bool>> Target to test against, and a List<(Type,int)> Items which is a value to test against the dictionary. The dictionary type is required to enforce unique entries elsewhere in code, but should otherwise behave as a collection in this test.

Let's say the dictionary has one item: {typeof(bool),(x)=>x==2}.

Let's say the List has one item: (typeof(bool),2).

I need to express that the above two collections are equal.

Let's reset and say the dictionary has two items: {typeof(bool), (x)=>x==2}, {typeof(int), (x)=>x==3}

...And the List has one item: (typeof(bool),3). This collection comparison is not equal because the Func evals to false.

...Change the one list item to : (typeof(bool),2) This is invalid because the Func evals to true, but missing an argument for the typeof(int) check.

...Change the list to have two items: (typeof(bool),2),(typeof(int),3). In this case, the two collections are equal.

How can I write an equality check for this in a performant manner?

I have tried these:

bool isEqual = Items.All(o => Target.TryGetValue(o.Type, out var f) && f(o.Count));

bool isEqual = Target.All(o => Items.Any(i => o.Key == i.Type && o.Value(i.Count)));

They both fail, for the following pseudo-explanation: they will be true for an unbalanced condition, i.e. the Target dict has more types than the Items, or the Items list has more types than Target.

Here is the code sample:

Dictionary<Type, Func<int, bool>> Target = new();
List<(Type Type, int Count)> Items = new();

Target.Add(typeof(bool), (x) => x == 2);

Items.Add((typeof(bool), 2));

Func<bool> test1 = () => 
    Items.All(o => Target.TryGetValue(o.Type, out var f) && f(o.Count));

Func<bool> test2 = () => 
    Target.All(o => Items.Any(i => o.Key == i.Type && o.Value(i.Count)));

var attempt1 = test1.Invoke();
var attempt2 = test2.Invoke();

Target.Add(typeof(int), (x) => x == 3);

// true, but wrong
var attempt3 = test1.Invoke(); 
// false, but returns true incorrectly if Target is one
// item and matches one item in a List of two items
var attempt4 = test2.Invoke();

Target is equal to Items if both have the same types with equal counts determined by evaluating the Func.

I think the above two Linq statements are bad because they are exponential, each iteration must iterate multiple times. Ideally, if I could match on type, return false if no matching types, then evaluate the Func, and return false if the count check fails. Repeat for each type. This would seem to be O(n) performance which would be better than exponential.

Do you have a good performant way to achieve the above?

linq c#
2 Answers

Answering my own question, but I hope you can offer an alternative. As you can see, it requires the memory overhead of instantiating an anonymous type, but includes two short circuits to improve efficiency.

public static bool IsEqual(Dictionary<Type,Func<int,bool>> Target,IEnumerable<(Type Type, int Count)> test)
{
    if(Target.Count != test.Count()) { return false; }

    var joined = Members.Join(test, (i) => i.Key, (o) => o.Type, (a, j) => new {Count = j.Count,Func = a.Value });

    // Since the join matched on the type, if the result count is less it means a non-matching type was present.
    if(joined.Count() != Members.Count) { return false; }

    return joined.All((o) => o.Func(o.Count));

}
user_35211780

You need two checks. One whether the count of matching types equals the count of both collections, and another - that you already coded - that checks that each value in Items has a matching Func returning true for its value.

A one liner in LinQ:

bool areSame  = Items.Select(i => i.Type).Intersect(Target.Keys).Count() == Items.Count == Target.Count
             && Items.All(o => Target.TryGetValue(o.Type, out var f) && f(o.Count));

As a complete test:

            Dictionary<Type, Func<int, bool>> Target = new() { { typeof(bool), x => x == 2 }, { typeof(int), x => x == 3 } };
            List<(Type Type, int Count)> Items = new() { (typeof(bool), 2 ), ( typeof(int), 3 ) };
            
            Console.WriteLine(AreSame()); //true

            Items.Add((typeof(float), 16));
            Console.WriteLine(AreSame()); //false

            Target.Add(typeof(float), x => x == 16);
            Console.WriteLine(AreSame()); //true

            bool AreSame()  => Items.Select(i => i.Type).Intersect(Target.Keys).Count() == Items.Count == Target.Count && Items.All(o => Target.TryGetValue(o.Type, out var f) && f(o.Count));
user_57394430
Related