Относится к этому вопросу на основе комментария пользователя Эрик Липперт.
Есть ли сценарий, при котором структура данных Rope более эффективна, чем построитель струн? Некоторые люди считают, что в типичных случаях веревочные структуры данных почти никогда не бывают лучше по скорости, чем нативные строки или операции построения строк, поэтому мне любопытно увидеть реалистичные сценарии, в которых веревки действительно лучше.
Документация для реализации SGI C ++ содержит некоторые подробности по стихам о большом поведении O постоянные факторы, что поучительно.
Их документация предполагает использование очень длинных строк, а примеры, приведенные для справки, говорят о строках размером 10 МБ. Будет написано очень мало программ, которые имеют дело с такими вещами, и для многих классов проблем с такими требованиями их переработка, чтобы они были основаны на потоках, вместо того, чтобы требовать, чтобы полная строка была доступна, где это возможно, приведет к значительно лучшему полученные результаты. Поскольку такие веревки предназначены для непотокового манипулирования многомегабайтными последовательностями символов, когда вы можете надлежащим образом рассматривать веревку как секции (сами веревки), а не просто последовательность символов.
Существенные плюсы:
Существенные минусы:
Это приводит к нескольким «очевидным» применениям (первое явно упоминается SGI).
Бывают случаи, когда поведение строки, зависящее от предметной области, может быть связано с относительно простыми дополнениями к реализации Rope, что позволяет:
Как видно из приведенных примеров, все они хорошо попадают в категорию «нишевых». Кроме того, некоторые из них могут иметь превосходные альтернативы, если вы желаете / можете вместо этого переписать алгоритм как операцию обработки потока.
краткий ответ на этот вопрос - да, и это требует небольшого объяснения. Конечно, есть ситуации, когда структура данных Rope более эффективна, чем построитель строк. они работают по-разному, поэтому больше подходят для разных целей.
(С точки зрения C #)
Структура данных веревки в виде двоичного дерева лучше в определенных ситуациях. Когда вы смотрите на чрезвычайно большие строковые значения (подумайте, что 100+ МБ xml, поступающего из SQL), структура данных веревки может удерживать весь процесс за пределами кучи больших объектов, где строковый объект попадает в него, когда он передает 85000 байт.
Если вы смотрите на строки из 5-1000 символов, это, вероятно, не улучшает производительность настолько, чтобы того стоило. это еще один случай структуры данных, предназначенной для 5% людей, попавших в экстремальную ситуацию.
10-й конкурс программирования ICFP полагался на людей, использующих структура данных веревки для эффективного решения. Это был большой трюк, позволяющий получить виртуальную машину, работающую в разумные сроки.
Веревка отлично подходит, если есть много префиксов (очевидно, слово «добавление» придумано ИТ-специалистами и не является подходящим словом!) И потенциально лучше для вставок; StringBuilders используют непрерывную память, поэтому эффективно работают только при добавлении.
Следовательно, StringBuilder отлично подходит для построения строк путем добавления фрагментов - очень нормальный вариант использования. Поскольку разработчикам требуется много делать это, StringBuilders - очень распространенная технология.
Веревки отлично подходят для буферов редактирования, например. структура данных, лежащая в основе, скажем, TextArea корпоративного уровня. Таким образом (ослабление Ropes, например, связанный список строк, а не двоичное дерево) очень распространено в мире элементов управления пользовательского интерфейса, но это не часто предоставляется разработчикам и пользователям этих элементов управления.
Вам нужны действительно большие объемы данных и отток, чтобы окупиться - процессоры очень хороши в потоковых операциях, и если у вас есть оперативная память, тогда просто перераспределение для префикса работает приемлемо для обычных случаев использования. Это соревнование, упомянутое наверху, было единственным разом, когда я видел, что это нужно.
Большинство продвинутых текстовых редакторов представляют тело текста как «своего рода веревку» (хотя в реализации листья обычно не являются отдельными символами, а являются бегущими по тексту), главным образом для улучшения частых вставок и удалений больших текстов.
Как правило, StringBuilder оптимизирован для добавления и пытается минимизировать общее количество перераспределений без чрезмерного превышения доступности. Типичная гарантия составляет (log2 N выделений и меньше 2,5-кратного объема памяти). Обычно строка создается один раз, а затем может использоваться некоторое время без изменения.
Rope оптимизирован для частых вставок и удалений и пытается минимизировать объем копируемых данных (за счет большего количества выделений). В реализации линейного буфера каждая вставка и удаление становится O (N), и вам обычно приходится представлять вставки одного символа.
Виртуальные машины Javascript часто используют веревки для строк.
Как сообщает , Максим Шевалье-Буазверт, разработчик виртуальной машины на основе Javascript Хиггса. :
В JavaScript вы можете использовать массивы строк и, в конечном итоге, Array.prototype.join, чтобы сделать конкатенацию строк достаточно быстрой, O (n), но «естественный» способ, которым программисты JS создают строки, - это просто добавить с помощью оператора + = к постепенно создавайте их. Строки JS неизменяемы, поэтому, если это не оптимизировано изнутри, инкрементное добавление составляет O (n2). Я думаю, что вполне вероятно, что веревки были реализованы в JS-движках именно из-за тестов SunSpider, которые выполняют добавление строк. Разработчики движка JS использовали веревки, чтобы получить преимущество над другими, сделав то, что раньше было медленным, быстрее. Если бы не эти тесты, я думаю, что крики сообщества о плохой работе добавления строк могли быть встречены словами «используйте Array.prototype.join, dummy!».
