Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
Классная штука Rope, да. Только на Хабре уже была, хотя и не так конкретно.
Ну конечно медленно, если не использовать StringBuilder (в C#, в других яп думаю тоже есть аналоги):
StringBuilder sb = new StringBuilder(String.empty);
for (int i = 0; i < 100000; i++) sb.Append("a");
Там как раз в следующем абзаце про такие билдеры написано. Это классический код с объяснением почему нельзя складывать строки именно таким образом.
Либо StringBuilder(), либо String.Format()
StringBuilder сильно проигрывает Ropes
У вас и имплементация Rope есть, наверное, для .NET?
Даешь бенчмарки!
Мой прогноз — незначительная разница при построении строки, а при сравнении строк огромный, в несколько порядков отрыв по скорости «обычного порошка» от веревочных строк.
Мой прогноз — незначительная разница при построении строки, а при сравнении строк огромный, в несколько порядков отрыв по скорости «обычного порошка» от веревочных строк.
Ожидаемо операции на «результирующей» строке медленнее, в частности и без того медленные регулярные выражения(в 2-10 раз медленннее с#/Java кода habrahabr.ru/post/126954/ — например ) еще в 3-30 раз замедляются.
Потестил StringBuilder в С#, Append скейлится линейно, в 10 раз увеличил количество итераций — в 10 раз выросло время, а вот Insert, как и в этих бенчмарках, геометрической прогрессией растет.
Возможно имеет смысл конструировать строку этим методом(сделать RopeBuilder какой нибудь), если нужен именно быстрый Insert, а затем так же как и StringBuilder экспортировать в обычную immutable строку, в которой быстрее другие операции.
Потестил StringBuilder в С#, Append скейлится линейно, в 10 раз увеличил количество итераций — в 10 раз выросло время, а вот Insert, как и в этих бенчмарках, геометрической прогрессией растет.
Возможно имеет смысл конструировать строку этим методом(сделать RopeBuilder какой нибудь), если нужен именно быстрый Insert, а затем так же как и StringBuilder экспортировать в обычную immutable строку, в которой быстрее другие операции.
А я оставлю пару комментариев Эрика Липперта:
1:
2:
1:
If you have a scenario where this data structure is more optimal than a string builder, I would be curious to know what it is. It has been my experience that rope data structures are almost never a win over the raw speed of native string or string builder operations in typical cases, so I am very interested to see realistic scenarios where its a win.
2:
My experience is admittedly limited; I've tried to add rope-style string representations to languages like VBScript and JScript. The number of cases in which we must aggressively reify internal strings into «real» buffer-based strings was so large, and the number of cases where runtime string manipulations actually grew large, complex strings was so small, that the net perf impact was negative. When we built the string logic in JScript.NET we simply used a stringbuilder rather than attempting ropes again.
Интересно, одноимённый класс в Java работает так же, как и в C#?
Мне кажется в этом случае сильно возрастает сложность алгоритма сравнения строк, а соответсвенно и сортировки.
Да, тоже подумал как такие строки будут в регулярных выражениях обрабатываться. :) Но если такой необходимости нет по задаче — почему нет?
Со сравнением строк все нормально как раз. Сравнение требует последовательного перебора символов который за счет кэширования последнего индекса работает быстро. Порядок сложности не увеличится, увеличится только константа.
Нет, сложность алгоритма не возрастёт, а останется прежней = o(n), где n — длина строки.
Интересный способ. Возможно, имело-бы смысл использовать nested sets для каких-то операций (веса — похожий прием, но не много не тот). Интуитивно мне кажется что при этом не пострадает скорость операций.
Спасибо за статью (и ссылки), познавательно!
ЗЫ: Кмк получаемое дерево все-таки не двоичное дерево поиска, нет?
ЗЫ: Кмк получаемое дерево все-таки не двоичное дерево поиска, нет?
Я в свой проекте на Delphi был вынужден что-то подобное строить. У меня строки доходили до 2 500 000 символов, и беда была не в скорости, а в проблеме сегментации строк. Эта проблема вызывала exception «out of mem».
Следует упомянуть, что для Delphi 7 (на других не проверял), такой подход помимо скорости дает и прирост отказоустойчивости.
Следует упомянуть, что для Delphi 7 (на других не проверял), такой подход помимо скорости дает и прирост отказоустойчивости.
А есть готовая интерпретация на C++?
Как тут уже говорили, даешь бенчмарки! :)
Ещё интересно, как давно вам приходилось соединять 100 000 строк в цикле?
Ещё интересно, как давно вам приходилось соединять 100 000 строк в цикле?
В 2007 году на ICFP Contest'e, когда спасали Endo
save-endo.cs.uu.nl/
Похожую структуру и применяли.
В практических задачах — вряд ли встретится, но структура хороша, если стоит задача в быстрой генерации больших текстовых данных.
save-endo.cs.uu.nl/
Похожую структуру и применяли.
В практических задачах — вряд ли встретится, но структура хороша, если стоит задача в быстрой генерации больших текстовых данных.
Хотелось бы обозначить область применимости такого хранения.
Первый ваш пример уже вызывает сомнения. Что будет в памяти после
for (int i = 0; i < 100000; i++) s += «a»;
Будет ли это лучше StringBuilder?
Первый ваш пример уже вызывает сомнения. Что будет в памяти после
for (int i = 0; i < 100000; i++) s += «a»;
Будет ли это лучше StringBuilder?
Об области применения можно почитать немного здесь: www.ibm.com/developerworks/java/library/j-ropes/
Я обычно использую массив строк.
Тем более конкатенация для много-много-много строк требуется как правило один раз (для вывода, например, в поток, в который, кстати можно скормить массив и без конкатенации).
Тем более конкатенация для много-много-много строк требуется как правило один раз (для вывода, например, в поток, в который, кстати можно скормить массив и без конкатенации).
Вот такие строки в WebKit используются.
И не всегда это хорошо — ибо эта зараза будет каждый раз при обращении к строке ее собирать.
Иногда крайне не приятно и не понятно получается
И не всегда это хорошо — ибо эта зараза будет каждый раз при обращении к строке ее собирать.
Иногда крайне не приятно и не понятно получается
А для питона есть адекватная реализация?
Ок, все вроде так офигенно, но… Данный паттерн используется повсеместно и, к сожалению не является серебрянной пулей. Такие решения применяются для более узконаправленных типов данных, что как бы обоснованно (на основе данных профилированния). Но если говорить о строках, ребята настолько разнообразно ими пользуются, что сделать серьезно эффективнее чем strcmp или strcpy (ок, плюсовые варианты) ну нет, чудес не бывает. Либо память, либо такты. Ну либо более специализированные варианты, которые привели выше.
если не ошибаюсь, то у libevent буфер-ы так и работают
Похожая структура Twine используется в LLVM.
Можно также заметить, что такую структуру данных можно сделать персистентной и использовать для реализации функционала DO-UNDO. Правда, деталей реализации у такого решения довольно много.
Можно также заметить, что такую структуру данных можно сделать персистентной и использовать для реализации функционала DO-UNDO. Правда, деталей реализации у такого решения довольно много.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Ropes — быстрые строки