Find items in one list that aren't in another list

Question

I have 2 list of objects and I want to get all the objects from the first where string a doesn't match string a in the 2nd list.

public class ObjectA  
{  
    string Item;  
    int b;  
}

public class ObjectB  
{  
    string Item;  
    int b;  
}

This can easily be done with linq this way but what is a faster way to do this?

var newList = objectAList.Where(a => !objectBList.Any(b => b.Item == a.Item)).ToList()

What's the size of your lists ? An alternative it would be to use two nested for statements. But saying that this would be faster doesn't say much. You should do some benchmark. The behavior for lists of small size might be negligible. For medium size or large might not. What is small ? What is large ? Using all these questions I am trying to convince you that this hasn't any meaning, if you don't find another way to solve the same problem and then perform a benchmark. — Christos, Sep 05 '19 at 17:59
You're looking for a faster way, a non-LINQ way, or a non-LINQ way that is also faster? Do you have any thoughts or attempts on solving this? — Lance U. Matthews, Sep 05 '19 at 18:01
@Christos Nested for statements is O(n*m). Linq's Except is significantly better. — Eric J., Sep 05 '19 at 18:18
@EricJ. I agree. My is was that trying to answer which is faster, when you have only one solution does not make sense. Even having two solutions, if you don't run any benchmark, any guessing might be meaningless. — Christos, Sep 05 '19 at 18:28
With the "without LINQ" condition removed, possible duplicate of [Most efficient way to compare two lists and delete the same](https://stackoverflow.com/questions/35265926/most-efficient-way-to-compare-two-lists-and-delete-the-same). Not all that different from [Find if listA contains any elements not in listB](https://stackoverflow.com/q/9524681/150605), [Use LINQ to get items in one List<>, that are not in another List<>](https://stackoverflow.com/q/3944803/150605), or [Difference between two lists](https://stackoverflow.com/q/5636438/150605). — Lance U. Matthews, Sep 05 '19 at 19:04

MrRobboto · Answer 1 · 2019-09-06T15:43:59.530

1

What about this - no linq, still nice and fluent, edited for the right types:

ObjectBList.RemoveAll(p => ObjectAList.Find(p2 => p2.Item == p.Item) != null ? true : false);

Full Example:

public class ObjectBase {
    public string Item;
    public int b;
}

public class ObjectA : ObjectBase{ }

public class ObjectB : ObjectBase { }

public List<ObjectB> Testing() {
    var list1 = new List<ObjectA> { new ObjectA { Item = "str1", b = 0 } };
    var list2 = new List<ObjectB> { new ObjectB { Item = "str1", b = 0 }, new ObjectB { Item = "str2", b = 1 } };

    // Key Line - Remove all from list2 found in list1
    list2.RemoveAll(p => list1.Find(p2 => p2.Item == p.Item) != null ? true : false);

    return list2;
}

edited Sep 06 '19 at 15:43

answered Sep 05 '19 at 18:11

MrRobboto

722
3
10

This doesn't act on objects that the OP has in his question. – Eric J. Sep 05 '19 at 18:46
Yeah, you'd have to use the IEqualityComparer with Contains to have this work on a Reference type and checking just one property for comparison. It wouldn't be much different though - RemoveAll() and Contains() is the key to avoid Linq in this scenario. I'll update my answer as soon as I can... – MrRobboto Sep 06 '19 at 14:41
Edited and I did have to change it. Easier to just use .Find() instead of Contains with the Comparer and all that. – MrRobboto Sep 06 '19 at 15:33

Eric J. · Answer 2 · 2019-09-05T18:20:29.870

The Linq Except method is designed for this purpose and is very fast. However, you have a wrinkle that your two classes have compatible fields but are different objects. Here's one way to handle it:

class ObjectBase
{
    public string Item;
    public int b;
}

class ObjectA : ObjectBase
{

}

class ObjectB : ObjectBase
{

}

class ObjectComparer : IEqualityComparer<ObjectBase>
{
    public bool Equals(ObjectBase a, ObjectBase b)
    {
        return a?.Item == b?.Item; 
    }
    public int GetHashCode(ObjectBase o)
    {
        return o.?Item?.GetHashCode() ?? 0;
    }
}

// Very fast compared to your current approach. 1000x for my test case.

var newList = objectAList.Except(objectBList, new ObjectComparer()).ToList();

Michał Turczyn · Answer 3 · 2019-09-05T18:15:53.883

You can try this code:

public static void Main(string[] args)
{
  List<ObjectA> listA = new List<ObjectA>()
  {
    new ObjectA(){Item = "abc" },
    new ObjectA(){Item = "ab" },
  };
  List<ObjectB> listB = new List<ObjectB>()
  {
    new ObjectB(){Item = "abc" },
  };
  // loop backwards removing entry if it is found in the other list
  for (int i = listA.Count - 1; i >= 0; i--)
    if (listB.Find(e => e.Item == listA[i].Item) != null)
      listA.RemoveAt(i);
}

I run both (yours and mine) methods five times and got following results (everytime repeating algorithm in a loop, 100000 iterations) in milliseconds:

my method: 107 46 94 67 91

your method: 108 267 171 138 173

It also might be due to extra ToList() call and creating new object newList.

So, to sum up, if there is any improvement, it is very little and I wouldn't sacrifice readability provided by wonderful LINQ methods for that.

Also, internally they were designed to work as fast as possible, so I would rely on them :)

RemoveAt is fairly slow because it's an O(N) operation and you must do it M times (where M is the number of intersecting elements to be removed), so the overall algorithm is O(N*M). — Eric J., Sep 05 '19 at 18:48

score 0 · Answer 4 · answered Sep 05 '19 at 18:07

0

The faster way to do this would be:

var newList = objectAList.Select(a => a.Item).Except(objectBList.Select(b => b.Item));

Yes, I know it is Linq but you asked for a faster way :)

HTH

answered Sep 05 '19 at 18:07

Canica

2,650
3
18
34

Except is the way to go, but this only gives you the Items, not the actual objects. – Eric J. Sep 05 '19 at 18:10

score 0 · Answer 5 · answered Sep 05 '19 at 18:59

The fastest way time wise is to use HashSet<>, especially for large lists:

    private List<ObjectA> Find(List<ObjectA> list1, List<ObjectB> list2)
    {
        var list2HashSet = list2.Select(x => x.Item).ToHashSet();
        return list1.Where(x => !list2HashSet.Contains(x.Item)).ToList();
    }

Note: and don't forget to make property Item public or it will not work!

Find items in one list that aren't in another list

5 Answers5