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

11

В те дни, когда я программировал на C, я вспоминаю, что когда две строки объединяются, ОС должна выделить память для объединенной строки, затем программа может скопировать весь текст строки в новую область памяти, а затем старая память должна вручную быть выпущеным. Таким образом, если это делается несколько раз, как в случае присоединения к списку, ОС должна постоянно выделять все больше и больше памяти, просто чтобы освободить ее после следующей конкатенации. Гораздо лучшим способом сделать это в C было бы определение общего размера объединенных строк и выделение необходимой памяти для всего объединенного списка строк.

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

JSideris
источник
оставьте это компилятору и профилировщику, они позаботятся об этом, ваше время намного дороже, чем время на объединение строк.
OZ_
7
Зависит от реализации - вы действительно должны проверить документацию для вашей конкретной библиотеки строк. Можно реализовать строки, которые объединяются по ссылке за O (1) раз. В любом случае, если вам нужно объединить произвольно длинный список строк, вы должны использовать классы или функции, предназначенные для такого рода вещей.
наступающий шторм
Обратите внимание, что такие вещи, как конкатенация строк, обычно обрабатываются библиотечной функцией, а не операционной системой. ОС может участвовать в распределении памяти, но, вероятно, не для относительно небольших объектов, таких как строки.
Калеб
@Caleb ОС участвует во всем распределении памяти. Несоблюдение этого правила является типом утечки памяти. Исключение составляют случаи, когда в приложении жестко закодированы строки; они записываются в виде двоичных данных в сгенерированной сборке. Но как только вы манипулируете (или, возможно, даже назначаете) строку, она должна быть сохранена в памяти (то есть память должна быть выделена).
JSideris
4
@Bizorke В типичном сценарии распределитель памяти, такой как malloc () (который является частью стандартной библиотеки C, а не ОС), используется для выделения различных фрагментов памяти из памяти, которая уже была выделена для процесса ОС. ОС не нужно вмешиваться, если процессу не хватает памяти и не нужно запрашивать больше. Он также может принимать участие на более низком уровне, если выделение вызывает ошибку страницы. Так что да, ОС в конечном итоге обеспечивает память, но она не обязательно участвует в частичном распределении строк и других объектов внутри процесса.
Калеб

Ответы:

21

