Question Si les chaînes sont immuables dans .NET, alors pourquoi Substring prend-il le temps O (n)?


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

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


427
2017-07-19 06:05


origine


Réponses:


MISE À JOUR: J'ai tellement aimé cette question, je l'ai juste blogué. Voir Cordes, immuabilité et persistance


La réponse courte est: O (n) est O (1) si n ne grossit pas.  La plupart des gens extraient des sous-chaînes minuscules à partir de minuscules cordes, alors comment la complexité se développe asymptotiquement complètement hors de propos.

La longue réponse est:

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

Parce que quand vous regardez des opérations qui sont typiquement fait sur les chaînes dans les programmes .NET, il est de toutes les manières pertinentes guère pire du tout simplement créer une chaîne entièrement nouvelle. Le coût et la difficulté de la construction d'une structure de données persistantes complexes ne sont pas rentables.

Les gens utilisent généralement "substring" pour extraire une chaîne courte - disons, dix ou vingt caractères - sur 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 sera peut-être quelques centaines de caractères, le nom sera quelques dizaines. L'allocation de chaîne et la copie de mémoire de cinquante octets est étonnamment rapide sur du matériel moderne. Que faire une nouvelle structure de données qui consiste en un pointeur vers le milieu d'une chaîne existante plus une longueur est aussi étonnamment rapide est hors de propos; "assez vite" est par définition assez rapide.

Les sous-chaînes extraites sont typiquement de petite taille et de courte durée de vie; le ramasse-miettes va bientôt les récupérer, et ils n'ont pas pris beaucoup de place sur le tas en premier lieu. Donc, l'utilisation d'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 est de ralentir votre garbage collector car il doit maintenant se préoccuper de la manipulation des pointeurs intérieurs.

Si les opérations de sous-chaînes généralement effectuées 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 se chevauchant avec des tailles dans la plage de cent mille caractères, et que ces sous-chaînes vivaient longtemps sur le tas, il serait parfaitement logique d'aller avec une sous-chaîne persistante approche; ce serait un gaspillage et une folie de ne pas le faire. Mais la plupart des programmeurs de ligne de métier ne font rien, même vaguement comme ce genre de choses. .NET n'est pas une plate-forme adaptée aux besoins du projet Génome humain; Les programmeurs d'analyse d'ADN doivent résoudre tous les jours des problèmes liés à ces caractéristiques d'utilisation des chaînes. les chances sont bonnes que vous ne le fassiez pas. Les rares qui construisent leurs propres structures de données persistantes leur scénarios d'utilisation

Par exemple, mon équipe écrit des programmes qui analysent à la volée le code C # et le code VB au fur et à mesure que vous le saisissez. Certains de ces fichiers de code sont énorme et donc nous ne pouvons pas faire de manipulation de chaînes 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, ce qui nous permet de réutiliser rapidement et efficacement l'essentiel des données de chaîne existantes et les analyses lexicales et syntaxiques existantes sur un montage 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ésolve ce problème pour nous.


401
2017-07-19 16:25



Précisément car Les cordes 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 le temps O (n).

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


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

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

Maintenant, la chaîne ENTIRE ne peut pas être garbage collection juste parce qu'une référence tient sur 4 caractères? Cela semble être un gaspillage ridicule de l'espace.

En outre, le suivi des références aux sous-chaînes (qui peuvent même être à l'intérieur des sous-chaînes), et essayer de copier à des moments optimaux pour éviter la GC (comme décrit ci-dessus), rend le concept un cauchemar. Il est beaucoup plus simple et plus fiable de copier sur .SubString, et maintenez le modèle immuable simple.


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


115
2017-07-19 06:08



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

Le simple .substring(...) partage l'utilisation interne char tableau avec l'objet String d'origine, que vous avec ensuite new String(...) peut copier vers un nouveau tableau, si nécessaire (pour éviter de gêner la récupération de place de l'original).

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


32
2017-07-19 08:32



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

Java a changé son comportement pour copier aussi, pour éviter les fuites de mémoire.

Je pense que cela peut être amélioré cependant: pourquoi ne pas faire la copie conditionnellement?

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


10
2017-12-03 19:21



Aucune des réponses ne concerne le "problème de bracketing", c’est-à-dire que les chaînes en .NET sont représentées par une combinaison de BStr (la longueur stockée en mémoire "avant" le pointeur) et 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

(si attribué à un char* dans un fixed-statement le pointeur pointe 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 transmis dans une API P / Invoke à Win32 (ou autre) qui attend une chaîne terminée par un caractère nul.

Quand tu fais Substring(0, 5) le "oh, mais j'ai promis qu'il y aurait un caractère nul après le dernier caractère" règle 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 de "le milieu de la chaîne", et vous ne vous souciez pas nécessairement du comportement de P / Invoke. Le récemment ajouté ReadOnlySpan<T> structure 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> "substring" stocke la longueur indépendamment, et il ne garantit pas qu'il y ait un '\ 0' après la fin de la valeur. Il peut être utilisé de plusieurs manières "comme une chaîne de caractères", mais ce n'est pas une "chaîne" car il ne possède pas de caractéristiques BStr ou CStr (beaucoup moins les deux). Si vous n'appelez jamais (directement) P / Invoke, il n'y a pas beaucoup de différence (sauf si l'API que vous voulez appeler n'a pas de ReadOnlySpan<char> surcharge).

ReadOnlySpan<char> ne peut pas être utilisé comme champ d'un type de référence, donc il y a aussi ReadOnlyMemory<char> (s.AsMemory(0, 5)), qui est une manière indirecte d'avoir ReadOnlySpan<char>, donc les mêmes différences-de-string exister.

Certaines des réponses / commentaires sur les réponses précédentes indiquaient qu’il était inutile de faire en sorte que le ramasse-miettes garde une chaîne de millions de caractères tout en continuant à parler de 5 caractères. C'est précisément le comportement que vous pouvez obtenir avec le ReadOnlySpan<char> approche. Si vous ne faites que des calculs courts, l’approche ReadOnlySpan est probablement meilleure. Si vous avez besoin de persister pendant un certain temps et que vous ne conservez qu'un faible pourcentage de la chaîne d'origine, il est probablement préférable de faire une sous-chaîne appropriée (pour réduire 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.


1
2017-07-16 16:21