C # a more efficient way to compare two collections

Question

I have two collections

List<Car> currentCars = GetCurrentCars(); List<Car> newCars = GetNewCars(); 

I don't want to use a foreach loop or anything else because I think there should be a much better way to do this.

I am looking for a more efficient way to compare these collections and get results:

• List of cars that are in newCars and not in CurrentCars
• List of cars that are not in the new ticket offices and in current maps

Car type has int id property.

There was an answer that was already deleted saying What do I mean by saying "effective": less code, less mechanics, and more readable cases.

So think so, what are my cases?

The less code, the less mechanics and more readable cases?

Answer 1

You can use Except :

 var currentCarsNotInNewCars = currentCars.Except(newCars); var newCarsNotInCurrentCars = newCars.Except(currentCars); 

But this solution has no advantages over the foreach solution. It just looks cleaner. Also keep in mind that you need to implement IEquatable<T> for your Car class, so the comparison is done by identifier, not by reference.

In the best case, it is better not to use List<T> , but Dictionary<TKey, TValue> with identifier as key:

 var currentCarsDictionary = currentCars.ToDictionary(x => x.ID); var newCarsDictionary = newCars.ToDictionary(x => x.ID); var currentCarsNotInNewCars = currentCarsDictionary.Where(x => !newCarsDictionary.ContainsKey(x.Key)) .Select(x => x.Value); var newCarsNotInCurrentCars = newCarsDictionary.Where(x => !currentCarsDictionary.ContainsKey(x.Key)) .Select(x => x.Value); 

Answer 2

You can do it as follows:

 // 1) List of cars in newCars and not in currentCars var newButNotCurrentCars = newCars.Except(currentCars); // 2) List of cars in currentCars and not in newCars var currentButNotNewCars = currentCars.Except(newCars); 

The code uses the Enumerable.Except extension method (available in .Net 3.5 and later).

I believe this meets your criteria of "less code, less mechanics, and more readability."

Answer 3

If you start with them in a HashSet , you can use the Except method.

 HashSet<Car> currentCars = GetCurrentCars(); HashSet<Car> newCars = GetNewCars(); currentCars.Except(newCars); newCars.Except(currentCars); 

It will be much faster than a set than a list. (Under the hood, the list just does foreach, sets can be optimized).

Answer 4

I would override Equals for Car to compare by id, and then you could use the IEnumerable.Except extension method. If you cannot override Equals , you can create your own IEqualityComparer<Car> , which compares two machines by id.

 class CarComparer : IEqualityComparer<Car> { public bool Equals(Car x, Car y) { return x != null && y != null && x.Id == y.Id; } public int GetHashCode(Car obj) { return obj == null ? 0 : obj.Id; } } 

Answer 5

You can use LINQ ...

  List<Car> currentCars = new List<Car>(); List<Car> newCars = new List<Car>(); List<Car> currentButNotNew = currentCars.Where(c => !newCars.Contains(c)).ToList(); List<Car> newButNotCurrent = newCars.Where(c => !currentCars.Contains(c)).ToList(); 

... but don't be fooled. It may be less code for you, but there will definitely be some loops somewhere out there.

EDIT: Didn't understand that Except method exists :(

Answer 6

If you are looking for efficiency, implement IComparable on cars (sorting by your unique identifier) ​​and use SortedList. You can then go through your collections and evaluate your checks in O (n). This, of course, is associated with additional costs for inserting lists to maintain an orderly nature.

Answer 7

You can copy the smaller list into a collection based on a hash table, such as a HashSet or Dictionary, and then iterate over the second list and check if an item exists in the hash table.

this will reduce the time from O (N ^ 2) in the naive foreach inside each case to O (N).

This is the best thing you can do without knowing more about the lists (you can do a little better if the lists are sorted, for example, but since you need to “touch” each car at least once to check if you are in the list of new cars you can never do better than O (N))

Answer 8

If you compare the Id property enough to say that the car is equal to another in order to avoid any kind of loop, you can redefine the list with your class that keeps track of the elements and uses IEqualityComparer for the entire collection, for example:

 class CarComparer : IList<Car>, IEquatable<CarComparer> { public bool Equals(CarComparer other) { return object.Equals(GetHashCode(),other.GetHashCode()); } public override int GetHashCode() { return _runningHash; } public void Insert(int index, Car item) { // Update _runningHash here throw new NotImplementedException(); } public void RemoveAt(int index) { // Update _runningHash here throw new NotImplementedException(); } // More IList<Car> Overrides .... } 

Then you just need to override Add , Remove , etc. and any other methods that may affect the items in the list. Then you can save a private variable, which is a hash of some identifier of the elements in the list. When overriding Equals methods, you can simply compare this private variable. Not the cleanest approach to date (since you need to keep up with your hash variable), but this will result in you not having to iterate over loops for comparison. If it were me, I would just use Linq, as some mentioned here ...