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

Question

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

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

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

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

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

UPD2: Серьезно, вопрос не в том, как сделать лучше. Я даже больше не использую строки STL в этом случае. Неудивительно, что сравнение длины не нужно, неправильно и т. Д. Интересно, что в одном конкретном тесте он действительно работает немного лучше. Как это возможно?

Answer 1

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

Answer 2

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

Оптимизация короткого замыкания может быть полезна только тогда, когда:

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

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

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

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

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

S + F * (1-P)

1021 * т.е. *

S

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

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

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

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

Ваш случай

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

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

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

Answer 9

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