Самый быстрый способ сравнить два общих списка для различий

214

Что является самым быстрым (и наименее ресурсоемким) для сравнения двух массивных (> 50 000 элементов) и в результате получается два списка, подобных приведенному ниже:

  1. элементы, которые отображаются в первом списке, но не во втором
  2. элементы, которые отображаются во втором списке, но не в первом

В настоящее время я работаю с List или IReadOnlyCollection и решаю эту проблему в запросе linq:

var list1 = list.Where(i => !list2.Contains(i)).ToList();
var list2 = list2.Where(i => !list.Contains(i)).ToList();

Но это не так хорошо, как хотелось бы. Любая идея сделать это быстрее и менее ресурсоемким, поскольку мне нужно обрабатывать много списков?

Фрэнк
источник

Ответы:

454

Используйте Except:

var firstNotSecond = list1.Except(list2).ToList();
var secondNotFirst = list2.Except(list1).ToList();

Я подозреваю, что есть подходы, которые на самом деле были бы немного быстрее, чем этот, но даже это будет значительно быстрее, чем ваш подход O (N * M).

Если вы хотите объединить их, вы можете создать метод с приведенным выше, а затем оператор return:

return !firstNotSecond.Any() && !secondNotFirst.Any();

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

Например, со списками [1, 2, 2, 2, 3]и [1]результат «элементы в списке 1 , но не в списке 2 » в исходном коде будет [2, 2, 2, 3]. С моим кодом это было бы просто так [2, 3]. Во многих случаях это не будет проблемой, но об этом стоит знать.

Джон Скит
источник
8
Это действительно огромный прирост производительности! Спасибо за этот ответ.
Фрэнк
2
Мне интересно два огромных списка, полезно ли сортировать перед сравнением? или внутри метода расширения, переданный список уже отсортирован.
Ларри
9
@Larry: это не отсортировано; он создает хэш-набор.
Джон Скит
2
@PranavSingh: Он будет работать для всего, что имеет соответствующее равенство - поэтому, если ваш пользовательский тип переопределяет Equals(object)и / или реализует, IEquatable<T>это должно быть хорошо.
Джон Скит
2
@ k2ibegin: он использует компаратор равенства по умолчанию, который будет использовать IEquatable<T>реализацию или object.Equals(object)метод. Похоже, вы должны создать новый вопрос с минимальным воспроизводимым примером - мы не можем диагностировать вещи в комментариях.
Джон Скит,
40

Более эффективным было бы использовать Enumerable.Except:

var inListButNotInList2 = list.Except(list2);
var inList2ButNotInList = list2.Except(list);

Этот метод реализован с использованием отложенного выполнения. Это означает, что вы могли бы написать, например:

var first10 = inListButNotInList2.Take(10);

Это также эффективно, так как он внутренне использует Set<T>для сравнения объектов. Он работает, сначала собирая все отдельные значения из второй последовательности, а затем выводит результаты первой, проверяя, что они не были видны ранее.

Тим Шмельтер
источник
1
Хм. Не совсем отложено. Я бы сказал, частично отложенный. Complete создается Set<T>из второй последовательности (то есть полностью повторяется и сохраняется), затем получаются элементы, которые можно добавить из первой последовательности.
спонсор
2
@spender, это все равно что сказать, что выполнение Whereчастично отложено, потому что в list.Where(x => x.Id == 5)значении число 5хранится в начале, а не выполняется лениво.
JWG
27

Метод Enumerable.SequenceEqual

Определяет, равны ли две последовательности согласно средству сравнения на равенство. MS.Docs

Enumerable.SequenceEqual(list1, list2);

Это работает для всех примитивных типов данных. Если вам нужно использовать его на пользовательских объектах, вы должны реализоватьIEqualityComparer

Определяет методы для поддержки сравнения объектов на равенство.

Интерфейс IEqualityComparer

Определяет методы для поддержки сравнения объектов на равенство. MS.Docs для IEqualityComparer

