С самого моего первого урока программирования в старшей школе я слышал, что строковые операции медленнее - то есть более дорогостоящие - чем мифическая «средняя операция». Почему делает их такими медленными? (Этот вопрос оставлен намеренно широким.)

«Средняя операция» происходит на примитивах. Но даже в языках, где строки обрабатываются как примитивы, они все еще являются массивами под капотом, и выполнение всего, что включает в себя всю строку, занимает O (N) времени, где N - длина строки.

Например, для добавления двух чисел обычно требуется 2-4 инструкции ASM. Конкатенация («добавление») двух строк требует нового выделения памяти и одной или двух строковых копий, включая всю строку.

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

^{Это старая ветка, и я думаю, что другие ответы великолепны, но что-то упускают из виду, так что вот мои (поздние) 2 цента.}

Синтаксическая сложность шкур сахарного покрытия

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

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

Детали реализации

Хороший ол

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

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

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

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

Таким образом, разные языки используют разные подходы к этим вопросам. Например, Java взяла на себя смелость сделать свои строки неизменяемыми по ряду веских причин (длина кэширования, безопасность потоков) и для своих изменяемых аналогов (StringBuffer и StringBuilder) выберет распределение размера с использованием блоков большего размера, чтобы не нужно было выделять каждый раз, но, скорее, надежда на лучшие сценарии. Обычно это работает хорошо, но недостатком является то, что иногда приходится платить за воздействие памяти.

Поддержка Юникода

Кроме того, и опять же, это связано с тем, что синтаксическое сахарное покрытие вашего языка скрывает это от вас, чтобы играть хорошо, вы часто не думаете, что это с точки зрения поддержки юникода (особенно если вам это действительно не нужно) и ударил эту стену). И некоторые языки, будучи дальновидными, не реализуют строки с базовыми массивами простых 8-битных примитивов char. Они выпекаются в UTF-8 или UTF-16 или в том, что у вас есть, и следствием этого является чрезвычайно большое потребление памяти, которое зачастую не требуется, и большее время обработки для выделения памяти, обработки строк, и реализовать всю логику, которая идет рука об руку с манипулированием кодами.

Результатом всего этого является то, что когда вы делаете что-то эквивалентное в псевдокоде:

hello = "hello,"
world = " world!"
str = hello + world

Это может быть не так - несмотря на все усилия, которые прикладывают языковые разработчики, чтобы заставить их вести себя так, как вы бы хотели, - просто:

a = 1;
b = 2;
shouldBeThree = a + b

В качестве продолжения вы можете прочитать:

• Неэффективно ли объединять строки по одной?

Фраза «средняя операция», вероятно, является сокращением для одной операции теоретического компьютера с хранимой программой произвольного доступа . Это теоретическая машина, которую обычно используют для анализа времени выполнения различных алгоритмов.

Общими операциями обычно считаются загрузка, сложение, вычитание, сохранение, ветвление. Возможно также прочитать, распечатать и остановить.

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

Это полностью зависит от операции, как представлены строки и какие существуют оптимизации. Если строки имеют длину 4 или 8 байт (и выровнены), они не обязательно будут медленнее - многие операции будут такими же быстрыми, как примитивы. Или, если все строки имеют 32-битный или 64-битный хэш, многие операции также будут такими же быстрыми (хотя вы оплачиваете стоимость хэширования заранее).

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

Позвольте мне ответить на ваш вопрос с вопросом. Почему произнесение последовательности слов занимает больше времени, чем произнесение одного слова?