c# - 在列表列表中查找重复项

Question

简单的情况。我有一个列表列表，几乎像表格一样，我试图找出是否有重复的列表。

例子:

List<List<int>> list = new List<List<int>>(){
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
  new List<int>() {0 ,1 ,4, 2, 4, 5, 6 },
  new List<int>() {0 ,3 ,2, 5, 1, 6, 4 }
};

我想知道总共有 4 个项目，其中 2 个是重复的。我正在考虑做类似 SQL checksum 的事情但我不知道是否有更好/更简单的方法。

我关心性能，我关心顺序。

可能有帮助的其他信息

• 永远不会删除插入此列表的内容
• 不受任何特定集合的约束。
• 不关心函数签名
• 他们的类型不限于int

Answer 1

让我们尝试获得最佳性能。如果 n 是列表的数量，m 是列表的长度，那么我们可以得到 O(nm + nlogn + n) 加上不同列表的哈希码相等的概率。

主要步骤:

1. 计算哈希码*
2. 对它们进行排序
3. 遍历列表以找到受骗者

* 这是重要的一步。为了简单起见，您可以将哈希计算为 = ... ^ (list[i] << i) ^ (list[i + 1] << (i + 1))

编辑 对于那些认为 PLINQ 可以提升性能但不是好的算法的人。也可以在此处添加 PLINQ，因为所有步骤都可以轻松并行化。

我的代码:

static public void Main()
{
    List<List<int>> list = new List<List<int>>(){
      new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
      new List<int>() {0 ,1 ,2, 3, 4, 5, 6 },
      new List<int>() {0 ,1 ,4, 2, 4, 5, 6 },
      new List<int>() {0 ,3 ,2, 5, 1, 6, 4 }
    };
    var hashList = list.Select((l, ind) =>
    {
        uint hash = 0;
        for (int i = 0; i < l.Count; i++)
        {
            uint el = (uint)l[i];
            hash ^= (el << i) | (el >> (32 - i));
        }
        return new {hash, ind};
    }).OrderBy(l => l.hash).ToList();
    //hashList.Sort();
    uint prevHash = hashList[0].hash;
    int firstInd = 0;            
    for (int i = 1; i <= hashList.Count; i++)
    {
        if (i == hashList.Count || hashList[i].hash != prevHash)
        {
            for (int n = firstInd; n < i; n++)
                for (int m = n + 1; m < i; m++)
                {
                    List<int> x = list[hashList[n].ind];
                    List<int> y = list[hashList[m].ind];
                    if (x.Count == y.Count && x.SequenceEqual(y))
                        Console.WriteLine("Dupes: {0} and {1}", hashList[n].ind, hashList[m].ind);
                }                    
        }
        if (i == hashList.Count)
            break;
        if (hashList[i].hash != prevHash)
        {
            firstInd = i;
            prevHash = hashList[i].hash;
        }
    }
}