ReverseSsortingng, une question d’entrevue en C #

Quelques commentaires sur les réponses données jusqu’à présent:

• Chacun d’entre eux (jusqu’à présent!) Échouera sur les paires de substitution et la combinaison de caractères. Oh les joies de Unicode. Inverser une chaîne ne revient pas à inverser une séquence de caractères.
• J’aime l’optimisation de Marc pour les entrées nulles, vides et à un caractère. En particulier, non seulement cela donne-t-il la bonne réponse rapidement, mais il gère également null (ce qui n’est le cas d’aucune autre réponse)
• Au départ, je pensais que ToCharArray suivi de Array.Reverse serait le plus rapide, mais il crée une copie “garbage”.
• La solution SsortingngBuilder crée une seule chaîne (pas de tableau de caractères) et la manipule jusqu’à ce que vous ToSsortingng . Il n’y a pas de copie supplémentaire impliquée … mais il y a beaucoup plus de travail à maintenir des longueurs etc.

Quelle est la solution la plus efficace? Eh bien, je devrais le comparer pour avoir une idée du tout – mais même ainsi, cela ne va pas raconter toute l’histoire. Utilisez-vous cela dans une situation avec une pression de mémoire élevée, où des déchets supplémentaires sont vraiment pénibles? Quelle est la vitesse de votre mémoire par rapport à votre processeur, etc.?

Comme toujours, la lisibilité est généralement primordiale – et la réponse de Marc à cet égard n’est guère meilleure. En particulier, il n’ya pas de place pour une erreur particulière, alors que je devrais réfléchir à la validation des autres réponses. Je n’aime pas penser. Cela me fait mal au cerveau, alors j’essaie de ne pas le faire très souvent. L’utilisation de la fonction Array.Reverse me semble beaucoup mieux. (OK, donc ça échoue toujours sur les mères porteuses, etc., mais bon …)

Le plus important? Cela va nuire aux performances – il doit créer beaucoup de chaînes (une par caractère). Le moyen le plus simple est quelque chose comme:

 public static ssortingng Reverse(ssortingng sz) // ideal for an extension method { if (ssortingng.IsNullOrEmpty(sz) || sz.Length == 1) return sz; char[] chars = sz.ToCharArray(); Array.Reverse(chars); return new ssortingng(chars); } 

Le problème est que les concaténations de chaînes sont coûteuses car les chaînes sont immuables en C #. L’exemple donné créera une nouvelle chaîne d’un caractère plus long à chaque itération, ce qui est très inefficace. Pour éviter cela, utilisez plutôt la classe SsortingngBuilder :

 public ssortingng ReverseSsortingng(ssortingng sz) { var builder = new SsortingngBuilder(sz.Length); for(int i = sz.Length-1; i>=0; i--) { builder.Append(sz[i]); } return builder.ToSsortingng(); } 

SsortingngBuilder est spécialement conçu pour des scénarios tels que celui-ci, car il vous permet de concaténer des chaînes sans les inconvénients d’une allocation de mémoire excessive.

Vous remarquerez que j’ai fourni à SsortingngBuilder une capacité initiale que vous ne voyez pas souvent. Comme vous connaissez la longueur du résultat pour commencer, cela supprime les allocations de mémoire inutiles.

Ce qui se passe normalement, c’est qu’il alloue une quantité de mémoire au SsortingngBuilder (16 caractères par défaut). Une fois que le contenu tente de dépasser cette capacité, il double (je pense) sa propre capacité et continue. C’est bien mieux que d’allouer de la mémoire à chaque fois comme cela se produirait avec des chaînes normales, mais si vous pouvez éviter cela aussi, c’est encore mieux.

Comme les chaînes sont immuables, chaque instruction += créera une nouvelle chaîne en la copiant à la dernière étape, avec le caractère unique pour former une nouvelle chaîne. Effectivement, ce sera un algorithme O (n ² ) au lieu de O (n).

Un moyen plus rapide serait (O (n)):

 // pseudocode: static ssortingng ReverseSsortingng(ssortingng input) { char[] buf = new char[input.Length]; for(int i = 0; i < buf.Length; ++i) buf[i] = input[input.Length - i - 1]; return new string(buf); } 

Vous pouvez le faire dans .NET 3.5 à la place:

  public static ssortingng Reverse(this ssortingng s) { return new Ssortingng((s.ToCharArray().Reverse()).ToArray()); } 

La meilleure façon de s’y attaquer serait d’utiliser un SsortingngBuilder, puisque ce n’est pas immuable, vous n’obtiendrez pas le terrible comportement de génération d’objects que vous auriez au-dessus. Dans .net, toutes les chaînes sont immuables, ce qui signifie que l’opérateur + = y créera un nouvel object chaque fois qu’il est touché. SsortingngBuilder utilise un tampon interne, l’inversion peut donc être effectuée dans le tampon avec aucune allocation d’object supplémentaire.

Vous devez utiliser la classe SsortingngBuilder pour créer la chaîne résultante. Une chaîne est immuable, donc lorsque vous ajoutez une chaîne à chaque interaction de la boucle, une nouvelle chaîne doit être créée, ce qui n’est pas très efficace.

Je préfère quelque chose comme ça:

 using System; using System.Text; namespace SpringTest3 { static class Extentions { static private SsortingngBuilder ReverseSsortingngImpl(ssortingng s, int pos, SsortingngBuilder sb) { return (s.Length <= --pos || pos < 0) ? sb : ReverseStringImpl(s, pos, sb.Append(s[pos])); } static public string Reverse(this string s) { return ReverseStringImpl(s, s.Length, new StringBuilder()).ToString(); } } class Program { static void Main(string[] args) { Console.WriteLine("abc".Reverse()); } } } 