miguelmpn
источник
это должен быть принятый ответ. Речь идет не о SETS, а о СПИСКАХ, которые могут содержать дублирование элементов.
Адриан
3
Я не понимаю, как это может быть ответом, учитывая, что результат SequenceEqualпрост bool. ОП хочет два списка результатов - и описывает, что они хотят в терминах операций над множествами: «элементы, которые отображаются в первом списке, но не во втором». Там нет никаких признаков того, что порядок имеет значение, в то время как SequenceEqual действительно считают ее актуальной. Похоже, это отвечает на совершенно другой вопрос.
Джон Скит
да, верно, кажется, что я ответил на этот вопрос слишком быстро и не посмотрел на вторую часть запроса ... так же, как первые два комментария ...
miguelmpn
9

Если вы хотите, чтобы результаты не учитывали регистр , сработает следующее:

List<string> list1 = new List<string> { "a.dll", "b1.dll" };
List<string> list2 = new List<string> { "A.dll", "b2.dll" };

var firstNotSecond = list1.Except(list2, StringComparer.OrdinalIgnoreCase).ToList();
var secondNotFirst = list2.Except(list1, StringComparer.OrdinalIgnoreCase).ToList();

firstNotSecondбудет содержать b1.dll

secondNotFirstбудет содержать b2.dll

e.gad
источник
5

Не для этой проблемы, но вот код для сравнения списков на равные и нет! идентичные объекты:

public class EquatableList<T> : List<T>, IEquatable<EquatableList<T>> where    T : IEquatable<T>

/// <summary>
/// True, if this contains element with equal property-values
/// </summary>
/// <param name="element">element of Type T</param>
/// <returns>True, if this contains element</returns>
public new Boolean Contains(T element)
{
    return this.Any(t => t.Equals(element));
}

/// <summary>
/// True, if list is equal to this
/// </summary>
/// <param name="list">list</param>
/// <returns>True, if instance equals list</returns>
public Boolean Equals(EquatableList<T> list)
{
    if (list == null) return false;
    return this.All(list.Contains) && list.All(this.Contains);
}
Пий Отшельник
источник
1
Это то, что вам нужно, чтобы иметь возможность сравнивать пользовательские типы данных. Тогда используйтеExcept
Пранав Сингх
Вы, вероятно, можете добиться большего успеха с сортируемыми типами. Это работает в O (n ^ 2), в то время как вы можете сделать O (nlogn).
yuvalm2
3

попробуйте так:

var difList = list1.Where(a => !list2.Any(a1 => a1.id == a.id))
            .Union(list2.Where(a => !list1.Any(a1 => a1.id == a.id)));
Али Исса
источник
13
Это страдает от ужасной производительности, требующей сканирования второго списка для каждого элемента в первом. Не понижение, потому что это работает, но это так же плохо, как оригинальный код.
спонсор
3
using System.Collections.Generic;
using System.Linq;

namespace YourProject.Extensions
{
    public static class ListExtensions
    {
        public static bool SetwiseEquivalentTo<T>(this List<T> list, List<T> other)
            where T: IEquatable<T>
        {
            if (list.Except(other).Any())
                return false;
            if (other.Except(list).Any())
                return false;
            return true;
        }
    }
}

Иногда вам нужно знать , отличаются ли два списка, а не каковы эти различия. В этом случае рассмотрите возможность добавления этого метода расширения в ваш проект. Обратите внимание, что ваши перечисленные объекты должны реализовывать IEquatable!

Использование:

public sealed class Car : IEquatable<Car>
{
    public Price Price { get; }
    public List<Component> Components { get; }

    ...
    public override bool Equals(object obj)
        => obj is Car other && Equals(other);

    public bool Equals(Car other)
        => Price == other.Price
            && Components.SetwiseEquivalentTo(other.Components);

    public override int GetHashCode()
        => Components.Aggregate(
            Price.GetHashCode(),
            (code, next) => code ^ next.GetHashCode()); // Bitwise XOR
}

Каким бы ни был Componentкласс, методы, показанные здесь, Carдолжны быть реализованы почти одинаково.

