Si les chaînes sont immuables dans .NET, alors pourquoi Subssortingng prend-il le 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 ssortingng.Subssortingng() prenne le temps O ( subssortingng.Lengthssortingng.Subssortingng() 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 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, de sorte que la complexité augmente de façon asymptotique.

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 lorsque vous regardez des opérations qui sont généralement effectuées sur des chaînes dans les programmes .NET, il est difficile 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 voulez extraire le troisième champ, qui est un nom de famille. La ligne aura peut-être quelques centaines de caractères, le nom sera de quelques dizaines. L’allocation de chaînes et la copie de mémoire de cinquante octets sont incroyablement rapides sur le matériel moderne. Le fait de créer une nouvelle structure de données composée d’un pointeur au milieu d’une chaîne existante et d’une longueur incroyablement rapide est sans importance. “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 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, utiliser une stratégie persistante qui encourage la réutilisation de la plus grande partie de la mémoire n’est pas non plus une victoire. tout ce que vous avez fait est de ralentir votre ramasse-miettes, car maintenant il faut se soucier de la manipulation des pointeurs intérieurs.

Si les opérations de sous-chaîne que les utilisateurs exécutaient 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 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 inutile et inutile de le faire. Mais la plupart des programmeurs ne font rien, même vaguement, comme ce genre de choses . .NET n’est pas une plate-forme adaptée aux besoins du projet du génome humain; Les programmeurs d’parsing d’ADN doivent résoudre chaque jour les problèmes d’utilisation de ces chaînes; les chances sont bonnes que vous ne le fassiez 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 d’parsing à 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 ensemble de structures de données permanentes immuables pour représenter les modifications apscopes à un tampon de texte, ce qui nous permet de réutiliser rapidement et efficacement la majeure partie des données de chaîne existantes et les parsings lexicales et syntaxiques existantes lors d’une édition classique. 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.

Précisément parce que les chaînes sont immuables, .Subssortingng doit faire une copie d’au moins une partie de la chaîne d’origine. Faire une copie de n octets devrait prendre O (n) heure.

Comment pensez-vous que vous copiez un tas d’octets dans un temps constant ?


EDIT: Mehrdad suggère de ne pas copier la chaîne du tout, mais de garder une référence à un morceau.

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

Maintenant, la chaîne ENTIRE ne peut pas être récupérée simplement parce qu’une référence contient 4 caractères? Cela semble être une perte d’espace ridicule.

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


EDIT: Voici une petite lecture sur le danger de garder des références aux sous-chaînes dans les grandes chaînes.

Java (par opposition à .NET) fournit deux façons de faire Subssortingng() , vous pouvez déterminer 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 .subssortingng(...) partage le tableau de caractères utilisé en interne avec l’object Ssortingng original, que vous pouvez ensuite copier avec un nouveau tableau (si nécessaire new Ssortingng(...) avec un new Ssortingng(...) (pour ne pas gêner la récupération de mémoire de l’original) un).

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 modifié son comportement pour éviter les memory leaks.

Je pense que cela peut être amélioré cependant: pourquoi ne pas simplement faire la copie sous certaines conditions?

Si la sous-chaîne a 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.

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 assigné à un caractère char* dans un état fixed 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.

Lorsque vous faites Subssortingng(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 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 structure ReadOnlySpan récemment ajoutée peut être utilisée pour obtenir une sous-chaîne sans copie:

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

Le ReadOnlySpan “subssortingng” 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 n’a 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 (à moins que l’API que vous souhaitez appeler n’ait pas de surcharge ReadOnlySpan ).

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

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 l’approche ReadOnlySpan . 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 gardez 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 sharepoint transition quelque part au milieu, mais cela dépend de votre utilisation spécifique.