en C #, quel est le moyen le plus rapide de détecter les caractères en double dans une chaîne et de les supprimer (suppression Exemple d'entrée: Exemple de sortie: nbhhkrvrxbvkn
rrx
5 Réponses :
la plus rapide comme dans le moins de lignes de code: le plus rapide comme dans la performance la plus rapide serait probablement quelque chose comme ceci (ne conserve pas la commande): P>
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
Très agréable. Excellente comparaison de performance aussi. La variation de performance est probablement encore plus visible avec de très grandes chaînes.
J'ai répété le test de performance dans la version de version avec débogueur détachée (mais même chaîne d'entrée). Je suis surpisée par la performance de la réponse de Yuriy; C'est assez vite!
@DTB: La chose qui ralentit ma réponse par rapport à la vôtre est que je préserve la commande d'origine dans la chaîne de sortie, ce qui nécessite une boucle supplémentaire via la chaîne d'entrée. La technique que vous et j'utilise pour trouver réellement les DuPes est exactement la même chose.
Voir ma solution ci-dessous ... vous avez eu la bonne idée, mais que vous utilisez un tableau pour que les données connues est 4 fois plus rapide que le hashset dans mes tests
c # a var? ... Je n'ai jamais vu l'utilisation de Var en C # avant ... Btw Bonne morceau de code bon travail! +1
représente une variante, généralement utilisée avec Linq pour les types anonymes, découragée autrement.
Cet algorithme est général, peut être appliqué à n'importe quelle langue
Voici un ordre de préservation assez rapide. Mais je serais un peu inquiet sur la façon dont Linq fait le groupe et où: Edit: Celui-ci bat de Luke est toujours plus lent que celui des DTB, mais il conserve la commande
Celui-ci devrait être assez rapide (et conserve la commande d'origine):
Pourquoi pensez-vous que la création d'un StressBuilder est probablement trop grande qui prendra moins de temps que de lui permettre d'obtenir de la place à la volée?
@Yuri: J'ai comparé! J'ai testé avec des millions de chaînes aléatoires et la pré-dimensionnement du stringbuilder était plus rapide dans la plupart des cas. Bien sûr, dans le monde réel, les cordes ne seraient probablement pas purement aléatoires. Dans cette situation, la différence de performance dépendrait du ratio de DuPes aux non-hausses de la chaîne source.
@Yuriy: Je viens de comparer sur une machine différente (Vista64 vs XP32) et les résultats étaient beaucoup plus proches. Sur la machine 64 bits, il semble ne faire aucune différence réelle si le StringBuilder est pré-alloué ou non. (Dans ce cas, il est probablement logique de ne pas déranger de pré-allouer et de nous sauver quelques béliers.)
Cela préserve la commande et, sur la base de mes tests, est 4 fois plus rapide que d'utiliser un hashset. Cela suppose que votre gamme de caractères est de 0 à 255, mais vous pouvez l'étendre facilement. Si vous envisagez d'utiliser cela dans une boucle, déplacez le int [] c = neuf int [255]; code> ou dans la fonction effectue un array.clear (C, 0.255) code>.
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();
}
De plus, je ne sais pas si le compilateur déroulera ces boucles pour vous, mais vous pouvez essayer cela aussi .wikipedia.org / wiki / loop_unwinding
Quel est votre résumé de test / chronomètre avec la chaîne d'échantillon?
Avec la chaîne d'échantillonnage, cette méthode serait de 1/4 ou moins comparée aux autres.
@Yuriy: Est-ce que la taille de la matrice est-elle correctement définie sur 65536? Dans mes tests, il n'y a pas vraiment beaucoup de différence entre cette méthode et à l'aide d'un hashset une fois que la matrice est correctement dimensionnée.
Non, une fois que la matrice est réglée correctement en moyenne sur une corde de 100 caractères, elle était pire de 60%.