Почему строки, как известно, дорогие

Question

Что это за способ реализации строк, который делает их настолько дорогими для манипулирования?

Разве невозможно сделать "дешевую" реализацию строки?

или я совершенно не прав в моем понимании?

Спасибо

Answer 1

Какой язык?

Строки, как правило, являются неизменяемыми, что означает, что любое изменение данных приводит к созданию новой копии создаваемой строки. Это может повлиять на производительность с большими строками.

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

Если вы беспокоитесь о производительности со строками, используйте StringBuilder (доступный в C # и Java) или другую конструкцию, которая работает с изменяемыми текстовыми данными.

Если вы работаете с большим количеством текстовых данных и нуждаетесь в мощном строковом решении, сохраняя при этом место, изучите использование канатов .

Answer 2

Многие из пунктов здесь хорошо взяты. В отдельных случаях вы можете обмануть и сделать что-то вроде использования 64-битного int для сравнения 8 байтов за раз в строке, но не так много обобщенных случаев, когда вы можете оптимизировать операции. Если у вас есть строка «стиль Паскаля» с числовым полем длины, сравнения могут быть закорочены логикой, чтобы проверять только остальную часть строки, если длина не совпадает. Другие операции обычно требуют, чтобы вы обрабатывали символы по байтам за раз или полностью копировали их при использовании. т. е. конкатенация => получить длину строки 1, получить длину строки 2, выделенную память, строку копирования 1, строку копирования 2. Можно было бы выполнить такие операции, используя контроллер DMA в строковом файле, но накладные расходы на установку это для маленьких строк перевесило бы преимущества.

Пит

Answer 3

Так как каждый раз в Java создается новая копия объекта, рекомендуется использовать StringBuffer

Синтаксис

StringBuffer strBuff=new StringBuffer();
strBuff.append("StringBuffer");
strBuff.append("is");
strBuff.append("more");
strBuff.append("economical");
strBuff.append("than");
strBuff.append("String");
String string=strBuff.tostring();

Answer 4

Проблема со строками заключается в том, что они не являются примитивными типами. Это массивы. Поэтому они испытывают те же проблемы со скоростью и памятью, что и массивы (возможно, с небольшой оптимизацией).

Теперь для «дешевых» реализаций потребуется много вещей: конкатенация, indexOf и т. Д. Есть много способов сделать это. Вы можете улучшить реализацию, но есть некоторые ограничения. Поскольку строки не являются «естественными» для компьютеров, им нужно больше памяти и медленнее манипулировать ... ВСЕГДА. Вы никогда не получите алгоритм конкатенации строк быстрее, чем любой алгоритм приличной целой суммы.

Answer 5

Изучите изменяемые строки, неизменные строки и веревки и подумайте, как бы вы реализовали общие операции на языке низкого уровня (скажем, C). Рассмотрим:

1. конкатенация.
2. нарезка.
3. Получение символа по индексу.
4. Изменение символа в индексе.
5. Поиск индекса персонажа.
6. Обход строки.

Придумав алгоритмы для этих ситуаций, вы почувствуете, когда уместен каждый тип хранилища.

Answer 6

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

Answer 7

Вы хотите прочитать эту статью Джоэла Спольски:

http://www.joelonsoftware.com/articles/fog0000000319.html

Я, я разочарован. В .NET нет собственного типа с именем F***edString.

Answer 8

Изменения и копирование строк обычно связаны с управлением памятью.

Управление памятью не очень хорошо для производительности, так как оно требует некоторого глобального мьютекса, что делает ваш код плохо масштабируемым для нескольких ядер.

Answer 9

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

Иногда вам нужна неизменность, иногда произвольный доступ, иногда быстрая вставка / удаление ...