在C#中实现字符串中重复字符的最快方法

Question

在C#中实现字符串中重复字符的最快方法

c#.netstring

8

在C＃中，检测字符串中重复字符并删除它们（删除包括第一个实例中的重复字符）的最快方法是什么？

示例输入：nbHHkRvrXbvkn

示例输出：RrX

- Alex

5个回答

9

这是一个保留顺序的相当快的方法。但我会担心LINQ如何处理Group和Where：

string s = "nbHHkRvrXbvkn";
Console.WriteLine( 
    s.ToCharArray()
        .GroupBy(c => c)
        .Where(g => g.Count() == 1)
        .Aggregate(new StringBuilder(), (b, g) => b.Append(g.Key)));

编辑：在某些情况下，这个版本仍然比Luke's慢，但它保留了顺序。

private static string MyMethod(string s)
{
    StringBuilder sb = new StringBuilder(s.Length);
    foreach (var g in s.ToCharArray().GroupBy(c => c))
        if (g.Count() == 1) sb.Append(g.Key);

    return sb.ToString();
}

- Yuriy Faktorovich

4

这个应该很快（并且它保留了原始顺序）：

public static string RemoveDuplicates(string source)
{
    HashSet<char> found = new HashSet<char>();
    HashSet<char> dupes = new HashSet<char>();

    foreach (char c in source)
    {
        if (!found.Add(c))
        {
            dupes.Add(c);
        }
    }

    StringBuilder sb = new StringBuilder(source.Length);
    foreach (char c in source)
    {
        if (!dupes.Contains(c))
        {
            sb.Append(c);
        }
    }
    return sb.ToString();
}

- LukeH

你认为创建一个可能过大的 StringBuilder 比让它在运行时获取空间需要更少的时间，是因为什么原因？ - Yuriy Faktorovich

@Yuri：我进行了基准测试！我使用了数百万个随机字符串进行测试，并且预设StringBuilder的大小在大多数情况下更快。当然，在实际应用中，字符串可能不是纯随机的。在这种情况下，性能差异将取决于源字符串中重复和非重复字符的比例。 - LukeH

@Yuriy：我刚在另一台机器上（Vista64 vs XP32）进行了基准测试，结果差距不太大。在64位机器上，StringBuilder 是否预先分配似乎并没有真正的影响。（在这种情况下，不预先分配可能是有意义的，可以节省一些内存。） - LukeH

2

这种方法保持了顺序，并且根据我的测试，比使用HashSet快4倍。这假定您的字符范围为0-255，但您可以轻松扩展它。如果您计划在循环中使用此功能，请将int [] c = new int [255];移出并在函数中执行Array.Clear（c，0，255）。


        private static string RemoveDuplicates(string s)
        {
            int[] c = new int[255];
            for (int i = 0; i < s.Length; i++)
            {
                c[s[i]]++;
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < s.Length; i++)
            {
                if (c[s[i]] == 1) sb.Append(s[i]);
            }
            return sb.ToString();
        }

- gabe

另外，我不知道编译器是否会为您展开这些循环，但您也可以尝试一下。http://en.wikipedia.org/wiki/Loop_unwinding - gabe

你使用样例字符串进行测试的计时/秒表结果是多少？ - Alex

使用示例字符串，与其他方法相比，此方法的效率将降低为1/4甚至更少。 - Yuriy Faktorovich

@Yuriy：数组大小是否正确设置为65536？在我的测试中，一旦数组大小正确设置，使用此方法与使用HashSet并没有太大的区别。 - LukeH

1

不，一旦数组正确设置，在平均处理100个字符的字符串时，性能会降低60%。 - Yuriy Faktorovich

0

这个算法是通用的，可以应用于任何语言

创建一个映射（哈希表）char->int，用于保存每个字符的计数，最初为空
扫描字符串一次以填充映射。
创建一个新的空字符串，用于保存输出，可能需要使用StringBuilder。
扫描字符串（或映射，以较短者为准），仅将出现1次的字符复制到输出字符串/StringBuilder中

- Diaa Sami

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dtb · Accepted Answer

最快，也就是最少代码的意思：

var s = "nbHHkRvrXbvkn";
var duplicates = s.Where(ch => s.Count(c => c == ch) > 1);
var result = new string(s.Except(duplicates).ToArray()); // = "RrX"

在最快性能方面，可能会使用以下方法(不保留顺序)：

var h1 = new HashSet<char>();
var h2 = new HashSet<char>();

foreach (var ch in "nbHHkRvrXbvkn")
{
    if (!h1.Add(ch))
    {
        h2.Add(ch);
    }
}

h1.ExceptWith(h2); // remove duplicates

var chars = new char[h1.Count];
h1.CopyTo(chars);
var result = new string(chars); // = "RrX"

性能测试

遇到疑问时，请进行测试 :)

Yuriy Faktorovich的答案        00:00:00.2360900
Luke的答案                     00:00:00.2225683
我的'few lines'答案           00:00:00.5318395
我的'fast'答案                00:00:00.1842144