Using ForEach and FindAll of Generics

[Doug]

Hi,

I have a collection of objects and I need to compare each item in the
collection to see if it's a match on any or all of the others. I have
stored my collection in an item like so: "List<PossibleDups> dups"
where PossibleDups is an object of my own creation.

I have been looking at how the ForEach and FindAll methods work and
here is what I was thinking might be a good approach to doing this (in
pseudocode):

1. Use the ForEach method to loop through each item in the
collection.
2. Use the FindAll method inside my Action delegate of the ForEach
method to do my comparison.

This would be pretty neat to get it to work like this (very little
code compared to what I had planned). But I think it won't work as I
would have to do something like this:

private void FindActualDuplicates(List<PossibleDups> dups)
{
possibleDuplicates.ForEach(CompareItems);
}

private void CompareItems(PossibleDups dup)
{
bool isDup = possibleDuplicates.FindAll(FindDups);
}

private static bool FindDups(PossibleDups dup)
{
//Code to determine if dups.
}

If you look at my CompareItems method you can see my problem. I don't
have a clear way to get the Array List into that method (even tho I
coded in the method as if I did get it in there) because the ForEach
only sends one item of that list in at a time.

I know that I could bypass the ForEach altogether and do a FindAll
over the entire collection, but I need to do something like this:

1. Compare object 1 in the collection to object 2, 3, 4.
2. Compare object 2 in the collection to object 3, 4.
3. Compare object 3 in the collection to 4.

In essence, if object 1 is a match to just 2. I still need to see if
3 is a match to just 4 (and so on depending on the number of objects
in the collection). Because of this I don't know if I can get away
with not using the ForEach (or using the old foreach method).

Does anyone have any suggestions? Is this possible? Am I
overthinking it?

 

[Nicholas Paldino [.NET/C# MVP]]

Doug,

I think you are overthinking it. Instead of basically performing a
number of iterations equal to the product of the number of items in each
list, I would take the list you are searching in, and place the items in a
hashtable/dictionary, keying the object on whatever makes the object unique
(its value identity).

Then, you cycle through the items to be searched for, and look in the
hashtable. You will find it is much more efficient.

 

[Peter Duniho]

[...]
If you look at my CompareItems method you can see my problem. I don't
have a clear way to get the Array List into that method (even tho I
coded in the method as if I did get it in there) because the ForEach
only sends one item of that list in at a time.

The delegate for the Action<T> can come from anywhere. In particular, you
could create a special class that simply holds on to the reference you
want, or you could create an anonymous delegate that references the
collection.

So, doing what you want is easy enough.

However, I'd suggest that your proposed solution isn't a very good one.
The algorithm is O(N^2) and very wasteful.

Depending on the exact situation, a more common way to detect duplicates
would be to do one of the following:

* Check for duplicates when adding items. This is also O(N^2) but at
least you keep N smaller, assuming you don't add duplicates when they are
found.

* Keep the list sorted and do the above. Then checking for any one
duplicate is O(log N) and the overall algorithm is only O(N log N). Of
course, you have the overhead of maintaining the list as sorted.

* Only sort the list at the specific moment you want to check for
duplicates. Also O(N log N), does require an extra O(N) iteration through
the list after sorting to do the actual check for duplicates, but without
the overhead of maintaining a sorted list. The net order is still O(N log
N).

If you don't have a need for the list to be sorted normally, I would
choose the last of the above. When you want to find duplicates, sort the
list and then scan through once. By comparing the current object with the
previous one you looked at, you can tell whether there are any duplicates.

Pete

 

[Doug]

Thank you Nick and Peter, I will look into both your suggestions.
Peter, I think I understood yours (but some of it seemed a bit over my
head ) so we'll see how it goes. I'll let you know how it turns
out.