Самый быстрый способ сравнить два списка <>

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

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

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

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

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

Ответы на вопрос(11)

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

var difList = list1.Where(a => !list2.Any(a1 => a1.id == a.id))
            .Union(list2.Where(a => !list1.Any(a1 => a1.id == a.id)));
 spender09 окт. 2012 г., 10:46
Это страдает от ужасной производительности, требующей сканирования второго списка для каждого элемента в первом. Не понижение, потому что это работает, но этотак же плохо, как оригинальный код.
Решение Вопроса

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

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

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

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

return !firstNotSecond.Any() && !secondNotFirst.Any();
 Jon Skeet05 сент. 2017 г., 14:45
@ k2ibegin: он использует компаратор равенства по умолчанию, который будет использоватьIEquatable реализация илиobject.Equals(object) метод. Похоже, вы должны создать новый вопрос сминимальный воспроизводимый пример - мы можем'не реально диагностировать вещи в комментариях.
 Pranav Singh08 апр. 2016 г., 12:12
Я в УДАЧЕ, сущность того же типа в EF равны и Except работает.
 Halit D10 окт. 2018 г., 19:30
Это'не вопрос просто обратная связь. Я уже проголосовал.
 Halit D10 окт. 2018 г., 19:59
@JonSkeet It 'Для работы этого метода необходимо точно такой же объект. Мои объекты были экземпляром объекта. Я имею в виду, так же, как содержание.
 Pranav Singh08 апр. 2016 г., 11:42
Это работа для списка пользовательских типов данных или просто для списка для собственных типов данных, таких как string или int?
 Jon Skeet10 окт. 2018 г., 19:36
@HalitD: Но опять же, без каких-либо подробностей, обратная связь нет полезно. Это определенноделает работать в нормальных случаях, так что не знаяЗачем Это'Это не работает для вас, никто не может получить какую-либо информацию из комментария, IMO.
 Jon Skeet08 апр. 2016 г., 11:46
@PranavSingh: он будет работать для всего, что имеет соответствующее равенство - так что если ваш пользовательский тип переопределяетEquals(object) и / или реализуетIEquatable это должно быть хорошо.
 Jon Skeet10 окт. 2018 г., 19:19
@HalitD: без контекста мы можемэто действительно поможет. Я предлагаю вам задать новый вопрос сминимальный воспроизводимый пример, (Одна из распространенных проблем заключается в том, что ваши элементы списка нет уравновешенный ...)
 Pranav Singh08 апр. 2016 г., 11:48
Мой тип - это сущность из Entity Framework. Я неЯ думаю, что это реализуетIEquatableНе уверен насчет этого.
 Halit D10 окт. 2018 г., 19:17
Это'не работает на меня. Возвращает ложь в каждом условии.
 Jon Skeet10 окт. 2018 г., 20:17
@HalitD: нет, этоне нужно - объекты просто должны бытьравный в определениях равенства по умолчанию, т.е.Equals метод. Похоже, вы не перезаписалиEquals не реализованоIEquatable, в этом случае результат, как и ожидалось. Это в основном то, что я сказал в 17: 19: 29Z. Или вы могли бы пройти вIEqualityComparer конечно.
 Frank09 окт. 2012 г., 10:57
Это действительно огромный прирост производительности! Спасибо за этот ответ.
 Jon Skeet10 окт. 2012 г., 11:14
@ Ларри: Этоне отсортировано; он создает хэш-набор.
 Larry10 окт. 2012 г., 10:59
интересно два огромных списка, полезно ли сортировать перед сравнением? или внутри метода расширения, переданный список уже отсортирован.
 Jon Skeet08 апр. 2016 г., 11:54
@PranavSingh: Ну, вы должны взглянуть на это ... Я могуне скажу тебе, ябоюсь, но вы должны быть в состоянии решить это. Обратите внимание, что если выпытаемся сделать это наIQueryable, это может быть совсем по-другому, так как это зависит от того, какой SQL генерируется поставщиком EF.
 kuldeep05 сент. 2017 г., 14:43
@JonSkeet это действительно только для равенства ссылок? ИЛИ также для значений, которые содержат пользовательские типы в списке? Я предоставил пользовательские реализации equals и gethash для всех моих вложенных классов, сегментов в расписаниях внутри класса Items. Теперь, когда у меня есть список из двух элементов (утверждение с использованием Nunit), тест завершается неудачно, когда переопределенный метод equals внутри Item делает что-то вроде item1.ScheduleList1 == item2.ScheduleList2. Я пытался поставить это решение, но все равно утверждение не удалось!

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

