Best way to check values from a list that are not contained in another list. (Performance Testing)

Question

I was performing some performance tests between various ways of checking which objects are in one list, but not in the other. And I came up with a result I did not expect, the average time for executing the same action using lambda was the highest between while, for, foreach, and lambda.

Code used:

// Object
public class ComplexObject
{
    public int Number { get; set; }
    public char Character { get; set; }
}

// Lists
private readonly List<ComplexObject> _complexList1 = new List<ComplexObject>();
private readonly List<ComplexObject> _complexList2 = new List<ComplexObject>();

/* Fills in lists with numbers from 0 to 100000 and characters from 0 to 50.
 * The first list contains 10000 records and a second list contains 1000 records. */
private void FillLists()
{
    var rnd = new Random();
    for (int i = 0; i < 100000; i++)
    {
        _complexList1.Add(new ComplexObject
        {
            Number = rnd.Next(5000),
            Character = (char)rnd.Next(50)
        });
    }
    for (int i = 0; i < 1000; i++)
    {
        _complexList2.Add(new ComplexObject
        {
            Number = rnd.Next(5000),
            Character = (char)rnd.Next(50)
        });
    }
}

// For
public void ExecuteFor()
{
    var result = new List<ComplexObject>();
    for (int countList2 = 0; countList2 < _complexList2.Count; countList2++)
    {
        bool found = false;
        for (int countList1 = 0; countList1 < _complexList1.Count; countList1++)
        {
            if (_complexList2[countList2].Number == _complexList1[countList1].Number &&
                _complexList2[countList2].Character == _complexList1[countList1].Character)
            {
                found = true;
                break;
            }
        }

        if (!found)
            result.Add(_complexList2[countList2]);
    }
}

// Foreach
public void ExecuteForeach()
{
    var result = new List<ComplexObject>();
    foreach (ComplexObject object2 in _complexList2)
    {
        bool found = false;
        foreach (ComplexObject object1 in _complexList1)
        {
            if (object2.Number == object1.Number &&
                object2.Character == object1.Character)
            {
                found = true;
                break;
            }
        }

        if (!found)
            result.Add(object2);
    }
}

// Lambda
public void ExecuteLambda()
{
    var result =
        _complexList2.Count(
            l2 => _complexList1.All(l1 => l2.Number != l1.Number || l2.Character != l1.Character));
}

Using StopWatch to measure the time and running each loop type 10 times and taking the average execution time, the results were as follows:

For:10.163.836 ticks in avarage
Foreach:8.747.627 ticks in avarage
Lambda:14.326.094 ticks in avarage

The question is:
Are there other ways to solve my problem?
Does Lambda really spend more time than ordinary loops like foreach?

There doesn't appear to be a question here. If you are asking for the most performant method of accomplishing your goal.. well, you have the empirical data in front of you. — Sam Axe, Jun 21 '17 at 18:16
I don't understand the question. It looks like you've already done the benchmarking. — itsme86, Jun 21 '17 at 18:17
One thing that I noticed is that you're not using a seed value for your Random instance. This will result in different lists being created each time you run the test. So if you want comparable results you need to make sure to only call FillLists once and then use the result for all your different implementations. — dnickless, Jun 21 '17 at 18:20
Also, you are comparing apples and pears here since, for example, your lambda method does not populate a list whereas the other methods do. — dnickless, Jun 21 '17 at 18:21
Sorry, I forgot to specify my question. Question has been edited, thanks. — Isabella Riquetti, Jun 21 '17 at 18:26
@dnickless The list is being created only at the start of execution, and all methods use the same two lists. — Isabella Riquetti, Jun 21 '17 at 18:27
@dnickless meant populating the `result` list. The lambda test is just counting. — Ivan Stoev, Jun 21 '17 at 18:34
But all these tests doesn't really matter, since all tested algorithms have quadratic O(M * N) time complexity. Any correct hash based implementation will trim them down to linear O(M+N). — Ivan Stoev, Jun 21 '17 at 18:37

score 1 · Answer 1 · answered Jun 21 '17 at 18:23

1

You can try using the Except extension method which will return the list item difference of the two sequences:

List<ComplexObjects> _onlyInList1 = _complexList1.Except(_complexList2);

https://msdn.microsoft.com/en-us/library/bb300779(v=vs.110).aspx

answered Jun 21 '17 at 18:23

Canica

2,650
3
18
34

This form does not work, I tested the way you suggested and reversed, in both cases the list returned all records. I suppose she compares objects rather than values. – Isabella Riquetti Jun 21 '17 at 18:32
2

You may need to use the other version of the Except method and provide your own custom EqualityComparer as shown here: https://msdn.microsoft.com/en-us/library/bb336390(v=vs.110).aspx – Canica Jun 21 '17 at 18:44

igorc · Accepted Answer · 2017-06-21T21:44:05.867

1

Does Lambda really spend more time than ordinary loops like foreach?

Look here to see why this is usually the case.
And here to see some exception.

edited Jun 21 '17 at 21:44

answered Jun 21 '17 at 20:46

igorc

2,024
2
17
29

Best way to check values from a list that are not contained in another list. (Performance Testing)

2 Answers2