Efficient list self compare in LINQ?

Question

This may be very similar to this question but I would like to know the most efficient way in C# and LINQ to compare a list of elements to each other in the same list.

For example, in pseudo code I would like to do this:

foreach(i in list)    
    foreach(j in list.Except(i))    
        Compare(j,i)

I know that Except takes an enumerable instead of single item and may not be the best idea, but it should illustrate my intent.

Any ideas?

Update:

I guess this question was a bit to vague. The goal was to iterate over an list twice (using LINQ) while skipping over the pair (i, i); whatever Compare(i,j) actually does is irrelevant to my question.

There's two cases then, one where (i,j) == (j,i) and (i,j) != (j,i). For the former, George Duckett's skipwhile solution below does the trick, but what about the latter? This is where my original use of Except came in so that both (i,j) and (j,i) would be evaluated.

So to clarify, is there a better way to skip over an element in a list, other than list.Except(Enumerable.Repeat(i,1))?

What are you intending to do with the results of comparison, as that might demand certain approaches. Also, please define "efficient" in the sense that is required. — Grant Thomas, Nov 16 '11 at 16:41
What do you want it to do when it compares, should it return as soon as the Compare returns false, etc? — pstrjds, Nov 16 '11 at 16:42
you are really trying to compare two arrays, the best i know is using quicksort (nlogn) and then a linear compare , so the total solution might be nlogn + n which is nlogn. I think the linq sort uses quicksort — np-hard, Nov 16 '11 at 16:45
Your pseudocode doesn't make much sense. What should be the result of all this? Maybe an example would help. — svick, Nov 16 '11 at 16:45
By efficient I guess I really mean elegant-for-linq. For example, creating an enumerable via Repeat(i, 1) for the Except() on each iteration doesn't seem that elegant to me. Is there any alternative to that? — E.Beach, Nov 16 '11 at 16:46
Note that your example compares `j` to `i` and `i` to `j`, that might not be needed, depending on `Compare`. — George Duckett, Nov 16 '11 at 16:47
@Shai: just a note: coding and making baseless statements about efficiency don't work well together. — R. Martinho Fernandes, Nov 16 '11 at 16:50
@Shai: sure. http://chat.stackoverflow.com/rooms/5058/linq-vs-efficient — R. Martinho Fernandes, Nov 16 '11 at 17:16
Does this answer your question? [Comparing each element with each other element in a list](https://stackoverflow.com/questions/17031771/comparing-each-element-with-each-other-element-in-a-list) — StayOnTarget, Nov 18 '20 at 18:09

score 8 · Answer 1 · answered Nov 16 '11 at 16:53

This will give you all pairs, assuming the order of pairs doesn't matter (Compare(i, j) == Compare(j, i)):

var test = from i in list
           from j in list.SkipWhile(j => j != i)
           where i != j // Remove the self-comparison if you want to
           select Compare(i, j);

pstrjds · Answer 2 · 2017-10-25T16:38:38.967

4

I don't know if you have a requirement for LINQ, but I would most likely write this code this way that way when I review the code 3 weeks from now, at a glance I know what is going on.

for(var i = 0; i < list.Count; ++i)
{
    var item = list[i];
    for(var j = i+1; j < list.Count; ++j)
    {
        Compare(item, list[j]);
    }
}

if you want to still use some LINQ, you could rewrite it this way:

for(var i = 0; i < list.Count; ++i)
{
    var item = list[i];
    foreach(var j in list.Skip(i+1))
    {
        Compare(item, j);
    }
}

edited Oct 25 '17 at 16:38

answered Nov 16 '11 at 16:47

pstrjds

16,840
6
52
61

I like the cleanliness of this code, but the Linq version could suffer from bad performance from the `.Skip()` method: http://stackoverflow.com/questions/20002975/performance-of-skip-and-similar-functions-like-take – Chakrava Jun 03 '16 at 00:31
1

@pstrjds I'm actually using a variant of this now to speed up some unnecessary duplication of logic. It's saved me a lot of processing time, so cheers! – Steve Oct 25 '17 at 17:53

score 2 · Answer 3 · answered Nov 16 '11 at 16:55

2

Your requirement need to illustrate more, but this can help you:

List<int> list = new List<int>() { 1, 2, 3, 4 };
var result = list.Aggregate((p, q) => p.CompareTo(q) > 0 ? p : q);//Return 4

answered Nov 16 '11 at 16:55

Reza ArabQaeni

4,848
27
46

score 1 · Answer 4 · answered Nov 16 '11 at 17:22

Your question's a bit vague as to what you want to do with the compared results, but here's an idea:

public static IEnumerable<TResult> Compare<T, TResult>(this IEnumerable<T> source,  Func<T, T, TResult> func)
{
    int i = 0;
    foreach (T item1 in source)
    {
        foreach (T item2 in source.Skip(i))
            yield return func(item1, item2);
        i++;
    }
}

Then you can do whatever you want with the compared results. For example, with these List objects:

List<string> list = new List<string> { "test", "hello", "foo", "bar" };

You could do this:

var compared = list.Compare((item1, item2) => item1.Equals(item2));
//compared will be IEnumerable<bool> in this case

Or this:

var compared = list.Compare((item1, item2) => new { item1, item2 });
//to get an enumerator of all the different comparisons of the 2 lists

Efficient list self compare in LINQ?

4 Answers4

Linked