x est la chaîne à inverser.

  Stack stack = new Stack(x); ssortingng s = new ssortingng(stack.ToArray()); 

Cette méthode réduit de moitié le nombre d’itérations. Plutôt que de commencer à la fin, il commence au début et échange des caractères jusqu’à ce qu’il atteigne le centre. Devait convertir la chaîne en un tableau de caractères car l’indexeur sur une chaîne n’a aucun séparateur.

  public ssortingng Reverse(Ssortingng value) { if (Ssortingng.IsNullOrEmpty(value)) throw new ArgumentNullException("value"); char[] array = value.ToCharArray(); for (int i = 0; i < value.Length / 2; i++) { char temp = array[i]; array[i] = array[(array.Length - 1) - i]; array[(array.Length - 1) - i] = temp; } return new string(array); } 

Nécromancie.
En tant que service public, c’est de cette façon que vous inversez CORRECTEMENT une chaîne.
(inverser une chaîne n’est pas équivalent à inverser une séquence de caractères )

 public static class Test { private static System.Collections.Generic.List GraphemeClusters(ssortingng s) { System.Collections.Generic.List ls = new System.Collections.Generic.List(); System.Globalization.TextElementEnumerator enumerator = System.Globalization.SsortingngInfo.GetTextElementEnumerator(s); while (enumerator.MoveNext()) { ls.Add((ssortingng)enumerator.Current); } return ls; } // this private static ssortingng ReverseGraphemeClusters(ssortingng s) { if(ssortingng.IsNullOrEmpty(s) || s.Length == 1) return s; System.Collections.Generic.List ls = GraphemeClusters(s); ls.Reverse(); return ssortingng.Join("", ls.ToArray()); } public static void TestMe() { ssortingng s = "Les Mise\u0301rables"; // s = "noël"; ssortingng r = ReverseGraphemeClusters(s); // This would be wrong: // char[] a = s.ToCharArray(); // System.Array.Reverse(a); // ssortingng r = new ssortingng(a); System.Console.WriteLine(r); } } 

Voir: https://vimeo.com/7403673

À propos, à Golang, la bonne façon est la suivante:

 package main import ( "unicode" "regexp" ) func main() { str := "\u0308" + "a\u0308" + "o\u0308" + "u\u0308" println("u\u0308" + "o\u0308" + "a\u0308" + "\u0308" == ReverseGrapheme(str)) println("u\u0308" + "o\u0308" + "a\u0308" + "\u0308" == ReverseGrapheme2(str)) } func ReverseGrapheme(str ssortingng) ssortingng { buf := []rune("") checked := false index := 0 ret := "" for _, c := range str { if !unicode.Is(unicode.M, c) { if len(buf) > 0 { ret = ssortingng(buf) + ret } buf = buf[:0] buf = append(buf, c) if checked == false { checked = true } } else if checked == false { ret = ssortingng(append([]rune(""), c)) + ret } else { buf = append(buf, c) } index += 1 } return ssortingng(buf) + ret } func ReverseGrapheme2(str ssortingng) ssortingng { re := regexp.MustComstack("\\PM\\pM*|.") slice := re.FindAllSsortingng(str, -1) length := len(slice) ret := "" for i := 0; i < length; i += 1 { ret += slice[length-1-i] } return ret } 

Et la manière incorrecte est la suivante (ToCharArray.Reverse):

 func Reverse(s ssortingng) ssortingng { runes := []rune(s) for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 { runes[i], runes[j] = runes[j], runes[i] } return string(runes) } 

Notez que vous devez connaître la différence entre
- un personnage et un glyphe
- un octet (8 bits) et un sharepoint code / rune (32 bits)
- un codepoint et un GraphemeCluster [32+ bit] (ou Grapheme / Glyph)

Référence:

Caractère est un terme surchargé qui peut vouloir dire beaucoup de choses.

Un sharepoint code est l'unité atomique d'information. Le texte est une séquence de points de code. Chaque sharepoint code est un nombre qui a une signification selon le standard Unicode.

Un graphème est une séquence d'un ou de plusieurs points de code affichés sous forme d'une seule unité graphique qu'un lecteur reconnaît comme un seul élément du système d'écriture. Par exemple, a et ä sont des graphèmes, mais ils peuvent être constitués de plusieurs points de code (par exemple, ä peut être deux points de code, un pour le caractère de base a suivi d'un pour la diarèse; mais il existe également une alternative, héritée, à code unique point représentant ce graphème). Certains points de code ne font jamais partie d'un graphème (par exemple, les largeurs de largeur non jointes ou les substitutions de direction).

Un glyphe est une image, généralement stockée dans une police (une collection de glyphes), utilisée pour représenter des graphèmes ou des parties de ceux-ci. Les fonts peuvent composer plusieurs glyphes en une seule représentation, par exemple, si ä est un seul sharepoint code, une police peut choisir de le rendre sous forme de deux glyphes séparés superposés dans l'espace. Pour OTF, les tables GSUB et GPOS de la police contiennent des informations sur la substitution et le positionnement pour que cela fonctionne. Une police peut également contenir plusieurs glyphes alternatifs pour le même graphème.

  static ssortingng reverseSsortingng(ssortingng text) { Char[] a = text.ToCharArray(); ssortingng b = ""; for (int q = a.Count() - 1; q >= 0; q--) { b = b + a[q].ToSsortingng(); } return b; }