Si les chaînes de caractères sont immuables en .NET, pourquoi la fonction Substring prend-elle du temps en O(n) ?

Question

Étant donné que les chaînes de caractères sont immuables dans .NET, je me demande pourquoi elles ont été conçues de telle sorte que string.Substring() prend du temps en O(substring.Length), au lieu de O(1)?

c'est-à-dire, quels étaient les compromis, le cas échéant?

Answer 1

MISE À JOUR : J'ai tellement aimé cette question que je viens de la bloguer. Voir Strings, immutabilité et persistence

---

La réponse courte est : O(n) est O(1) si n ne devient pas grand. La plupart des gens extraient de minuscules sous-chaînes de minuscules chaînes, donc la façon dont la complexité croît asymptotiquement est complètement irrélevant.

La réponse longue est :

Une structure de données immuable, construite de telle sorte que les opérations sur une instance permettent la réutilisation de la mémoire de l'original avec seulement une petite quantité (typiquement O(1) ou O(log n)) de copie ou de nouvelle allocation, est appelée une structure de données immuable "persistante". Les chaînes dans .NET sont immuables ; votre question est essentiellement "pourquoi ne sont-elles pas persistantes" ?

Parce que lorsque vous regardez les opérations qui sont typiquement effectuées sur les chaînes dans les programmes .NET, il est, de toutes les manières, à peine pire du tout de tout simplement créer une toute nouvelle chaîne. La dépense et la difficulté de construire une structure de données persistante complexe ne se justifient pas.

Les gens utilisent généralement "substring" pour extraire une courte chaîne -- disons, dix ou vingt caractères -- d'une chaîne un peu plus longue -- peut-être quelques centaines de caractères. Vous avez une ligne de texte dans un fichier séparé par des virgules et vous voulez extraire le troisième champ, qui est un nom de famille. La ligne aura peut-être quelques centaines de caractères de long, le nom en aura une vingtaine. L'allocation de chaîne et la copie de mémoire de cinquante octets sont étonnamment rapides sur le matériel moderne. Le fait qu'une nouvelle structure de données qui consiste en un pointeur vers le milieu d'une chaîne existante plus une longueur est également étonnamment rapide est sans importance ; "assez rapide" est par définition assez rapide.

Les sous-chaînes extraites sont généralement de petite taille et de courte durée de vie ; le ramasse-miettes va bientôt les récupérer, et elles n'ont pas pris beaucoup de place sur le tas en premier lieu. Donc utiliser une stratégie persistante qui encourage la réutilisation de la majeure partie de la mémoire n'est pas non plus une victoire ; tout ce que vous avez fait, c'est ralentir votre ramasse-miettes parce qu'il doit maintenant gérer les pointeurs intérieurs.

Si les opérations de sous-chaînes que les gens font généralement sur les chaînes étaient complètement différentes, alors il aurait du sens d'adopter une approche persistante. Si les gens avaient généralement des chaînes d'un million de caractères, et extrayaient des milliers de sous-chaînes se chevauchant avec des tailles dans la plage des cent-mille caractères, et que ces sous-chaînes vivaient longtemps sur le tas, alors il serait parfaitement logique d'adopter une approche persistante des sous-chaînes ; ce serait gaspiller et illogique de ne pas le faire. Mais la plupart des programmeurs en entreprise ne font rien qui ressemble même vaguement à ce genre de choses. .NET n'est pas une plateforme adaptée aux besoins du Projet du Génome Humain ; les programmeurs d'analyse ADN doivent résoudre des problèmes avec ces caractéristiques d'utilisation de chaînes tous les jours ; il est probable que vous ne le faites pas. Ceux qui le font construisent leurs propres structures de données persistantes qui correspondent étroitement à leurs scénarios d'utilisation.

Par exemple, mon équipe écrit des programmes qui analysent en temps réel du code C# et VB au fur et à mesure que vous le tapez. Certains de ces fichiers de code sont énormes et donc nous ne pouvons pas effectuer de manipulation de chaînes en O(n) pour extraire des sous-chaînes ou insérer ou supprimer des caractères. Nous avons construit un ensemble de structures de données immuables persistantes pour représenter les modifications apportées à un tampon de texte qui nous permettent de réutiliser rapidement et efficacement la majeure partie des données de chaînes existantes et les analyses lexicales et syntaxiques existantes lors d'une modification typique. C'était un problème difficile à résoudre et sa solution était spécifiquement adaptée au domaine spécifique de l'édition de code C# et VB. Ce serait irréaliste de s'attendre à ce que le type de chaîne intégré résolve ce problème pour nous.

Answer 2

Précisément parce que les chaînes de caractères sont immuables, .Substring doit faire une copie d'au moins une partie de la chaîne d'origine. Faire une copie de n octets devrait prendre un temps O(n).

Comment pensez-vous que vous pourriez copier une série d'octets en temps constant ?

---

MODIFICATION : Mehrdad suggère de ne pas copier du tout la chaîne, mais de conserver une référence à une partie de celle-ci.

