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