Есть ли сценарий, в котором структура данных Rope более эффективна, чем построитель строк?

Question

В связи с этот вопрос , основано на комментарий пользователя Эрик Lippert .

Существует ли сценарий, в котором структура данных Rope более эффективна, чем построитель строк? По мнению некоторых людей, структуры данных веревок почти никогда не бывают лучше по скорости, чем обычные операции с строками или строителями строк, поэтому мне любопытно увидеть реалистичные сценарии, где действительно веревки лучше.

Answer 1

Документация для реализации SGI C ++ содержит некоторые подробности о поведении больших О, а константные факторы поучительны.

В их документации предполагается, что задействованы очень длинные строки , примеры, приведенные для справки, говорят о 10 МБ строках . Будет написано очень мало программ, которые имеют дело с такими вещами, и, для многих классов проблем с такими требованиями, переработав их, чтобы они были основаны на потоке , вместо того, чтобы требовать, чтобы полная строка была доступна, где это возможно, приведет к значительно превосходящим результатам , Так как такие веревки предназначены для не потокового манипулирования мульти-мегабайтными символьными последовательностями, когда вы можете соответствующим образом трактовать веревку как секции (сами веревки), а не просто как последовательность символов.

Важные плюсы:

• Конкатенация / вставка становятся операциями с почти постоянным временем
• Некоторые операции могут повторно использовать предыдущие секции веревки, чтобы обеспечить совместное использование в памяти.
  • Обратите внимание, что строки .Net, в отличие от строк Java, не разделяют символьный буфер на подстроки - выбор за и против с точки зрения использования памяти. Веревки имеют тенденцию избегать такого рода проблем.
• Веревки допускают отложенную загрузку подстрок, пока не потребуется
  • Обратите внимание, что это трудно понять правильно, очень легко сделать бессмысленным из-за чрезмерного стремления к доступу и требует использования кода, чтобы рассматривать его как веревку, а не последовательность символов.

Существенные минусы:

• Случайный доступ для чтения становится O (log n)
• Постоянные коэффициенты для последовательного доступа для чтения, кажется, между 5 и 10
• Эффективное использование API требует , рассматривая его как веревку, а не просто сбрасывая веревку в качестве вспомогательной реализации для 'нормальной' строки API.

Это приводит к нескольким «очевидным» применениям (первое упомянуто явно SGI).

• Редактировать буферы на больших файлах, позволяя легко отменить / повторить
  • Обратите внимание, что в какой-то момент вам может потребоваться записать изменения на диск, включая потоковую передачу по всей строке, так что это полезно только в том случае, если большинство изменений будут в основном храниться в памяти, а не требовать частого сохранения (например, с помощью функции автосохранения). )
• Манипуляции с сегментами ДНК, где происходят значительные манипуляции, но на самом деле происходит очень мало результатов
• Многопоточные алгоритмы, которые изменяют локальные подразделы строки. Теоретически такие случаи могут быть разделены на отдельные потоки и ядра без необходимости делать локальные копии подразделов, а затем рекомбинировать их, экономя значительную память и избегая дорогостоящей операции последовательного объединения в конце.

Существуют случаи, когда специфичное для домена поведение в строке может быть связано с относительно простыми дополнениями к реализации Rope, чтобы:

• Строки, доступные только для чтения, со значительным количеством общих подстрок, поддаются простому интернированию для значительной экономии памяти.
• Строки с разреженными структурами или значительным локальным повторением допускают выполнение кодирования длины, но при этом допускают разумные уровни произвольного доступа.
• Где границы подстрок сами являются «узлами», где информация может храниться, хотя такие структуры вполне возможно лучше сделать как Radix Trie , если они редко модифицируются, но часто читаются.

Как видно из приведенных примеров, все они попадают в категорию «нишевых». Кроме того, некоторые могут иметь превосходные альтернативы, если вместо этого вы захотите / сможете переписать алгоритм как операцию обработки потока.

Answer 2

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

(с точки зрения C #)

Структура данных веревочки в виде двоичного дерева лучше в определенных ситуациях. Когда вы смотрите на очень большие строковые значения (например, 100+ МБ XML, поступающих из SQL), структура данных веревки может удерживать весь процесс в куче больших объектов, где строковый объект попадает в него, когда он проходит 85000 байт.

Если вы смотрите на строки из 5-1000 символов, это, вероятно, недостаточно повышает производительность, чтобы того стоить. это еще один случай структуры данных, которая предназначена для 5% людей, которые находятся в экстремальных ситуациях.

Answer 3

10-й конкурс программирования ICFP опирался , в основном, на людей, использующих структуру данных веревки для эффективного решения. Это была большая хитрость, чтобы получить виртуальную машину, которая работала в разумные сроки.

Веревка отлично подходит, если есть много префиксов (очевидно, слово «предоплата» составлено ИТ-специалистами и не является подходящим словом!) И потенциально лучше для вставок; StringBuilders используют непрерывную память, поэтому эффективно работают только для добавления.

Следовательно, StringBuilder отлично подходит для построения строк путем добавления фрагментов - очень нормальный вариант использования. Поскольку разработчики должны делать это много, StringBuilders - очень распространенная технология.

Канаты отлично подходят для буферов редактирования, например структура данных, стоящая, скажем, за сильной стороной TextArea. Таким образом (ослабление Веревок, например связанный список строк, а не двоичное дерево) очень часто встречается в мире элементов управления пользовательского интерфейса, но это не часто предоставляется разработчикам и пользователям этих элементов управления.

Вам нужны действительно большие объемы данных и отток, чтобы оправдать себя - процессоры очень хороши в потоковых операциях, и если у вас есть ОЗУ, тогда просто realloc для префиксов работает приемлемо для обычных сценариев использования. Это соревнование, упомянутое сверху, было единственным разом, когда я видел, что это было необходимо.

Answer 4

Большинство продвинутых текстовых редакторов представляют текстовое тело как «вид веревки» (хотя в реализации листья обычно представляют собой не отдельные символы, а текстовые прогоны), главным образом, для улучшения частых вставок и удалений больших текстов. 1001 *

Как правило, StringBuilder оптимизирован для добавления и пытается минимизировать общее количество перераспределений , не перераспределяя слишком много. Типичная гарантия (log2 N выделений и менее чем в 2,5 раза больше памяти). Обычно строка строится один раз и затем может использоваться некоторое время без изменений.

Канат оптимизирован для частых вставок и удалений и пытается минимизировать количество копируемых данных (путем большего количества выделений). В реализации линейного буфера каждая вставка и удаление становятся O (N), и вам обычно приходится представлять вставки из одного символа.

Answer 5

Виртуальные машины Javascript часто используют веревки для строк.

Максим Шевалье-Буасверт, разработчик Javascript VM Хиггса, говорит :

В JavaScript вы можете использовать массивы строк и в конечном итоге Array.prototype.join, чтобы сделать конкатенацию строк достаточно быстрой, O (n), но «естественный» способ, которым программисты JS стремятся создавать строки, заключается в просто добавьте, используя оператор + =, чтобы постепенно построить их. JS строки неизменяемы, поэтому, если это не оптимизировано внутри, добавочное добавление O (n2). Я думаю, что вполне вероятно, что веревки были реализовано в движках JS специально из-за SunSpider тесты, которые делают добавление строк. Реализованы JS-движки веревки, чтобы получить преимущество над другими, делая что-то, что было ранее медленнее быстрее. Если бы не те тесты, я думаю что кричит от сообщества о плохом добавлении строки возможно, встречался с «используйте Array.prototype.join, dummy!».

Также .