if(str1==str2) и if(str1.length()==str2.length() && str1==str2)

Question

Я видел второе в чужом коде и полагаю, что это сравнение длины было сделано для повышения производительности кода.Он использовался в парсере скриптового языка с определенным словарем:слова имеют длину от 4 до 24 букв, в среднем 7-8 букв, алфавит включает 26 латинских букв плюс «@», «$» и «_».

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

Я провел несколько тестов и вот что выяснил:При тестировании сравнения двух случайных строк миллион раз второй способ намного быстрее, поэтому сравнение длины кажется полезным.Но в работающем проекте он работает ещё медленнее в режиме отладки и недостаточно быстрее в режиме релиза.

Итак, мой вопрос:почему сравнение длин может ускорить сравнение и почему оно может его замедлить?

УПД:Второй способ мне тоже не нравится, но, полагаю, это было сделано по какой-то причине, и мне интересно, что это за причина.

УПД2:Серьезно, вопрос не в том, как сделать лучше.В этом случае я даже больше не использую строки STL.Неудивительно, что сравнение длин ненужно, неправильно и т. д.Удивительно то, что в одном конкретном тесте он действительно работает немного лучше.Как это возможно?

Answer 1

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

Answer 2

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

Answer 3

Когда короткое замыкание может быть полезным

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

• стоимость сравнения невысока по сравнению со стоимостью полного теста
• сравнение часто приводит к короткому замыканию

Математически пусть S — стоимость состояния короткого замыкания, F — стоимость полного состояния, а P — процент случаев, когда происходит короткое замыкание (полное состояние не обязательно).

Средняя стоимость оригинального корпуса (без короткого замыкания) составляет F.

Средняя стоимость оптимизации короткого замыкания равна S + F * (1-P).

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

S + F * (1-P) < F

то есть

С < Ф*П

Стоимость сравнения строк

Далее вы написали:

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

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

Ваш случай

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

Answer 4

Как правило, вы должны оставить это STL и не беспокоиться об этом.

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

Это было бы лучше, чем "оптимизация", разбросанная по всему коду.

Answer 5

Реализация оператора std :: string == не может определить, быстрее ли будет сначала проверить длину или начать проверять символы. Четкая проверка длины - пустая трата строк одинаковой длины. Поэтому разные реализации STL могут работать по-разному.

Включите явную проверку длины только в качестве окончательной оптимизации (с таким комментарием), и только если ваш профилировщик подтвердит преимущество.

Answer 6

сравнение длины не имеет для меня никакого смысла .. достаточно использовать оператор сравнения

Answer 7

запустить вашу реализацию STL. Это не должно иметь значения

Answer 8

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

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

Код выполнит сравнение длины, потерпит неудачу, затем проигнорирует полное сравнение строк и пропустит код.

Answer 9

Длина std :: string, скорее всего, является членом объекта std :: string. Для сравнения, первый персонаж вполне может быть в куче. Это означает, что сравнение длины строки улучшает местность ссылки. Конечно, с оптимизацией коротких строк это становится еще более сложным - Lhs [0] может быть в куче, а Rhs [0] в стеке.