C # более эффективный способ сравнения двух коллекций

Question

У меня есть две коллекции

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

Я не хочу использовать цикл foreach или что-то еще, потому что я думаю, что должен быть намного лучший способ сделать это.

Я ищуболее эффективный способ сравнить эти коллекции и получить результаты:

1. Список автомобилей, которые находятся в новых автомобилях, а не в текущих автомобилях
2. Список автомобилей, которых нет в новых автомобилях и в текущих автомобилях

Тип Car имеет свойство int. Идентификатор.

Был ответ, который уже удален, говоря, что я имею в виду, говоря «эффективный»: меньше кода, меньше механики и больше читаемых случаев

Итак, если подумать, какие у меня кейсы?

Что будет меньше кода, меньше механики и больше читаемых кейсов?

Answer 1

Вы можете сделать это следующим образом:

// 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);

В коде используется метод расширения Enumerable.Except (доступен в .Net 3.5 и более поздних версиях).

Я считаю, что это соответствует вашим критериям «меньше кода, меньше механики и больше читаемости».

Answer 2

Вы можете использовать Except:

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

Но это не дает преимущества в производительности по сравнению с решением foreach.Это выглядит просто чище.
Кроме того, помните о том, что вам нужно реализовать IEquatable<T> для вашего Car класса, поэтому сравнение выполняется по идентификатору, а не по ссылке.

Performancewise, лучший подход был бы не использовать List<T>, а Dictionary<TKey, TValue> с идентификатором в качестве ключа:

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 3

Если вы начинаете с них через HashSet s, вы можете использовать метод Except.

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

currentCars.Except(newCars);
newCars.Except(currentCars);

Это было бы намного быстрее с сетом, чем со списком. (Под капотом список просто делает foreach, наборы можно оптимизировать).

Answer 4

Вы можете использовать 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();

... но не обманывайте себя.Это может быть меньше кода для вас, но определенно там будет несколько циклов for где-то

РЕДАКТИРОВАТЬ: Не понял, что существует метод Except: (*

Answer 5

Я бы переопределил Equals из Car для сравнения по id, и тогда вы могли бы использовать метод расширения IEnumerable.Except. Если вы не можете переопределить Equals, вы можете создать свой собственный IEqualityComparer<Car>, который сравнивает две машины по идентификатору.

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 6

Если вы ищете эффективность, внедрите IComparable on Cars (сортировка по вашему уникальному идентификатору) и используйте SortedList. Затем вы можете вместе просмотреть свои коллекции и оценить свои чеки в O (n). Это, конечно, связано с дополнительными затратами на вставки List для поддержания отсортированного характера.

Answer 7

Если вам достаточно сравнения свойства Id, чтобы сказать, равен ли Car другому, чтобы избежать какого-либо цикла, вы можете переопределить List своим собственным классом, который отслеживает элементы и используетIEqualityComparer для всей коллекции, например:

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 ....
}

Затем вам просто нужно переопределить Add, Remove и т. Д. И любые другие методы, которые могут повлиять на элементы в списке.Затем вы можете сохранить приватную переменную, которая является хэшем некоторого рода идентификаторов элементов в списке.При переопределении ваших Equals методов вы можете просто сравнить эту приватную переменную.На сегодняшний день это не самый чистый подход (так как вы должны идти в ногу со своей хеш-переменной), но это приведет к тому, что вам не придется переходить по циклам для сравнения.Если бы это был я, я бы просто использовал Linq, как некоторые упоминали здесь ...

Answer 8

Вы можете скопировать меньший список в коллекцию на основе хеш-таблицы, например HashSet или Dictionary, а затем выполнить итерацию по второму списку и проверить, существует ли элемент в хеш-таблице.

это сократит время от O (N ^ 2) в наивном foreach внутри случая foreach до O (N).

Это лучшее, что вы можете сделать, не зная больше о списках (вы можете сделать немного лучше, если списки отсортированы, например, но, так как вам нужно "дотронуться" до каждого автомобиль хотя бы один раз, чтобы проверить, есть ли в новом списке автомобилей, вы никогда не сможете сделать лучше, чем O (N))