Moyen le plus rapide d'implémenter la suppression de caractères en double dans String (C#)

Question

Exemple d'entrée: nbHHkRvrXbvkn

Résultat: RrX

Answer 1

plus rapide que dans moins de lignes-de-code:

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

plus rapide que dans la plus rapide performance serait probablement quelque chose comme ça (ne conserve pas l'ordre):

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" 

---

Test de performance

En cas de doute - le tester :)

 
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

Cet algorithme est général, peut être appliquée à toute langue

1. créer une carte (HashTable) char-> int qui contient le nombre de chaque caractère trouvé, initialement vide
2. scan the strin g une fois pour peupler la carte.
3. créez une nouvelle chaîne vide qui conservera la sortie, vous devrez peut-être utiliser un StringBuilder.
4. scan la chaîne (oula carte, selon la plus courte) copie uniquement des caractères qui une occurrence de 1 à la chaîne de sortie/StringBuilder

Answer 3

Voici un assez rapide maintien de l'ordre. Mais je serais un peu inquiet sur la façon dont LINQ fait groupe et où:

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: Celui-ci bat Luke dans certains cas encore plus lent que celui des DTB, mais il conserve l'ordre

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

Cette on devrait être assez rapide (et il conserve l'ordre 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

Cela préserve l'ordre et, en fonction de mes tests, est 4 fois plus rapide que d'utiliser un HashSet. Cela suppose que votre plage de caractères est comprise entre 0 et 255 mais vous pouvez l'étendre facilement. Si vous envisagez d'utiliser ceci dans une boucle, déplacez le int[] c = new int[255]; et dans la fonction faites 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(); 
     }