文字列の重複文字の削除を実装する最も速い方法（C＃）

Question

C＃では、重複する文字を検出して削除する最も速い方法は何ですか（除外文字を含む）。

例入力：nbHHkRvrXbvkn

出力例：最も少ないライン・オブ・コードのように最速RrX

Answer 1

：最速のパフォーマンスのように最速

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's answer  00:00:00.2360900 
Luke's answer      00:00:00.2225683 
My 'few lines' answer    00:00:00.5318395 
My 'fast' answer     00:00:00.1842144 

Answer 2

このアルゴリズムは一般的である、（任意の言語

1. マップを作成するために適用することができますHashTable）最初に空の文字の数を保持するchar-> int
2. strinをスキャンするgを1回押して地図を入力します。
3. 出力を保持する新しい空の文字列を作成します。StringBuilderを使用する必要があります。
4. 文字のみをコピーする文字列（いずれか短い方ortheマップを、）スキャンここでは、出力文字列/ StringBuilderの
から1の発生

Answer 3

が注文を保存かなり速い一つです。

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

編集：この1はDTB年代よりもルークのいくつかのケースでは、まだ遅く打つが、それはこの

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(); 
} 

Answer 4

順序を保持しかし、私はLINQのグループとどうするかについて少し心配するだろう一つは（と、それは元の順序を維持する）かなり速い必要があります：

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(); 
} 

Answer 5

これは私のテストに基づいて、順序を保持して、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(); 
     }