Considérez dans .Net, une chaîne de plusieurs mégaoctets, sur laquelle quelqu'un appelle .SubString(n, n+3) (pour tout n au milieu de la chaîne).

Maintenant, TOUTE la chaîne ne peut pas être ramassée par le ramasse-miettes simplement parce qu'une référence retient 4 caractères ? Cela semble être un gaspillage ridicule d'espace.

De plus, suivre les références aux sous-chaînes (qui peuvent même être à l'intérieur de sous-chaînes), et essayer de copier aux moments optimaux pour éviter de compromettre le ramasse-miettes (comme décrit ci-dessus), rend le concept cauchemardesque. Il est beaucoup plus simple, et plus fiable, de copier lors de l'appel de .SubString, et de maintenir le modèle immuable simple et direct.

---

MODIFICATION : Voici une bonne petite lecture sur le danger de conserver des références aux sous-chaînes au sein de chaînes plus grandes.

Answer 3

Java (par opposition à .NET) propose deux façons de faire Substring(), vous pouvez considérer si vous voulez simplement garder une référence ou copier une sous-chaîne entière vers un nouvel emplacement mémoire.

Le simple .substring(...) partage le tableau char utilisé en interne avec l'objet String d'origine, que vous pouvez ensuite copier vers un nouveau tableau avec new String(...), si nécessaire (pour éviter de gêner la collecte des déchets de l'original).

Je pense que ce genre de flexibilité est la meilleure option pour un développeur.

Answer 4

Java utilisé pour faire référence à des chaînes plus grandes, mais:

Java a changé son comportement en copiant également, pour éviter les fuites de mémoire.

Je pense que cela peut être amélioré cependant : pourquoi ne pas simplement copier de manière conditionnelle?

Si la sous-chaîne est au moins la moitié de la taille du parent, on peut faire référence au parent. Sinon, on peut simplement en faire une copie. Cela évite les fuites de mémoire tout en offrant un bénéfice significatif.

Answer 5

Aucune des réponses ici n'a abordé "le problème du bracketing", c'est-à-dire que les chaînes de .NET sont représentées par une combinaison d'un BStr (la longueur stockée en mémoire "avant" le pointeur) et d'un CStr (la chaîne se termine par un '\0').

La chaîne "Hello there" est donc représentée comme suit :

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

(si elle est affectée à un char* dans une instruction fixed, le pointeur pointerait vers le 0x48.)

Cette structure permet une recherche rapide de la longueur d'une chaîne (utile dans de nombreux contextes) et permet au pointeur d'être passé dans un P/Invoke vers les API Win32 (ou autres) qui s'attendent à une chaîne terminée par un caractère nul.

Lorsque vous faites Substring(0, 5), la règle "oh, mais j'ai promis qu'il y aurait un caractère nul après le dernier caractère" dit que vous devez faire une copie. Même si vous avez la sous-chaîne à la fin, il n'y aurait pas d'endroit où mettre la longueur sans corrompre les autres variables.

---

Parfois, cependant, vous voulez vraiment parler "du milieu de la chaîne", et vous ne vous souciez pas nécessairement du comportement P/Invoke. La structure récemment ajoutée ReadOnlySpan peut être utilisée pour obtenir une sous-chaîne sans copie :

string s = "Hello there";
ReadOnlySpan hello = s.AsSpan(0, 5);
ReadOnlySpan ell = hello.Slice(1, 3);

La "sous-chaîne" ReadOnlySpan stocke la longueur de manière indépendante, et elle ne garantit pas qu'il y ait un '\0' après la fin de la valeur. Elle peut être utilisée de nombreuses manières "comme une chaîne", mais elle n'est pas "une chaîne" car elle n'a ni les caractéristiques de BStr ni de CStr (encore moins les deux). Si vous ne faites jamais (directement) de P/Invoke, il n'y a pas beaucoup de différence (à moins que l'API que vous voulez appeler n'ait pas de surcharge ReadOnlySpan).

ReadOnlySpan ne peut pas être utilisé comme champ d'un type de référence, donc il existe aussi ReadOnlyMemory (s.AsMemory(0, 5)), qui est un moyen indirect d'avoir un ReadOnlySpan, donc les mêmes différences par rapport à une string existent.

Certaines des réponses/commentaires sur les réponses précédentes ont parlé du gaspillage que cela représente pour le ramasse-miettes de devoir garder une chaîne d'un million de caractères alors que vous continuez à parler de 5 caractères. C'est précisément le comportement que vous pouvez obtenir avec l'approche ReadOnlySpan. Si vous ne faites que de courtes opérations, l'approche ReadOnlySpan est probablement meilleure. Si vous devez la conserver pendant un certain temps et que vous ne conservez qu'un petit pourcentage de la chaîne d'origine, faire une véritable sous-chaîne (pour éliminer les données superflues) est probablement mieux. Il y a un point de transition quelque part au milieu, mais cela dépend de votre utilisation spécifique.