从列表中删除重复值的最佳算法

Question

什么是从列表中删除重复值的最佳算法？ 我尝试了以下代码：

for (int i = 0; i < AuthorCounter-1; i++)
{
    for (int j = 0; j < AuthorCounter-1; j++)
    {
        if (i != j)
        {
            if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[j].Text)
            {
                AuthorGroupNode.Nodes[j].Remove();
                AuthorCounter--;
            }

        }
    }
}

这里，AuthorGroupNodes 是一个节点列表。它在某种程度上做得不错，但并不完美。有没有更好的解决方案？

- Itz.Irshad

---

根据什么标准来判断最佳？是CPU最低，内存最低，编码难度最小？ - Eric J.

您需要保留顺序吗？关于去重，StackOverflow有很多其他的问题，大多数都提到了去重的标准。顺便说一句，为了编码方便可以使用list.Distinct().toList()，但这可能不是最快的方法。 - Ray Toal

列表中有多少个成员？我不确定您是否真的需要担心规格瓶颈，相反速度应该是问题，前提是该列表中有数万个项目。 - nawfal

如果你的环境受到内存限制，“最佳”算法可能是一种能够在原地完成任务而不分配更多内存的算法，即使 CPU 成本更高。 - Eric J.

这里有正确的答案吗？ - Glenn Ferrie

Answer 1

你目前的算法是O(N平方)，对于大型列表表现非常差。

如果空间不是问题，你可以保留节点哈希值的HashSet。遍历一次列表。如果节点的哈希在HashSet中，则知道这是一个重复的节点。跳过它。如果哈希不在HashSet中，则将此节点添加到新列表中，并将节点的哈希添加到HashSet中。

这将执行O(N)，并需要原始列表的内存，复制列表减去任何重复项的内存和HashSet的内存。该算法是非破坏性的。

如果你可以使用Linq，只需执行

var distinctList = originalList.Distinct().ToList();

更新

发现这基本上就是Jon Skeet重新实现Distinct的方式。

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source) 
{ 
    return source.Distinct(EqualityComparer<TSource>.Default); 
} 

public static IEnumerable<TSource> Distinct<TSource>( 
    this IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer) 
{ 
    if (source == null)  
    { 
        throw new ArgumentNullException("source"); 
    } 
    return DistinctImpl(source, comparer ?? EqualityComparer<TSource>.Default); 
} 

private static IEnumerable<TSource> DistinctImpl<TSource>( 
    IEnumerable<TSource> source, 
    IEqualityComparer<TSource> comparer) 
{ 
    HashSet<TSource> seenElements = new HashSet<TSource>(comparer); 
    foreach (TSource item in source) 
    { 
        if (seenElements.Add(item)) 
        { 
            yield return item; 
        } 
    } 
}

https://codeblog.jonskeet.uk/2010/12/30/reimplementing-linq-to-objects-part-14-distinct/

- Eric J.

Answer 2

这个东西运作得非常好：

var xs = new []
{
    2, 3, 2, 4, 3, 3, 5, 6,
};

var ys = xs
    .ToLookup(z => z, z => z)
    .Select(x => x.First());

对于您的代码，它应该长这样：

var nodes = AuthorGroupNode.Nodes
    .ToLookup(z => z.Text, z => z)
    .Select(x => x.First())
    .ToArray();

那就没有比这更简单的了。:-)

- Enigmativity

---

@EricJ. - Distinct 不适用于自定义对象，除非它们实现了 Equals 和 GetHashCode 方法，而对于这些节点对象，我们并不知道。 - Enigmativity

@Enigmativity tolookup 返回什么？这个方法比 hashset 更快吗？ - nawfal

@nawfal - 它返回一个 System.Linq.ILookup<T1, T2> - 本质上是一个以 T1 为键的 IEnumerable<IEnumerable<T2>>。 - Enigmativity

@nawfal - 它还在内部使用哈希集合（从内存中）因此它非常快。但重要的是它是否使代码清晰，并且它是否足够快。 - Enigmativity

@Enigmativity 谢谢，我懂了。我更关心速度而不是代码清晰性，因为这是我的要求。 - nawfal

@nawfal - 你要求的是“最好”，而不是“最快”。这取决于你如何定义“最好”。 :-) - Enigmativity

Answer 3

借鉴Eric J.的回答...您需要实现一个EqualityComparer来完全控制如何识别不同的项。

class Program
{
    static void Main(string[] args)
    {
        var list = new List<SampleClass>();
        // add some items

        var distinctItems = list.Distinct(new SampleClass());
    }
}

public class SampleClass : EqualityComparer<SampleClass>
{
    public string Text { get; set; }

    public override bool Equals(SampleClass x, SampleClass y)
    {
        if (x == null || y == null) return false;
        return x.Text == y.Text;
    }

    public override int GetHashCode(SampleClass obj)
    {
        if (obj == null) return 0;
        if (obj.Text == null) return 0;
        return obj.Text.GetHashCode();
    }
}

更多信息：http://msdn.microsoft.com/en-us/library/bb338049

这个链接是有关于IT技术的相关信息。

- Glenn Ferrie

Answer 4

您没有检查列表的最后一个元素，您的第二个for循环需要更改为以下内容才能正常工作：

for (int j = 0; j < AuthorCounter; j++)

你正在两次检查每对节点。首先，当i = 0且j = 1时进行检查，稍后再检查当i = 1且j = 0时。没有必要在i之前或等于i开始j。当i = 0时，你的内部循环将删除该元素的所有重复项，因此你知道AuthorGroupNodes.Nodes[0]是唯一的。下一次通过外部循环，你将确信AuthorGroupNodes.Nodes[1]是唯一的。因此，你可以从j等于i + 1开始，并删除i == j的检查。另外，当你删除节点时，j仍然会增加到下一个节点。这将跳过j后面的新节点，这是你删除的节点后面的节点，所以你应该减少j，或者如果你不删除节点，就增加j：

for (int j = i + 1; j < AuthorCounter;)
{
    if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[j].Text)
    {
        AuthorGroupNode.Nodes[j].Remove();
        AuthorCounter--;
    }
    else
    {
        j++;
    }
}

你说这个方法可行但不完美，因此我猜测你没有使用标准的列表，并且你的节点使用Remove()方法自行从列表中删除。

如果列表按照你要比较的字段排序，你可以完全删除内部的for循环，并删除当前元素的任何重复项，直到找到不同的元素。

for (int i = 0; i < AuthorCounter-1;)
{
    if (AuthorGroupNode.Nodes[i].Text == AuthorGroupNode.Nodes[i + 1].Text)
    {
        AuthorGroupNode.Nodes[i].Remove();
        AuthorCounter--;
    }
    else
    {
        i++;
    }
}

- Jason Goemaat

---

哦，我的天啊，这里有那么多好的答案，一定会帮助我完成我的项目，收藏了！ :) - nawfal