Pourquoi les cordes sont-elles si lentes?

23

Depuis ma toute première classe de programmation au lycée, j'entends dire que les opérations de cordes sont plus lentes - c'est-à-dire plus coûteuses - que la mythique «opération moyenne». Pourquoi les rend-ils si lents? (Cette question est laissée intentionnellement large.)

Pops
la source
11
Si vous savez que ces «opérations moyennes» sont mythiques, pouvez-vous au moins nous en dire quelques-unes? Étant donné que vous posez une question aussi vague, il est difficile de faire confiance à votre affirmation selon laquelle ces opérations non spécifiées sont vraiment mythiques.
seh
1
@seh, malheureusement, je ne peux pas répondre à cela. Les quelques fois où j'ai demandé aux gens quelles cordes sont plus lentes, ils ont juste haussé les épaules et ont dit "ils sont juste lents". D'ailleurs, si j'avais des informations plus précises, ce serait une question pour SO, pas pour les programmeurs; c'est déjà un peu limite.
Pops
Dans quel but ? Si les chaînes sont dites lentes, allez-vous arrêter de les utiliser?
Tulains Córdova
Oublie. Si quelqu'un vous dit un tel non-sens, la contre-question est: "Vraiment? Sont-ils? Devrions-nous alors utiliser un int-array?"
Ingo

Réponses:

47

"L'opération moyenne" a lieu sur des primitives. Mais même dans les langues où les chaînes sont traitées comme des primitives, elles sont toujours des tableaux sous le capot, et faire quoi que ce soit impliquant la chaîne entière prend du temps O (N), où N est la longueur de la chaîne.

Par exemple, l'ajout de deux nombres prend généralement 2 à 4 instructions ASM. La concaténation ("ajout") de deux chaînes nécessite une nouvelle allocation de mémoire et une ou deux copies de chaîne, impliquant la chaîne entière.

Certains facteurs linguistiques peuvent aggraver la situation. En C, par exemple, une chaîne est simplement un pointeur vers un tableau de caractères terminé par null. Cela signifie que vous ne savez pas combien de temps il est, il n'y a donc aucun moyen d'optimiser une boucle de copie de chaîne avec des opérations de déplacement rapide; vous devez copier un caractère à la fois afin de pouvoir tester chaque octet pour le terminateur nul.

Mason Wheeler
la source
4
Et certains langages le rendent beaucoup mieux: le codage Delphi de la longueur de chaîne au début du tableau rend la concaténation de chaîne très rapide.
Frank Shearar
4
@gablin: Cela aide également en accélérant la copie de la chaîne elle-même. Lorsque vous connaissez la taille à l'avance, vous n'avez pas besoin de copier un octet à la fois et de vérifier chaque octet pour un terminateur nul, vous pouvez donc utiliser la taille complète de n'importe quel registre, y compris les registres SIMD, pour le mouvement des données, ce qui rend jusqu'à 16 fois plus rapide.
Mason Wheeler
4
@mathepic: Oui, et c'est bien pour autant que cela vous amène, mais lorsque vous commencez à interagir avec libc ou un autre code externe, il attend un char*, pas un strbuf, et vous revenez à la case 1. Il n'y a que tant de choses que vous peut faire quand un mauvais design est cuit dans la langue.
Mason Wheeler
6
@mathepic: Bien sûr, le bufpointeur est là. Je n'ai jamais voulu laisser entendre qu'il n'est pas disponible; c'est plutôt nécessaire. Tout code qui ne connaît pas votre type de chaîne optimisé mais non standard, y compris des éléments aussi fondamentaux que la bibliothèque standard , doit toujours se replier sur le lent et dangereux char*. Vous pouvez appeler ce FUD si vous le souhaitez, mais cela ne le rend pas faux.
Mason Wheeler
7
Les gens, il y a une chronique de Joel Spolsky sur le point de Frank Shearer: Back to Basics
user16764
14

Ceci est un vieux fil et je pense que les autres réponses sont excellentes, mais oubliez quelque chose, alors voici mes (tardifs) 2 cents.

Le revêtement de sucre syntactique cache la complexité

Le problème avec les chaînes est qu'elles sont des citoyens de seconde classe dans la plupart des langues, et ne sont en fait pas la plupart du temps une partie de la spécification de la langue elle-même: elles sont une construction implémentée par la bibliothèque avec une couche de sucre syntaxique occasionnelle sur le dessus pour les rendre moins pénibles à utiliser.

