C#从List<List<int>>中删除重复项

Question

我想知道如何最有效地从List<List<int>>中删除重复项，例如：（我知道这看起来像int[]的列表，但只是为了视觉效果而这样做）：

my_list[0]= {1, 2, 3};
my_list[1]= {1, 2, 3};
my_list[2]= {9, 10, 11};
my_list[3]= {1, 2, 3};

所以输出结果就是：

new_list[0]= {1, 2, 3};
new_list[1]= {9, 10, 11};

如果你有任何想法，请告诉我。我会非常感激。

- marseilles84

---

“{1, 2, 3}”是否等于“{3, 2, 1}”？ - Tim Schmelter

我知道我可以对该实例中的每个元素进行排序，这两个元素最终会相同，所以在这里我会说不需要。 - marseilles84

我会看一下下面使用 Linq 的答案，因为它可以大大简化你的代码（相对于使用 EqualityComparers 的答案）。 - Andy

Answer 1

构建自定义的EqualityComparer<List<int>>：

public class CusComparer : IEqualityComparer<List<int>>
{
    public bool Equals(List<int> x, List<int> y)
    {
        return x.SequenceEqual(y);
    }

    public int GetHashCode(List<int> obj)
    {
        int hashCode = 0;

        for (var index = 0; index < obj.Count; index++)
        {
            hashCode ^= new {Index = index, Item = obj[index]}.GetHashCode();
        }

        return hashCode;
    }
}

您可以使用自定义比较器方法和 Distinct 来获取结果：

var result = my_list.Distinct(new CusComparer());

编辑：

在 GetHashCode 方法中包含索引以确保不同的顺序不相等。

- cuongle

---

那个哈希码会导致很多冲突 - 例如，对于任何 a，{a,a} 都会发生碰撞，{a,b} 与 {b,a} 也会发生碰撞，因为它们是排列。 （尽管您可能希望排列发生碰撞，在这种情况下，答案很棒！） - Rawling

@Rawling：您说得对，等待Tim的评论后，我正在尝试修复。 - cuongle

这里是我认为更好的哈希码生成器：return obj.Take(5).Aggregate(1, (current, item) => (current * 37) + item.GetHashCode()); 首先，我不会迭代整个序列。哈希只有在快速生成时才有效；迭代整个列表会破坏这个目的。前5个或者更少（根据需要编辑）应该就足够了。如果前几个相同，则列表可能不同。接下来，将N个不同哈希组合成一个好的通用算法是遍历每个哈希，将当前值乘以一个质数，然后加上下一个哈希。 - Servy

Answer 2

这个简单的程序可以满足你的要求：

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {
            List<List<int>> lists = new List<List<int>>();

            lists.Add(new List<int> { 1, 2, 3 });
            lists.Add(new List<int> { 1, 2, 3 });
            lists.Add(new List<int> { 9, 10, 11 });
            lists.Add(new List<int> { 1, 2, 3 });

            var distinct = lists.Select(x => new HashSet<int>(x))
                    .Distinct(HashSet<int>.CreateSetComparer());

            foreach (var list in distinct)
            {
                foreach (var v in list)
                {
                    Console.Write(v + " ");
                }

                Console.WriteLine();
            }
        }
    }
}

- Leniel Maccaferri

---

这真的是最好的答案，因为它充分利用了Linq来简化问题。 - Andy

非常快的解决方案。这是正确的答案。谢谢！+1 - Aalawlx

Answer 3

    var finalList = lists.GroupBy(x => String.Join(",", x))
                         .Select(x => x.First().ToList())
                         .ToList();

- L.B

Answer 4

您可以使用带有比较器的LINQ Distinct 重载。比较器应该检查列表是否相等。请注意，列表的默认相等操作不会实现您真正需要的功能，因此比较器需要为您循环遍历每个列表。以下是这样一个比较器的示例：

public class SequenceComparer<T> : IEqualityComparer<IEnumerable<T>>
{
    IEqualityComparer<T> itemComparer;
    public SequenceComparer()
    {
        this.itemComparer = EqualityComparer<T>.Default;
    }

    public SequenceComparer(IEqualityComparer<T> itemComparer)
    {
        this.itemComparer = itemComparer;
    }

    public bool Equals(IEnumerable<T> x, IEnumerable<T> y)
    {
        if (object.Equals(x, y))
            return true;
        if (x == null || y == null)
            return false;
        return x.SequenceEqual(y, itemComparer);
    }

    public int GetHashCode(IEnumerable<T> obj)
    {
        if (obj == null)
            return -1;
        int i = 0;
        return obj.Aggregate(0, (x, y) => x ^ new { Index = i++, ItemHash = itemComparer.GetHashCode(y) }.GetHashCode());
    }
}

更新：我从Cuong Le的回答中得到了使用匿名类型来创建更好哈希的想法，然后通过LINQ对其进行了改进并在我的类中使其工作。

- Tim S.

---

请注意，List<T> 中的 T 必须实现 IComparable 接口。如果 T 是自定义类型，则需要自己实现该接口。 - Michael Sallmen

@MichaelSallmen 我展示了一种实现，可以选择性地使用 IEqualityComparer<T> 来指定如何比较 T 对象。不过你说得很好。（如果一个类型没有定义适当的比较接口，则默认的相等比较器只会检查引用相等性） - Tim S.

@Servy 是的，确实。不过这只是一个示例实现。编写一个好的实现并不容易（例如，请参见Coung Le的更好实现，但仍存在问题）。也许在异或之前将每个项的哈希乘以下一个更大的质数会更好？ - Tim S.

@TimS。我会只留下一个//TODO generate hash，而不是放置你所写的内容；至少这样读者就会知道他们需要自己找到一个好的算法，而不是认为这个已经足够了。 - Servy

@Servy 我已经用一个好的实现替换了它。否则，我会同意你的观点。 - Tim S.

Answer 5

对于小数据集，比较器可能很有用，但如果您有1000个或更多的List>，尝试将它们全部进行比较可能需要很长时间。

我建议您使用数据构建一个不同的树。构建树会快得多，完成后您可以随时将数据带回旧的数据结构中。

- Jastill

Answer 6

我想比较@Leniel Macaferi和@L.B的答案表现，因为我不确定哪个更高效，或者差异是否显著。结果表明，差别非常显著：

Method 1: 00:00:00.0976649 @Leniel Macaferi
Method 2: 00:00:32.0961650 @L.B

这是我用来进行基准测试的代码：

public static void Main(string[] args)
        {
            var list = new List<List<int>> {new List<int> {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3,}, new List<int> {1, 2, 31, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 6}, new List<int> {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 9, 10, 11, 1}, new List<int> {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 9}, new List<int> {1, 2, 31, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 6, 7}, new List<int> {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 9, 10, 11}, new List<int> {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3,}, new List<int> {1, 2, 31, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 6}, new List<int> {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 9, 10, 11}};

            var sw1 = new Stopwatch();
            sw1.Start();

            for (var i = 0; i < 1_000_000; i++)
            {
                var distinct = list.Select(x => new HashSet<int>(x)).Distinct(HashSet<int>.CreateSetComparer());
            }

            sw1.Stop();
            Console.WriteLine($"Method 1: {sw1.Elapsed}");

            var sw2 = new Stopwatch();
            sw2.Start();
            for (var i = 0; i < 1_000_000; i++)
            {
                var distinct = list.GroupBy(a => string.Join(",", a)).Select(a => a.First()).ToList();

            }
            sw2.Stop();
            Console.WriteLine($"Method 2: {sw2.Elapsed}");

            Console.ReadKey();
        }

- Aalawlx