var list3 = list1.Where(l => list2.ToList().Contains(l));
 Wai Ha Lee15 янв. 2019 г., 09:03
Это на самом деле очень плохо, потому что это создает новыйList для каждого элемента вlist1, Также результат называетсяlist3 когда это'не а.List

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

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

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

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

Enumerable.Except

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

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

var first10 = inListButNotInList2.Take(10);

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

 jwg20 янв. 2014 г., 15:35
@ Спендер, этоЭто как сказать, что казньWhere частично отложено, потому что вlist.Where(x => x.Id == 5) значение числа5 хранится в начале, а не выполняется лениво.
 spender09 окт. 2012 г., 10:44
Хм. Не совсем отложено. Я'скажу частично отложено. ПолныйSet построен из второй последовательности (т.е. это 'полностью итерированы и сохранены), затем получаются элементы, которые могут быть добавлены из первой последовательности.

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

public class EquatableList : List, IEquatable where    T : IEquatable

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

/// 
/// True, if list is equal to this
/// 
/// list
/// True, if instance equals list
public Boolean Equals(EquatableList list)
{
    if (list == null) return false;
    return this.All(list.Contains) && list.All(this.Contains);
}
 yuvalm208 февр. 2018 г., 17:06
Вы, вероятно, можете добиться большего успеха с сортируемыми типами. Это работает в O (n ^ 2), в то время как вы можете сделать O (nlogn).
 Pranav Singh08 апр. 2016 г., 11:45
Это то, что вам нужно, чтобы иметь возможность сравнивать пользовательские типы данных. Тогда используйтеExcept
 Kaitlyn06 сент. 2015 г., 15:53
Интересно, есть ли более простой способ сделать то, что он делает, но только с помощью функции ...
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;
        }
    }
}
</t></t></t></t>

если два списка разные, а не то, что эти различия. В этом случае рассмотрите возможность добавления этого метода расширения в ваш проект. Обратите внимание, что ваши перечисленные объекты должны реализовывать 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>

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

Это'очень важно отметить, как мыя написал GetHashCode. Для того, чтобы правильно реализовать,IEquatableEquals а такжеGetHashCode должен оперируйs свойства логически совместимым способом.

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

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

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

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

    //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;
    }
</string></string></string></string></string>

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

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

 SwissCoder22 февр. 2018 г., 14:02
@ user1027167: Я не говорю о прямом сравнении строк (так как это тоже не вопрос). Вызов метода .ToString () для всех объектов в Списке с 50 000 объектов может создать огромную строку, в зависимости от того, какреализовано. Я нене думаю, чтоЭто путь. Затем это'также рискованно полагаться на символ или строку "уникальный»код на самом деле не может быть так многократно использован.
 user102716722 февр. 2018 г., 13:30
@SwissCoder: Вы не правы, это не убийца производительности для строки. Если у вас есть два списка с 50.000 строк (каждая длиной 3), этот алгоритм требует 3 мс на моей машине. Принято отвечать на запросы 7. Я думаю, уловка в том, что Джибзу нужно только одно сравнение строк. Конечно, он должен добавить уникальный разделитель.
 user102716722 февр. 2018 г., 14:47
Хорошо, что 'это правда. Спрашивающий попросил самый быстрый способ, не указав тип данных в своих списках. Вероятно, этот ответ - самый быстрый способ использования вопроса.
 SwissCoder05 окт. 2017 г., 14:29
как это's написано здесь, это не будет работать даже для List <строка> или список <Int>как, например, два списка 11; 2; 3 и 1; 12; 3 будут идентичны, так как вы нет соединить строки с некоторым уникальным разделителем, который неt возможный пункт в списке. Кроме того, объединение строк для списка с большим количеством элементов, вероятно, снижает производительность.

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

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

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

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)
 Wai Ha Lee15 янв. 2019 г., 12:49
Возможно, вы могли бы удалить этот ответ и переместить его (например)Как я могу сравнить два списка в Python и вернуть совпадения?
 Wai Ha Lee15 янв. 2019 г., 09:01
Это вопрос C #, и вы не предоставили код C #.
 user1091570715 янв. 2019 г., 12:04
Окей, ты прав. Это полезно в питоне.

Ваш ответ на вопрос