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

Question

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

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

Answer 1

Документация для Реализация SGI C ++ Вдается некоторым деталям о Big O Behaviors стихи о постоянных факторах, которые являются поучительными.

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

Значительные плюсы:

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

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

Answer 5

VMS JavaScript часто использует веревки для строк.

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

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

Также.