Есть ли любой сценарий, где структура данных Веревки более эффективна, чем строковый разработчик

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

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

• Обратите внимание, что строки .Net, в отличие от строк java, не разделяют символьный буфер на подстроки - выбор с плюсами и минусами с точки зрения объема памяти. Веревки, как правило, позволяют избежать подобных проблем.

Веревки позволяют отложить загрузку подстрок до тех пор, пока они не потребуются.

• Обратите внимание, что это сложно сделать правильно, очень легко сделать бессмысленным из-за чрезмерного желания доступа и требует использования кода, чтобы рассматривать его как веревку, а не как последовательность символов.

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

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

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

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

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

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

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

Строки с разреженными структурами или значительным локальным повторением поддаются кодированию длины прогона, при этом позволяя разумные уровни произвольного доступа.

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

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

Строки с разреженными структурами или значительным локальным повторением поддаются кодированию длин серий, при этом позволяя разумные уровни произвольного доступа.

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

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

где может храниться информация, хотя такие структуры вполне возможно лучше сделать в виде Radix Trie , если они редко изменяются, но часто читаются.

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

где может храниться информация, хотя такие структуры вполне возможно лучше сделать в виде Radix Trie , если они редко изменяются, но часто читаются.

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