Il modo più veloce per implementare la rimozione di caratteri duplicati in stringa (C#)

Question

In C#, qual è il modo più veloce per rilevare caratteri duplicati in una stringa e rimuoverli (rimozione compresa la prima istanza del carattere duplicato)?

Esempio Ingresso: nbHHkRvrXbvkn

Esempio di output: RrX

Answer 1

più veloce come nel minor numero di linee-di-code:

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

più veloce come in più rapida delle prestazioni sarebbe probabilmente qualcosa di simile (non conserva l'ordine):

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

In caso di dubbio - provarlo :)

 
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

Questo algoritmo è generale, può essere applicato a qualsiasi lingua

1. creare una mappa (HashTable) char-> int che contiene il conteggio di ogni carattere trovato, inizialmente vuoto
2. scan the strin g una volta per popolare la mappa.
3. creare una nuova stringa vuota che terrà l'output, potrebbe essere necessario utilizzare un oggetto StringBuilder.
4. scansione stringa (orthe cartina, se minore) copiando solo caratteri un'occorrenza 1 alla stringa di output/StringBuilder

Answer 3

Qui è un ordine racchiudono abbastanza veloce. Ma sarei un po 'preoccupato di come LINQ fa Gruppo e Dove:

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: Questo batte Luca in alcuni casi ancora più lento di DTB di, ma conserva l'ordine

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

Questo uno dovrebbe essere piuttosto veloce (e conserva l'ordine originale):

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

Ciò preserva l'ordine e, in base alle mie prove, è 4 volte più veloce rispetto all'utilizzo di un HashSet. Questo presuppone che il tuo range di caratteri sia 0-255 ma puoi estenderlo facilmente. Se si prevede di utilizzare questo in un ciclo, spostare il int[] c = new int[255]; fuori e nella funzione fare un 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(); 
     }