Очень важно отметить, как мы написали GetHashCode. Для того , чтобы правильно реализовать IEquatable, Equalsи GetHashCode должны работать на свойства экземпляра в логически совместимым способом.

Два списка с одинаковым содержимым по-прежнему являются разными объектами и будут создавать разные хэш-коды. Поскольку мы хотим, чтобы эти два списка рассматривались как равные, мы должны позволить GetHashCodeсоздать одинаковое значение для каждого из них. Мы можем сделать это путем делегирования хэш-кода каждому элементу в списке и использования стандартного побитового XOR для их объединения. XOR не зависит от порядка, поэтому не имеет значения, сортируются ли списки по-разному. Имеет значение только то, что они содержат только эквивалентные члены.

Примечание: странное имя подразумевает тот факт, что метод не учитывает порядок элементов в списке. Если вы заботитесь о порядке элементов в списке, этот метод не для вас!

Девон Парсонс
источник
1

Я использовал этот код, чтобы сравнить два списка, который имеет миллион записей.

Этот метод не займет много времени

    //Method to compare two list of string
    private List<string> Contains(List<string> list1, List<string> list2)
    {
        List<string> result = new List<string>();

        result.AddRange(list1.Except(list2, StringComparer.OrdinalIgnoreCase));
        result.AddRange(list2.Except(list1, StringComparer.OrdinalIgnoreCase));

        return result;
    }
Sathish
источник
0

Если нужен только комбинированный результат, это тоже будет работать:

var set1 = new HashSet<T>(list1);
var set2 = new HashSet<T>(list2);
var areEqual = set1.SetEquals(set2);

где T - тип элемента списков.

Али Халеги Карсалари
источник
-1

Может быть, это смешно, но у меня работает

string.Join ("", List1)! = string.Join ("", List2)

Jibz
источник
как написано здесь, это не будет работать даже для List <string> или List <int>, как, например, два списка 11; 2; 3 и 1; 12; 3 будут идентичны, так как вы не объединяете строки с некоторыми уникальный разделитель, который не является возможным элементом в списке. Кроме того, объединение строк для списка с большим количеством элементов, вероятно, снижает производительность.
SwissCoder
@ SwissCoder: Вы не правы, это не убийца производительности для строки. Если у вас есть два списка с 50.000 строк (каждая длиной 3), этот алгоритм требует 3 мс на моей машине. Принято отвечать на запросы 7. Я думаю, дело в том, что Джибзу нужно только одно сравнение строк. Конечно, он должен добавить уникальный разделитель.
user1027167
@ user1027167: Я не говорю о прямом сравнении строк (так как это тоже не вопрос). Вызов метода .ToString () для всех объектов в Списке с 50 000 объектов может создать огромную строку, в зависимости от того, как она реализована. Я не думаю, что это путь. Кроме того, рискованно полагаться на то, что символ или строка являются «уникальными», код на самом деле не может быть повторно использован таким образом.
SwissCoder
Хорошо, это правда. Спрашивающий попросил самый быстрый способ, не указав тип данных в своих списках. Вероятно, этот ответ - самый быстрый способ использования вопроса.
user1027167
-3

Я думаю, что это простой и легкий способ сравнить два списка элемент за элементом

x=[1,2,3,5,4,8,7,11,12,45,96,25]
y=[2,4,5,6,8,7,88,9,6,55,44,23]

tmp = []


for i in range(len(x)) and range(len(y)):
    if x[i]>y[i]:
        tmp.append(1)
    else:
        tmp.append(0)
print(tmp)
user10915707
источник
3
Это вопрос C #, и вы не предоставили код C #.
Вай Ха Ли
1
Возможно, вы могли бы удалить этот ответ и переместить его (например) Как я могу сравнить два списка в python и вернуть совпадения ?
Вай Ха Ли
-4

Это лучшее решение, которое вы нашли

var list3 = list1.Where(l => list2.ToList().Contains(l));
Фахуи Эль Махди
источник
1
Это на самом деле очень плохо, потому что создает новый List<T>для каждого элемента в list1. Также результат вызывается, list3когда он не является List<T>.
Вай Ха Ли