Représentations de cordes: améliorations par rapport aux cordes?

Question

Je veux une représentation pour les chaînes avec des opérations rapides de concaténation et d'édition. J'ai lu le document "Ropes: an Alternative to Strings", mais y a-t-il eu des améliorations significatives dans ce domaine depuis 1995?

EDIT: Une possibilité que j'ai envisagée avant utilise un 2-3 finger tree avec des chaînes comme des feuilles, mais je n'ai pas fait une analyse détaillée de ceci; ceci donne une addition/suppression à temps constant amortie sur les extrémités et une concaténation logarithmique (dans le nombre de morceaux de la plus petite chaîne), par opposition à l'inverse pour les cordes.

Answer 1

Ceci est une vieille question! Je me demande si quelqu'un lit ceci. Mais encore, c'est intrigant. Dans vos commentaires, vous dites que vous recherchez:

plus rapide asymptote, ou les facteurs constants, ou moins l'utilisation de la mémoire

Eh bien, les cordes ont O (1) insertion, et O (n) itération. Tu ne peux pas faire mieux que ça. Les sous-chaînes et l'indexation vont évidemment être plus coûteux. Mais la plupart des cas d'utilisation de documents volumineux ne nécessitent pas d'édition ou d'accès aléatoire. Si vous concattez seulement à la fin, un vecteur 1D/liste de chaînes pourrait améliorer la constante de temps d'insertion. J'avais l'habitude de l'utiliser en JavaScript parce qu'il avait une concaténation de chaînes si lente.

On dit que la représentation de la mémoire est moins efficace que l'utilisation de chaînes. Je doute que: Si vous travaillez dans un langage qui a la garbage collection, la corde vous permet d'utiliser la même instance de fragment de chaîne à plusieurs endroits. Dans une corde qui représente un document HTML, il y aura beaucoup de DIV, SPAN et LINK. Cela peut même arriver automatiquement en supposant que ces balises sont des constantes de temps de compilation, et vous les ajoutez directement à la corde. Même pour de telles phrases courtes, le document de corde va réduire de manière significative, au même ordre de grandeur que la chaîne originale. Des chaînes plus longues produiront un gain net.

Si vous ne faites que lire l'arborescence en lecture seule, vous pouvez créer des sous-réseaux (expressions plus longues exprimées sous forme de cordes), qui se produisent plusieurs fois ou sont partagés entre des chaînes. L'inconvénient de ce partage est que de telles sections de corde de partition ne peuvent pas être changées: pour les éditer, ou pour équilibrer l'arbre, vous devez copier le graphe d'objet. Mais cela n'a pas d'importance si vous concaténez et itérez. Dans un serveur Web, vous pouvez conserver une sous-arborescence qui représente la déclaration de feuille de style CSS partagée par tous les documents HTML fournis par ce serveur.