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

Ответ 1

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

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

Значительные профи:

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

Значительные минусы:

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

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

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

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

Ответ 5

Javascript VM часто используют веревки для строк.

Maxime Chevalier-Boisvert, разработчик Viagra Javascript VM, говорит:

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

Также.