Najszybszy sposób na porównanie dwóch ogólnych list różnic

Jaka jest najszybsza (i najmniej zasobochłonna) do porównania dwóch masywnych (>50.000 pozycji) i w rezultacie mają dwie listy, takie jak te poniżej:

  1. pozycje, które pojawiają się na pierwszej liście, ale nie na drugiej
  2. pozycje, które pojawiają się na drugiej liście, ale nie na pierwszej

Obecnie pracuję z listą lub IReadOnlyCollection i rozwiązuję ten problem w zapytaniu linq:

var list1 = list.Where(i => !list2.Contains(i)).ToList();
var list2 = list2.Where(i => !list.Contains(i)).ToList();
Ale to nie działa tak dobrze, jak bym chciał. Dowolne pomysł uczynienia tego szybszym i mniej wymagającym zasobów, ponieważ muszę przetwarzać wiele list?
 242
Author: Robert Harvey, 2012-10-09

12 answers

Użycie Except:

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

Podejrzewam, że istnieją podejścia, które faktycznie byłyby nieznacznie szybsze niż to, ale nawet to będzie znacznie szybsze niż Twoje podejście O(N * m).

Jeśli chcesz je połączyć, możesz utworzyć metodę z powyższą, a następnie instrukcją return:

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

Należy zauważyć, że istnieje jest różnica w wynikach między oryginalnym kodem w pytaniu a rozwiązaniem tutaj: dowolne zduplikowane elementy które są tylko na jednej liście będą zgłaszane tylko raz z moim kodem, podczas gdy będą zgłaszane tyle razy, ile występują w oryginalnym kodzie.

Na przykład, w przypadku list [1, 2, 2, 2, 3] i [1]," elementy w list1, ale nie list2 " powodują, że oryginalny kod będzie [2, 2, 2, 3]. Z moim kodem będzie to po prostu [2, 3]. W wielu przypadkach nie będzie to problemem, ale warto o tym wiedzieć.

 492
Author: Jon Skeet,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2019-09-05 09:55:21

/ align = "left" / Metoda Sekwencyjna

Określa, czy dwie sekwencje są równe zgodnie z porównaniem równości. ms. Docs

Enumerable.SequenceEqual(list1, list2);

To działa dla wszystkich prymitywnych typów danych. Jeśli chcesz używać go na obiektach niestandardowych, musisz zaimplementować IEqualityComparer

Definiuje metody wspierające porównywanie obiektów dla równości.

Ieequalitycomparer Interface

Definiuje metody wspierające porównanie obiektów dla równości. MS. Docs for Ieequalitycomparer

 47
Author: miguelmpn,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2020-06-20 09:12:55

Bardziej efektywne byłoby użycie Enumerable.Except:

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

Ta metoda jest zaimplementowana przy użyciu odroczonego wykonania. Oznacza to, że możesz napisać na przykład:

var first10 = inListButNotInList2.Take(10);

Jest również wydajny, ponieważ wewnętrznie używa Set<T> do porównywania obiektów. Działa on najpierw zbierając wszystkie różne wartości z drugiej sekwencji, a następnie przesyłając strumieniowo wyniki pierwszej, sprawdzając, czy nie były wcześniej widziane.

 40
Author: Tim Schmelter,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-10-09 08:31:44

Jeśli chcesz, aby wyniki były wielkość liter była niewrażliwa , to będzie działać:

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 zawiera b1.dll

secondNotFirst zawiera b2.dll

 10
Author: e.gad,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-02-03 09:32:08

Nie dla tego problemu, ale tu jest jakiś kod do porównywania list dla equal i not! identyczne obiekty:

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);
}
 5
Author: Pius Hermit,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-07-11 21:57:01

Spróbuj w ten sposób:

var difList = list1.Where(a => !list2.Any(a1 => a1.id == a.id))
            .Union(list2.Where(a => !list1.Any(a1 => a1.id == a.id)));
 4
Author: Ali Issa,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-10-09 08:32:30
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;
        }
    }
}

Czasami trzeba tylko wiedzieć czy dwie listy są różne, a nie Jakie są te różnice. W takim przypadku rozważ dodanie tej metody rozszerzenia do projektu. Zauważ, że wymienione obiekty powinny zaimplementować IEquatable!

Użycie:

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
}

Niezależnie od klasy Component, metody przedstawione tutaj dla Car powinny być zaimplementowane niemal identycznie.

To bardzo ważne, aby pamiętać, jak napisaliśmy GetHashCode. W celu prawidłowego wdrożenia IEquatable, Equals oraz GetHashCode musi działać na właściwościach instancji w logicznie zgodny sposób.

Dwie listy z tą samą zawartością są wciąż różnymi obiektami i generują różne kody skrótu. Ponieważ chcemy, aby te dwie listy były traktowane jako równe, musimy pozwolić GetHashCode produkować tę samą wartość dla każdej z nich. Możemy to osiągnąć, delegując hashcode do każdego elementu na liście i używając standardowego bitowego XOR, aby połączyć je wszystkie. XOR jest porządkowo-agnostyczny, więc to nie ma znaczenia, czy listy są sortowane inaczej. Liczy się tylko to, że zawierają tylko równorzędnych członków.

Uwaga: dziwna nazwa ma sugerować fakt, że metoda nie uwzględnia kolejności elementów na liście. Jeśli zależy ci na kolejności elementów na liście, ta metoda nie jest dla Ciebie!

 4
Author: Devon Parsons,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-12-15 12:06:43

Użyłem tego kodu do porównania dwóch list, które mają milion rekordów.

Ta metoda nie zajmie dużo czasu

    //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;
    }
 2
Author: Sathish,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2016-08-09 07:35:35

Może to zabawne, ale mi to odpowiada:

string.Join("",List1) != string.Join("", List2)
 1
Author: Jibz,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2020-11-02 13:14:41

Jeśli potrzebny jest tylko połączony wynik, to również zadziała:

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

Gdzie T jest typem elementu list.

 0
Author: Ali Khaleghi Karsalari,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-09-12 10:07:56

Myślę, że jest to prosty i łatwy sposób na porównanie dwóch list element po elemencie

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)
 -2
Author: user10915707,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2019-01-15 07:47:56

To najlepsze rozwiązanie, jakie znajdziesz

var list3 = list1.Where(l => list2.ToList().Contains(l));
 -3
Author: Fajoui El Mahdi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2018-09-05 14:32:27