Si les chaînes sont immuables dans .NET, alors pourquoi la sous-chaîne prend-elle du temps O (n)?

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

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

MISE À JOUR: J'ai tellement aimé cette question, je viens de la bloguer. Voir Cordes, immuabilité et persistance

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

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é (généralement O (1) ou O (lg n)) de copie ou de nouvelle allocation est appelée "persistante" structure de données immuable. Les chaînes en .NET sont immuables; votre question est essentiellement "pourquoi ne sont-ils pas persistants"?

Parce que lorsque vous examinez les opérations qui sont généralement effectuées sur des chaînes dans des programmes .NET, il n'est guère pire du tout de créer une chaîne entièrement nouvelle. Le coût et la difficulté de construire une structure de données persistante complexe ne sont pas rentables.

Les gens utilisent généralement "sous-chaîne" pour extraire une chaîne courte - 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 souhaitez extraire le troisième champ, qui est un nom de famille. La ligne comptera peut-être quelques centaines de caractères, le nom sera une douzaine de caractères. L'allocation de chaînes et la copie de mémoire de cinquante octets sont étonnamment rapides sur le matériel moderne. Ce faisant une nouvelle structure de données qui se compose d'un pointeur au milieu d'une chaîne existante plus une longueur est également étonnamment rapide hors de propos; "assez vite" 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 ramasseur de déchets va bientôt les récupérer, et ils 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 plupart de la mémoire n'est pas non plus une victoire; tout ce que vous avez fait est de ralentir le ramassage des ordures, car il doit maintenant se soucier de la manipulation des pointeurs intérieurs.

Si les opérations de sous-chaîne que les gens effectuaient généralement sur les chaînes étaient complètement différentes, il serait logique d'adopter une approche persistante. Si les gens avaient généralement des chaînes de millions de caractères et extrayaient des milliers de sous-chaînes qui se chevauchent avec des tailles dans la plage de cent mille caractères, et que ces sous-chaînes vivaient longtemps sur le tas, alors il serait parfaitement logique d'aller avec une sous-chaîne persistante approche; ce serait inutile et insensé de ne pas le faire. Mais la plupart des programmeurs métier ne font rien, même vaguement, comme ce genre de choses. .NET n'est pas une plateforme adaptée aux besoins du projet du génome humain; Les programmeurs d'analyse d'ADN doivent résoudre tous les jours des problèmes avec ces caractéristiques d'utilisation des chaînes; les chances sont bonnes que vous n'avez pas. Les rares qui construisent leurs propres structures de données persistantes qui correspondent étroitement à leurs scénarios d'utilisation.

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

Précisément parce que les chaînes sont immuables, vous .Substringdevez faire une copie d'au moins une partie de la chaîne d'origine. Faire une copie de n octets devrait prendre du temps O (n).

Comment pensez-vous que vous copieriez un tas d'octets en temps constant ?

EDIT: Mehrdad suggère de ne pas copier la chaîne du tout, mais de conserver une référence à un morceau 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, la chaîne ENTIÈRE ne peut pas être récupérée simplement parce qu'une référence contient 4 caractères? Cela semble être un gaspillage ridicule d'espace.

De plus, le suivi des références aux sous-chaînes (qui peuvent même se trouver à l'intérieur des sous-chaînes) et essayer de copier à des moments optimaux pour éviter de vaincre le GC (comme décrit ci-dessus), fait du concept un cauchemar. Il est beaucoup plus simple et plus fiable de copier .SubStringet de maintenir le modèle immuable simple.

EDIT: Voici une bonne petite lecture sur le danger de conserver des références à des sous-chaînes dans des chaînes plus grandes.

Java (par opposition à .NET) offre deux façons de faire Substring(), vous pouvez déterminer si vous souhaitez conserver uniquement une référence ou copier une sous-chaîne entière vers un nouvel emplacement de mémoire.

Le simple .substring(...) partage le chartableau utilisé en interne avec l'objet String d'origine, avec lequel vous pouvez ensuite new String(...)copier dans un nouveau tableau, si nécessaire (pour éviter d'entraver le garbage collection de celui d'origine).

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

Java utilisé pour référencer des chaînes plus grandes, mais:

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

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

Si la sous-chaîne fait au moins la moitié de la taille du parent, on peut référencer le parent. Sinon, il suffit de faire une copie. Cela évite de perdre beaucoup de mémoire tout en offrant un avantage significatif.

Aucune des réponses ici n'a abordé "le problème du bracketing", c'est-à-dire que les chaînes en .NET sont représentées comme 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

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

(s'il est affecté à un char*dans une fixedinstruction, le pointeur pointerait vers 0x48.)

Cette structure permet une recherche rapide de la longueur d'une chaîne (utile dans de nombreux contextes) et permet de passer le pointeur dans une API P / Invoke à Win32 (ou autre) qui attend une chaîne terminée par null.

Lorsque vous effectuez 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", la règle dit que vous devez faire une copie. Même si vous avez obtenu la sous-chaîne à la fin, il n'y aurait pas de place pour 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 ReadOnlySpan<T>structure récemment ajoutée peut être utilisée pour obtenir une sous-chaîne sans copie:

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

le ReadOnlySpan<char> "sous-chaîne" stocke la longueur indépendamment, et elle ne garantit pas qu'il y a un '\ 0' après la fin de la valeur. Il peut être utilisé de plusieurs façons "comme une chaîne", mais ce n'est pas "une chaîne" car il n'a pas de caractéristiques BStr ou CStr (et encore moins les deux). Si vous n'avez jamais (directement) P / Invoke, il n'y a pas beaucoup de différence (sauf si l'API que vous souhaitez appeler n'a pas de ReadOnlySpan<char>surcharge).

ReadOnlySpan<char>ne peut pas être utilisé comme champ d'un type de référence, il y a donc aussi ReadOnlyMemory<char>(s.AsMemory(0, 5) ), qui est un moyen indirect d'avoir un ReadOnlySpan<char>, donc les mêmes différences stringexistent.

Certaines des réponses / commentaires sur les réponses précédentes parlaient du gaspillage d'avoir le garbage collector à garder une chaîne d'un million de caractères pendant que vous continuez à parler de 5 caractères. C'est précisément le comportement que vous pouvez obtenir avec l' ReadOnlySpan<char>approche. Si vous ne faites que de courts calculs, l'approche ReadOnlySpan est probablement meilleure. Si vous devez le conserver pendant un certain temps et que vous ne conserverez qu'un faible pourcentage de la chaîne d'origine, il est probablement préférable de créer une sous-chaîne appropriée (pour supprimer les données en excès). Il y a un point de transition quelque part au milieu, mais cela dépend de votre utilisation spécifique.