Najszybszym sposobem na wykonanie Duplicate Character Removal w łańcuchu znaków (C#)

Question

W języku C#, jaki jest najszybszy sposób na wykrycie duplikatów znaków w łańcuchu znaków i usunięcie ich (usunięcie , w tym pierwsza instancja zduplikowanej litery)?

Przykład Wejście: nbHHkRvrXbvkn

Przykład wyjściowa: RrX

Answer 1

Najszybciej jak w najmniejszej linii-of-kodu:

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

Najszybciej jak w najszybszym wydajności prawdopodobnie będzie coś takiego (nie zachowuje zamówienia):

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" 

---

Performance Test

W razie wątpliwości - przetestować :)

 
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

Algorytm ten ma charakter ogólny, można stosować do dowolnego języka

1. stworzyć mapę (HashTable) char-> int, który przechowuje liczbę znalezionych znaków, początkowo pusty
2. zeskanuj strin g raz, aby wypełnić mapę.
3. utworzyć nowy pusty ciąg, który będzie przechowywać dane wyjściowe, może być konieczne użycie StringBuilder.
4. skanować ciąg (Orthe mapę, która wartość jest mniejsza) kopiując tylko znaki, które zdarzenie z 1 do ciągu wyjściowego/StringBuilder

Answer 3

o to dość szybko porządek jeden zachowaniu. Ale byłbym trochę zaniepokojony jak LINQ robi Group i Gdzie:

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

Edit: To bije Łukasza w niektórych przypadkach nadal wolniejsze niż DTB-tych, ale zachowuje kolejność

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

ten trzeba być bardzo szybkie (i zachowuje oryginalną kolejność):

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

to zachować porządek i na podstawie moich badań, jest 4 razy szybciej niż przy użyciu HashSet. Zakłada to, że twój zakres znaków wynosi 0-255, ale możesz to łatwo rozszerzyć. Jeśli planujesz użyć tego w pętli, przenieś urządzenie int[] c = new int[255]; i wykonaj funkcję 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(); 
     }