Ваше объяснение, почему оно неэффективно, является точным, по крайней мере, на языках, с которыми я знаком (C, Java, C #), хотя я бы не согласился с тем, что повсеместно распространено выполнение большого количества конкатенации строк. В C # код я работаю, есть обильное использование StringBuilder, String.Formatи т.д. , которые все памяти экономии techiniques , чтобы избежать чрезмерной перераспределению.

Поэтому, чтобы получить ответ на ваш вопрос, мы должны задать еще один вопрос: если объединение строк никогда не является проблемой, почему классы любят StringBuilderи StringBufferсуществуют ? Почему использование таких классов включено в учебники и уроки даже для начинающих? Почему, казалось бы, советы по оптимизации до такой зрелости так важны?

Если бы большинство разработчиков, объединяющих строки, основывали свой ответ исключительно на своем опыте, большинство сказали бы, что это никогда не изменится, и отказались бы от использования таких инструментов в пользу «более читабельного» for (int i=0; i<1000; i++) { strA += strB; }. Но они никогда не измеряли это.

Реальный ответ на этот вопрос может быть найден в этом SO-ответе , который показывает, что в одном случае при объединении 50 000 строк (что, в зависимости от вашего приложения, может быть обычным явлением), даже небольших, это привело к снижению производительности в 1000 раз .

Если производительность буквально ничего не значит, во что бы то ни стало, объедините все. Но я бы не согласился с тем, что использование альтернатив (StringBuilder) сложно или менее читабельно , и поэтому будет разумной практикой программирования, которая не должна вызывать защиту «преждевременной оптимизации».

ОБНОВИТЬ:

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

  1. В другом SO ответ , то точная противоположность были найдены характеристики (Array.join против + =) , чтобы быть иногда верно в JavaScript . В некоторых браузерах конкатенация строк оптимизируется автоматически, а в других - нет. Таким образом, рекомендация (по крайней мере, в этом вопросе) - просто объединить и не беспокоиться об этом.
  2. В другом случае компилятор Java может автоматически заменить конкатенацию более эффективной конструкцией, такой как StringBuilder. Однако, как отмечали другие, это является неопределенным, не гарантируется, и использование StringBuilder не ухудшает читабельность. В этом конкретном случае я бы рекомендовал не использовать конкатенацию для больших коллекций или полагаться на недетерминированное поведение компилятора Java. Точно так же в .NET оптимизация сортировки никогда не проводится.

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

Кевин Маккормик
источник
-1: содержит основной BS. strA + strBэто точно так же , как с помощью StringBuilder. Это имеет 1x хит производительности. Или 0x, в зависимости от того, как вы измеряете. Для более подробной информации, codinghorror.com/blog/2009/01/...
амара
5
@ Sparkleshy: Я предполагаю, что SO ответ использует Java, а ваша связанная статья использует C #. Я согласен с теми, кто говорит «зависит от реализации» и «измеряет это для вашей конкретной среды».
Кай Чан
1
@KaiChan: конкатенация строк в основном одинакова в java и c #
amara
3
@sparkleshy - Точка взята, но использование StringBuilder, String.Join и т. д. для объединения ровно двух строк редко когда-либо рекомендуется. Кроме того, вопрос OP касается, в частности, «содержимого коллекций , соединяемых вместе», а это не тот случай (когда StringBuilder и т. Д. Очень применим). Несмотря на это, я обновлю свой пример, чтобы быть ближе к делу.
Кевин Маккормик
3
Я не забочусь о языке для цели этого вопроса. Использование stringbuilder за кулисами в некоторых языках объясняет, почему не может быть неэффективным объединение всего списка строк, что отвечает на мой вопрос. Однако этот ответ объяснил, что присоединение к списку может быть опасным, и рекомендовал в качестве альтернативы string Builder. Я рекомендую добавить компилятор stringbuilder за кулисами к вашему ответу, чтобы избежать возможной потери репутации или неправильной интерпретации.
JSideris
2

Это не эффективно, примерно по причинам, которые вы описали. Строки в C # и Java являются неизменяемыми. Операции со строками возвращают отдельный экземпляр вместо изменения исходного, в отличие от того, что было в C. При объединении нескольких строк на каждом шаге создается отдельный экземпляр. Выделение и последующий сбор мусора неиспользованных экземпляров может привести к снижению производительности. Только на этот раз управление памятью выполняется для вас сборщиком мусора.

И C #, и Java представляют класс StringBuilder в виде изменяемой строки специально для задач этого типа. Эквивалентом в C будет использование связанного списка объединенных строк вместо их объединения в массив. C # также предлагает удобный метод Join для строк для присоединения к коллекции строк.

scrwtp
источник
1

Строго говоря, это менее эффективное использование циклов ЦП, поэтому вы правы. Но как насчет времени разработчика, затрат на обслуживание и т. Д. Если вы добавите в уравнение стоимость времени, то почти всегда эффективнее будет делать то, что проще, чем при необходимости профилировать и оптимизировать медленные биты.
«Первое правило оптимизации программы: не делай этого. Второе правило оптимизации программы (только для экспертов!): Пока не делай этого».

mattnz
источник
3
не очень эффективные правила, я думаю.
OZ_
@OZ_: Это широко используемая цитата (Майкл А. Джексон) и другие, подобные Дональду Кнуту ... Тогда есть еще одна, которую я обычно воздерживаюсь от использования "Больше вычислительных грехов совершается во имя эффективности ( не обязательно достигнув этого), чем по любой другой единственной причине - включая слепую глупость. "
Mattnz
2
Я должен отметить, что Майкл Джексон был британцем, так что это Оптимизация, а не Оптимизация . В какой-то момент я действительно должен исправить страницу википедии . * 8 ')
Марк Бут
Я полностью согласен, вы должны исправить эти орфографические ошибки. Несмотря на то, что мой родной язык - английский Квинс, мне легче говорить по-американски во внутренней сети .......
mattnz
не будет ли кто-нибудь думать о пользователях. Вы можете сделать это немного быстрее для разработчика, но тогда каждый из ваших клиентов страдает от этого. Напишите свой код для них, а не для вас.
gbjbaanb
1

Очень сложно что-либо сказать о производительности без практического теста. Недавно я был очень удивлен, обнаружив, что в JavaScript наивная конкатенация строк обычно выполняется быстрее, чем рекомендуемое решение «составить список и объединить» (протестируйте здесь , сравните t1 с t4). Я все еще озадачен тем, почему это происходит.

Вот несколько вопросов, которые вы можете задать, рассуждая о производительности (особенно об использовании памяти): 1) насколько велик мой вклад? 2) насколько умен мой компилятор? 3) как моя среда выполнения управляет памятью? Это не является исчерпывающим, но это отправная точка.

  1. Насколько велик мой вклад?

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

  2. Насколько умен мой компилятор?

    Многие компиляторы достаточно умны, чтобы «оптимизировать» переменные, которые записываются, но никогда не читаются. Аналогичным образом, хороший компилятор также может преобразовать наивную конкатенацию строк в (базовую) библиотеку, и, если многие из них создаются без каких-либо операций чтения, нет необходимости преобразовывать их обратно в строку между этими операциями (даже если ваш исходный код, кажется, делает именно это). Я не могу сказать, делают ли это какие-либо компиляторы или в какой степени это делается (AFAIK Java по крайней мере заменяет несколько конкатов в одном выражении на последовательность операций StringBuffer), но это возможно.

  3. Как моя среда выполнения управляет памятью?

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

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

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

