Using LINQ to select a list of every item in a collection, except if it exists in another collection

Question

This works, but not only looks bad, but doesn't seem terribly efficient (I have not evaluated performance yet since I know there must be a better way to do this).

public IEnumerable<Observation> AvailableObservations
{
    get 
    {
        foreach (var observation in db.Observations)
        {
            if (Observations.Any(x => x.Id == observation.Id))
            {

            }
            else
            {
                yield return observation;
            }
        }
    }
}

Essentially, I want everything in the list db.Observations (which pulled from db via EF6) and remove all the entries currently selected in this.Observations, which is an ICollection<Observations>

I've tried using .Except(this.Observations) but get an error that I believe might be related to using except with an ICollection on an entity that is an IEnumerable.

Anything that will remove the foreach loop would be a good start.

Answer 1

Well your loop is equivalent to:

return db.Observations.Where(o => !Observations.Any(oo => oo.Id == o.Id));

but that's no more efficient that what you have.

A more efficient method would be to create a HashSet of IDs and filter off of that:

HashSet<int> ids = new HashSet<int>(Observations.Select(o => o.Id));
return db.Observations.Where(o => !ids.Contains(o.Id));

That way you're only traversing the main list once in order to create a HashSet that can be searched in O(1) time.

Answer 2

You can do two optimizations here:

1. Limit the number of observations you fetch from the database
2. Make the lookup of the selected observation IDs quicker

The current implementation has a O(N * M) complexity, where N is the number of items in db.Observations and M is the number of items in this.Observations.

What would help performance would be to first create a HashSet of the IDs in this.Observations:

var observationIds = new HashSet<int>(this.Observations.Select(x => x.Id));

This will allow you to do quick lookups on the IDs.

Combine this with a where clause (using LINQ's Where()) to get an efficient query:

public IEnumerable<Observation> AvailableObservations
{
    get 
    {
        var observationIds = new HashSet<int>(this.Observations.Select(x => x.Id));
        return db.Observations.Where(x => !observationIds.Contains(x.Id));
    }
}