从可枚举对象中过滤重复项。

Question

我有一个可能包含重复项的无序枚举，我想删除所有具有重复项的项目，并仅保留在原始枚举中只出现一次的项目。

例如：由于它们出现了多次，因此将删除A和C：

输入 {A,C,B,A,C,D,A}
输出 {B,D}

一个快速而简单的实现可能是：

IEnumerable<T> Filter(IEnumerable<T> items)
{
   items.Where(item => items.Count(x => x.Equals(item)) == 1);
}

显然，这不是一个快速或优雅的方法。

下面的示例仍然是二次的（稍微快一些），但需要对输入进行ToList()调用。

IEnumerable<T> Filter(IEnumerable<T> items)
{
    List<T> src = items.ToList();
    for(int i=0; i<src.Count; i++)
    {
       if (src.IndexOf(src[i], i+1) < 0)
         yield return src[i]; 
    }
}

如果您希望代码在保持紧凑和易读的同时，不会像这些实现一样非常慢，那么您该如何做呢？

- Anders Forsgren

---

你可以按自身分组，然后丢弃大小大于1的组。虽不是最优解，但读起来还算清晰易懂，时间复杂度也不会超过二次方。 - Raymond Chen

说实话，“快速而肮脏”的代码看起来“优雅而迅速”，比使用groupby更喜欢。 - ericosg

在使用了一些秒表后，第一行“脏”代码比Brad的groupby更快，老实说，当上面的行以//开头时，它是完全可读的 ;) - ericosg

@ericosg：我想看看那些基准测试，因为500k个元素根本不需要时间（http://ideone.com/RpgD87）。 - Brad Christie

确实，速度快多了，我的测试数据太弱了。顺便提一下，在你的秒表之间不要忘记加上 .ToList();，否则它们不会计算实际执行时间（除非你也将输出包装在 sw 中）。 - ericosg

@ericosg：好观点。.ToList() 运行稍微慢一些，但是在 580k 条目下仍然很快。 - Brad Christie

Answer 1

LINQ通过GroupBy函数使这个过程变得非常简单：

IEnumerable<String> foo = new[]{ "A", "C", "B", "A", "C", "D", "A" };
Ienumerable<String> result = foo.GroupBy (x => x)          // A=>3,C=>2,B=>1,D=>1
                               .Where(x => x.Count() == 1) // B=>1,D=>1
                               .Select (x => x.Key);       // B,D

1. 按值将它们分组
2. 过滤掉只有一个条目的内容
3. 选择原始值

不确定您对性能需要什么，但我个人倾向于使用GroupBy。

- Brad Christie

---

似乎这也是我能想到的最好的答案。 - Patrick Magee

无论哪种方式，您都需要查找另一个包含匹配项及其数量的结构。 GroupBy 可以优雅地完成这个任务(在我看来)，同时保持简洁。 - Brad Christie

利用PLINQ会提高性能吗？如果有成百上千个重复项呢？使用.AsParallel，这只是一个可以考虑的想法吗？将可枚举对象分割成块，然后分别处理，最后合并结果或类似的操作。 - Patrick Magee

@PatrickMagee，如果你分割数据，可能会导致连接的块具有重复项（单独的块没问题，但一起出现重复项）。 - Ivaylo Slavov

@PatrickMagee：处理50万条记录速度相当快。 - Brad Christie

Answer 2

您可以在O(N)时间内完成此操作。

算法：

• 创建一个字典[T，count] - (O(1))
• 扫描输入 - (O(N))，插入一个项目 - (O(1)) 或增加计数 - (O(1))
• 扫描具有计数为1的项目的字典 - (O(N))

此解决方案需要两次完整扫描：一次是输入，第二次是结果字典。虽然它不是LINQ，但实际上可能比LINQ更快。

class Program
{
    static void Main(string[] args)
    {
        var input = new[] { "A", "C", "B", "A", "C", "D", "A" };
        var result = Filter(input);
        Console.WriteLine(result);
    }

    static IEnumerable<T> Filter<T>(IEnumerable<T> items)
    {
        var dictionary = new Dictionary<T, int>();

        //first scan of the input
        foreach (T item in items)
        {
            if (dictionary.ContainsKey(item))
            {
                dictionary[item]++;
            }
            else
            {
                dictionary[item] = 1;
            }
        }

        //second scan
        return from x in dictionary
                where x.Value == 1
                select x.Key;
    }
}

- oleksii

Answer 3

使用集合如何：

IEqualityComparer<T> comparer = EqualityComparer<T>.Default;

HashSet<T> itemsToKeep = new HashSet<T>(comparer );
HashSet<T> itemsToRemove = new HashSet<T>(comparer );

foreach(T item in items)
{
   if (itemsToRemove.Add(item))
   {
       continue;
   }
   itemsToKeep.Add(item);
}

itemsToKeep.ExceptWith(itemsToRemove);

---

如果可能的话，您可以使用自定义的 IEqualityComparer<T> 实现来加速集合的性能。

- Ivaylo Slavov

---

可能有点过头了？ - ericosg

@ericosg，我非常确定这两个循环是不可避免的（ExceptWith是第二个循环）。内置的集合修改操作可能已经足够优化了。一个好的自定义比较器对于 T 可以证明是有用的。你指的是向集合中添加操作太慢了吗？ - Ivaylo Slavov