La forma más rápida de implementar la eliminación de caracteres duplicados en cadena (C#)

Question

En C#, ¿cuál es la forma más rápida de detectar caracteres duplicados en una cadena y eliminarlos (eliminación incluyendo 1ª instancia del carácter duplicado)?

Ejemplo de entrada nbHHkRvrXbvkn

Ejemplo de salida: RrX

Answer 1

más rápido que en el menor número de líneas-de-código:

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

más rápido que en el de mayor rendimiento, probablemente sería algo como esto (no conserva el orden):

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" 

---

Prueba de rendimiento

En caso de duda - probarlo :)

 
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

Este algoritmo es general, se puede aplicar a cualquier idioma

1. crear un mapa (HashTable) char-> int que contiene el recuento de cada carácter encontrado, inicialmente vacío
2. escanea el strin g una vez para poblar el mapa.
3. crea una nueva cadena vacía que contendrá el resultado, puede ser que necesites usar un StringBuilder.
4. escanear la cadena (osi mapa, el que sea más corto) copiando sólo caracteres que una ocurrencia de 1 a la cadena de salida/StringBuilder

Answer 3

Aquí es una orden de preservar uno bastante rápido. Pero me gustaría ser un poco preocupado por cómo lo hace LINQ Group y Donde:

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

Editar: Éste es mejor que Lucas, en algunos casos aún más lento que el de DTB, pero conserva el orden

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

Este uno debe ser bastante rápido (y se preserva el orden original):

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

Esto preserva el orden y, con base en mis pruebas, es 4 veces más rápido que el uso de un HashSet. Esto supone que tu rango de caracteres es 0-255, pero puedes extenderlo fácilmente. Si planea usar esto en un bucle, mueva el int[] c = new int[255]; y en la función haga 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(); 
     }