La conséquence directe de cela est que le langage cache une très grande partie de leur complexité à votre vue, et vous payez pour les effets secondaires sournois parce que vous avez l'habitude de les considérer comme une entité atomique de bas niveau, tout comme d'autres types primitifs (comme expliqué par la réponse la plus votée et d'autres).

Détails d'implémentation

Good Ol 'Array

Un des éléments de cette "complexité" sous-jacente est que la plupart des implémentations de chaînes auraient recours à une structure de données simple avec un espace mémoire contigu pour représenter la chaîne: votre bon vieux tableau.

Cela a du sens, sachez que vous voulez que l'accès à la chaîne dans son ensemble soit rapide. Mais cela implique des coûts potentiellement terribles lorsque vous souhaitez manipuler cette chaîne. L'accès à un élément au milieu peut être rapide si vous savez quel index vous recherchez , mais pas la recherche d'un élément basé sur une condition.

Même le retour de la taille de la chaîne peut être coûteux, si votre langue ne met pas en cache la longueur de la chaîne et doit la parcourir pour compter les caractères.

Pour des raisons similaires, l' ajout d' éléments à votre chaîne s'avérera coûteux car vous devrez probablement réallouer de la mémoire pour que cette opération se produise.

Ainsi, différentes langues adoptent des approches différentes à ces problèmes. Java, par exemple, a pris la liberté de rendre ses chaînes immuables pour des raisons valables (longueur de mise en cache, sécurité des threads) et pour ses homologues mutables (StringBuffer et StringBuilder) choisiront d'allouer la taille en utilisant des morceaux de plus grande taille pour ne pas avoir besoin d'allouer à chaque fois, mais espérez plutôt les meilleurs scénarios. Cela fonctionne généralement bien, mais l'inconvénient est parfois de payer pour les impacts sur la mémoire.

Prise en charge Unicode

De plus, et encore une fois, cela est dû au fait que le revêtement de sucre syntaxique de votre langue vous le cache pour jouer bien, vous ne le pensez souvent pas en termes de support unicode (surtout aussi longtemps que vous n'en avez pas vraiment besoin). et a frappé ce mur). Et certains langages, étant avant-gardistes, n'implémentent pas de chaînes avec des tableaux sous-jacents de simples primitives char 8 bits. Ils ont cuit en UTF-8 ou UTF-16 ou ce que vous avez en charge, et la conséquence est une consommation de mémoire considérablement plus grande, qui n'est souvent pas nécessaire, et un temps de traitement plus long pour allouer de la mémoire, traiter les chaînes, et implémenter toute la logique qui va de pair avec la manipulation des points de code.


Le résultat de tout cela, c'est que lorsque vous faites quelque chose d'équivalent en pseudo-code pour:

hello = "hello,"
world = " world!"
str = hello + world

Il se peut que ce ne soit pas - malgré tous les efforts que les développeurs de langage mettent en œuvre pour les faire se comporter comme vous le feriez sauf - aussi simple que:

a = 1;
b = 2;
shouldBeThree = a + b

À titre de suivi, vous voudrez peut-être lire:

haylem
la source
Bon ajout à la discussion actuelle.
Abel
Je viens de réaliser que c'est la meilleure réponse car la déclaration mythique peut être appliquée à n'importe quoi comme le cryptage RSA est lent. La seule raison pour laquelle des chaînes sont placées dans cet endroit embarrassant est que l'opérateur plus a fourni des chaînes dans la plupart des langues, ce qui fait que les débutants ne sont pas conscients du coût de l'opération.
Codisme
@Abel: merci, il m'a semblé qu'il y avait de la place pour des détails plus génériques.
haylem
@Codism: merci, content que vous ayez aimé. Je pense en effet que cela peut être appliqué à de nombreux cas où c'est juste une question de complexité cachée (et nous ne prêtons plus autant d'attention aux détails de niveau inférieur jusqu'à ce que nous en ayons finalement besoin parce que nous avons frappé un goulot d'étranglement ou un mur de briques en quelque sorte ).
haylem
1

L'expression "opération moyenne" est probablement un raccourci pour une seule opération d'une machine théorique à programme d'accès aléatoire . Il s'agit de la machine théorique qu'il est habituel d'utiliser pour analyser le temps d'exécution de divers algorithmes.

Les opérations génériques sont normalement prises pour être charger, ajouter, soustraire, stocker, branche. Peut-être aussi lire, imprimer et arrêter.

Mais la plupart des opérations de chaîne nécessitent plusieurs de ces opérations fondamentales. Par exemple, la duplication d'une chaîne nécessite normalement une opération de copie, et donc un nombre d'opérations qui est proportionnel à la longueur d'une chaîne (c'est-à-dire qu'elle est "linéaire"). La recherche d'une sous-chaîne à l'intérieur d'une autre chaîne présente également une complexité linéaire.

James Youngman
la source
1

Cela dépend complètement de l'opération, de la façon dont les chaînes sont représentées et des optimisations existantes. Si les chaînes ont une longueur de 4 ou 8 octets (et sont alignées), elles ne seraient pas nécessairement plus lentes - de nombreuses opérations seraient aussi rapides que les primitives. Ou, si toutes les chaînes ont un hachage 32 bits ou 64 bits, de nombreuses opérations seraient également aussi rapides (bien que vous payiez le coût de hachage à l'avance).

Cela dépend aussi de ce que vous entendez par «lent». La plupart des programmes traitent les chaînes très rapidement pour ce qui est nécessaire. Les comparaisons de chaînes peuvent ne pas être aussi rapides que la comparaison de deux entiers, mais seul le profilage révélera ce que "lent" signifie pour votre programme.

Kevin Hsu
la source
0

Permettez-moi de répondre à votre question par une question. Pourquoi dire une chaîne de mots prend plus de temps que de dire un seul mot?

ChaosPandion
la source
2
Ce n'est pas nécessairement le cas.
user16764
3
Supercalifragilisticexpialidocious
Spoike
s / mot / syllabe / g
Caleb
Permettez-moi de répondre à votre question-réponse par une question: pourquoi ne dites-vous pas ce que signifie votre réponse? Il est, après tout, loin d'être clair comment il peut être interprété comme s'appliquant à un système d'exécution.
PJTraill