Quelle est la complexité de la concaténation des cordes équilibrées?

Je l'ai regardé différents papiers et voici les informations que j'ai recueillies:Quelle est la complexité de la concaténation des cordes équilibrées?

SGI implementation et C cords ni garantie O (1) concaténation de temps pour de longues cordes ni ~ log N profondeur pour les plus courtes .
Différentes sources se contredisent. Wikipedia revendique O (1) concaténation. This page indique que la concaténation est O (1) seulement lorsqu'un opérande est petit et O (log N) sinon.

Alors, quelle est la complexité temporelle de la concaténation? Quand exactement le rééquilibrage est effectué pour assurer cette complexité de concaténation tout en maintenant l'équilibre de l'arbre? Certains modèles d'utilisation spécifiques sont-ils supposés lorsqu'on parle de cette complexité?

Source

2010-10-08 ybungalobill

Toutes les opérations sont de type 'log (N)' complexité temporelle. La corde est essentiellement un arbre de recherche binaire composé de clés implicites, qui sont dans la nature se référer à la taille du sous-arbre. Cela permet des opérations puissantes telles que concat/split. Une des implémentations possibles est l'utilisation d'une structure de données Treap, qui est délibérément faite pour fonctionner avec des clés implicites et avec une probabilité élevée de garder la hauteur de l'arbre avec une plage '4 * log (n)', qui est 'O (log n) '. J'ai fait une implémentation simple en utilisant Treap: https://ideone.com/uMt0Mi. – Yerken

@Yerken: merci, puisque j'ai posé cette question, j'ai implémenté des cordes moi-même - avec une complexité déterministe de 'log N' garantie. Il semble que 'O (1)' concaténation est une idée fausse répandue par certaines personnes, le faire dans 'O (log N)' est trivial. J'ai jeté un coup d'oeil sur votre code, mais cela ne semble pas convenir aux implémentations en corde: si vous utilisez des pointeurs parents, vous devez cloner l'arbre entier (en temps O (N)) lors de changements locaux. Le point des cordes est qu'ils évitent cela. – ybungalobill

désolé, ne comprends pas, qu'est-ce que tu veux dire par le clonage de l'arbre entier? Toutes les modifications locales sont effectuées par fusion et scission, qui sont effectuées uniquement le long de la ligne de coupe (où les pointeurs sont déréférencés) qui est une hauteur de l'arbre – Yerken

L'article de wikipedia n'est pas clair, le papier "Ropes: an Alternative to Strings" qu'il cite nulle part, réclame un tel résultat de complexité.

D'autre part, cet article récent (par Gerth Stölting Brodal, Christos Makris et Kostas Tsichlas) -t: "Purely Functional Worst Case Constant Time Catenable Sorted Lists". Ils ont aussi la recherche O (logn), donc en effet vous pouvez l'étiqueter "équilibré", je n'ai pas lu les détails cependant, juste les résultats.

"Corde" est un terme qui est (relativement) commun dans la pratique, mais pas dans la recherche. Au lieu de cela, j'ai cherché catenable queues (ou des listes), en particulier la recherche faite par des gens comme Tarjan, Okasaki, Kaplan et d'autres, je pense que c'est là que votre vraie réponse est.

Source

2010-10-13 16:20:33

Merci pour l'article, malheureusement, il ne peut pas être utilisé pour implémenter des cordes car il ne supporte pas l'opération * split * efficace (dernier paragraphe de l'article), donc nous ne pouvons pas récupérer efficacement la sous-chaîne. – ybungalobill

Eh bien, si vous pouviez trouver une solution à cela, elle serait publiable :) L'article sur les cordes est difficile à suivre, apparemment les auteurs avaient quelque chose contre la notation du big-oh - mais une telle notation rendrait très précis ce qu'ils sont après. Sur le rééquilibrage, ils sont aussi vagues que possible. "Nous faisons rarement un rééquilibrage" ". Ok ... ça sonne bien, je suppose ... –

Quelle est la complexité de la concaténation des cordes équilibrées?

Répondre

Questions connexes