List Contains

Question

What's the fastest way (coding wise) to check if one entry exist on a list? MyObject has 2 properties

public class Name
{
    public string FirstName{ get; set; }
    public string LastName { get; set; }
}

then I have another class like this:

public class Foo
{ 
   private  List<Name> Names : new List<Name>();
   public List<Name> Names { get; set; }

   public bool Contains(Name x)
   {
      if (x == null)
         return false;

      >>> Navigate || Equals || Linq.Contains
      >>> What's the easiest way to do this?
   }
}

By fastest way, you mean least CPU usage or easiest to understand code? — Patashu, Apr 30 '13 at 03:16
I guess it would be `.Any` [For](http://stackoverflow.com/questions/4445219/linq-ring-any-vs-contains-for-huge-collections) [details](http://stackoverflow.com/questions/305092/which-method-performs-better-any-vs-count-0) — V4Vendetta, Apr 30 '13 at 03:17

Steven Wexler · Accepted Answer · 2013-04-30T03:40:06.743

Fastest for List are O(n) lookup speed and O(1) insert speed:

Atleast One

Names.Any(n=> x.FirstName == n.FirstName && x.LastName == n.LastName)

Exactly One:

Names.Count(n=> x.FirstName == n.FirstName && x.LastName == n.LastName) == 1

Any() is faster because it short circuits when it finds the first instance of Name. Count searches through the list everytime to find all instances of Name.

Instead, you could use a Collection (e.g. HashSet, Dictionary, etc) where lookup operations are O(1). However, collections don't hold the same properties as Lists. Note, Hashset<string> where names are stored as something like FirstName + (delimeter) + LastName is faster than any other option you have.

You could also use a SortedList where lookup speeds are O(log(n)). However, inserting elements in a sorted list is O(nlog(n)) because you must keep the list sorted after every insertion.

score 1 · Answer 2 · answered Apr 30 '13 at 03:20

1

I would say linq .Any is pretty easy http://msdn.microsoft.com/en-us/library/system.linq.enumerable.any.aspx

Names.Any(n=> n==x)

answered Apr 30 '13 at 03:20

Jras

518
3
12

jacob aloysious · Answer 3 · 2013-04-30T03:30:24.060

Using Linq should be easier to read. Here is sample using Any.

    public bool Contains(Name x)
    {
        if (x == null)
            return false;

        return this.Names.Any(item => item.FirstName == x.FirstName && item.LastName == x.LastName);
    }

Suggestion: If the items in your list are supposed to be unique then you could use System.Collections.Generic.HashSet and use System.Linq.Enumerable.Contains..

score 1 · Answer 4 · answered Apr 30 '13 at 04:53

You might want to compare for the performance with the methods Contains and Any of the following code:

partial class Foo {
    class NameComparer: IComparer<Name> {
        public int Compare(Name x, Name y) {
            return
                object.ReferenceEquals(x, y)
                ||y.LastName==x.LastName&&y.FirstName==x.FirstName?0:~0;
        }

        public static readonly NameComparer Default=new NameComparer();
    }

    public bool Any(Name x) {
        return
            Names.Any(
                y => object.ReferenceEquals(x, y)
                ||y.LastName==x.LastName&&y.FirstName==x.FirstName);
    }

    public bool Contains(Name x) {
        return Names.BinarySearch(x, NameComparer.Default)>~0;
    }
}

My testing reports about 25%~30% faster with `BinarySearch`. — Ken Kin, Apr 30 '13 at 04:57

List Contains

4 Answers4