LINUX.ORG.RU
Форум — Development  

представление строк в виде ropes


0

0

Тут намедни читал про ropes - структура данных, в которой строка хранится как бинарное дерево, получается, что почти все операции работают эффективнее чем с традиционным представлением в виде массива. Единственное - индексация O(ln N), но по-моему индексация используется чаще всего для foreach, а foreach как раз O(N). В общем очень интересно, но почему оно так редко используется? O(1) (или O(ln N) в случае сбалансированного дерева) конкатенация это же круто :) Или я чего то не понимаю?

http://en.wikipedia.org/wiki/Rope_%28computer_science%29

★★★★★
← emacs, автовставка парных символов
поддержка языка D в emacs →

Первое, что бросается в глаза - повышенный расход памяти по сравнению с обычными строками.

Конкатенация конечно происходит быстро, но после конкатенации обычно надо что-то делать с получившейся строкой. А для этого опять надо будет лазить по дереву. То есть, получается, что-то типа ленивых вычислений конкатенации.

Так что, ИМХО, использовать ropes нужно там, где это необходимо, а не как замену обычных строк. Просто надо помнить о том, что операции над обычными строками тяжелые.

kpanic ★★
()

> В общем очень интересно, но почему оно так редко используется?

std::string ЕМНИПС как минимум в 2-х реализациях STL сделан на ropes.

execve ★
()
Ответ на: комментарий от execve

> std::string ЕМНИПС как минимум в 2-х реализациях STL сделан на ropes.

Надо же, даже не предполагал. (++respect["stl"]) :) а в каких именно? в gnuтой вроде обычный массив. Хотя надо будет проверить.

Legioner ★★★★★
() автор топика

Дорогие in-place операции типа замены одного символа, как уже сказали, больший расход памяти. Плюс итерация значительно медленнее массива (несмотря на такую же амортизированую сложность), а это очень частая операция. Проще всего взять код под вопросом и проверить, перевесит ли для него быстрая конкатенация медленную итерацию, поскольку коэффициенты в обоих O(n), конечно, implementation-dependent.

grob ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← emacs, автовставка парных символов
Development
поддержка языка D в emacs →