mgibsonbr
источник
Да, я согласен, что это определенно та область, где компилятор может теоретически понять, что вы пытаетесь добавить кучу строк вместе, а затем оптимизировать, как если бы вы использовали построитель строк. Однако это вряд ли тривиальная вещь, и я не думаю, что это реализовано в каких-либо современных компиляторах. Вы только что дали мне отличную идею для исследовательского проекта для студентов: D.
JSideris
Проверьте этот ответ , компилятор Java уже использует StringBuilderего внутри, все, что ему нужно сделать, это не вызывать toStringдо тех пор, пока переменная действительно не понадобится. Если я правильно помню, он делает это для одного выражения, мое единственное сомнение - применимо ли это к нескольким операторам в одном и том же методе. Я ничего не знаю о внутренностях .NET, но я верю, что подобная стратегия может быть использована и компилятором C #.
mgibsonbr
0

Джоэл написал отличную статью на эту тему некоторое время назад. Как отмечали некоторые другие, это сильно зависит от языка. Из-за способа реализации строк в C (с нулевым символом в конце, без поля длины) стандартная процедура библиотеки strcat очень неэффективна. Джоэл представляет альтернативу с небольшим изменением, которое намного эффективнее.

tcrosley
источник
-1

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

Нет.

Вы читали «Печальную трагедию театра микрооптимизации» ?

Джим Г.
источник
4
«Преждевременная оптимизация - корень всего зла». - Кнут
Скотт С. Уилсон
4
Корень зла в оптимизации берет эту фразу без контекста.
OZ_
Просто сказать, что что-то является правдой без указания каких-либо вспомогательных причин, не полезно на таком форуме.
Эдвард Стрендж,
@Crazy Eddie: Вы читали, почему Джефф Этвуд должен был сказать?
Джим Г.