Сравнение строк: strcmp или посимвольно. Benchmark
Я искал ответ на вопрос «что быстрее» strcmp (in, «first») == 0 или strlen (in) == 5 && in[0] == 'f' && in[1] == 'i' && in[2] == 'r' && in[3] == 's' && in[4] == 't' И, кажется, нашёл…
Задача Проверить, не является ли строка «специальным маркером». Всего маркеров пять: «first», «last», «even», «odd», «exit», причём по «exit» программа завершается.За те несколько дней что я изучаю C, я встречал два подхода к сравнению: функцией strcmp и побайтово (ака посимвольно). Мнения знакомых и коллег о том, какой подход работает быстрее, разделились. Значит нужен benchmark.
Исходники
Решение, использующее strcmp, я буду называть bench_str:
#include
int main () { char in[100] = »;
while (scanf (»%s», in)) { if (strcmp (in, «first») == 0) { printf («F\n»); } else if (strcmp (in, «last») == 0) { printf («L\n»); } else if (strcmp (in, «odd») == 0) { printf («O\n»); } else if (strcmp (in, «even») == 0) { printf («E\n»); } else if (strcmp (in, «exit») == 0) { return 0; } else { printf («unknown\n»); } }
return 0; } Решение, использующее побайтовое сравнение, я буду называть bench_char:
#include
int main () { char in[100] = »;
while (scanf (»%s», in)) { if (strlen (in) == 5 && in[0] == 'f' && in[1] == 'i' && in[2] == 'r' && in[3] == 's' && in[4] == 't') { printf («F\n»); } else if (strlen (in) == 4 && in[0] == 'l' && in[1] == 'a' && in[2] == 's' && in[3] == 't') { printf («L\n»); } else if (strlen (in) == 3 && in[0] == 'o' && in[1] == 'd' && in[2] == 'd') { printf («O\n»); } else if (strlen (in) == 4 && in[0] == 'e' && in[1] == 'v' && in[2] == 'e' && in[3] == 'n') { printf («E\n»); } else if (strlen (in) == 4 && in[0] == 'e' && in[1] == 'x' && in[2] == 'i' && in[3] == 't') { return 0; } else { printf («unknown\n»); } }
return 0; } Компилятся и работают они одинаково корректно:
$ gcc -Wall -o ./bin/bench_str bench_str.c && ./bin/bench_str some unknown first F last L exit
$ gcc -Wall -o ./bin/bench_char bench_char.c && ./bin/bench_char any unknown odd O even E exit Входные данные Используйте ваш любимый скриптовый язык для создания файла, содержащего изрядное число входных строк. Мне понадобилось 10M строк для того, чтобы время исполнения занимало несколько секунд. На меньших интервалах разница в скорости может быть не так заметна, и влияние прочих процессов, отжирающих ваш CPU, будет сказываться сильнее.Я сделал make_input.php:
for ($i = 0; $i < 10000000; $i++) { $str = $variants[array_rand($variants)]; echo $str . PHP_EOL; }
echo «exit» . PHP_EOL; $ php make_input.php >/tmp/input Обратите внимание, поскольку input читается бесконечно while (scanf (»%s», in)), последней строкой в файле идёт «exit» — иначе программа зациклится.
Таким набором я пытался добиться максимального разнообразия входных строк: есть неподходящие по длине, есть начинающиеся с «неправильных» букв, есть строки с «неправильными» концами, ну и, наконец, есть подходящие строки.
Push the button, Max! Выполняем! Я перенаправил вывод в /dev/null, чтобы не тратить ресурсы на вывод результата на экран: это тоже вносит погрешность и занимает приличное время. Если не собираетесь перенаправлять вывод, я рекомендую уменьшить число входных строк на порядок или два.Итак, на сцене побайтовое сравнение:
$ time ./bin/bench_char /dev/null
real 0m2.962s user 0m2.908s sys 0m0.048s I’d like to see the Great Leslie try THAT one! ©
На сцене strcmp:
$ time ./bin/bench_str /dev/null
real 0m2.495s user 0m2.448s sys 0m0.036s Конечно, от запуска к запуску результаты немного варьируются, но в целом картина не меняется: strcmp примерно на полсекунды быстрее, а это около 20%! И я даже молчу о читаемости кода.
В качестве крайних кейсов можно оставить только корректные строки или только некорректные.
В случае использования только корректных строк, время выполнения обеих реализаций сокращается, и преимущество strcmp падает до 15%:
$ time ./bin/bench_char /dev/null
real 0m2.026s user 0m1.992s sys 0m0.028s
$ time ./bin/bench_str /dev/null
real 0m1.739s user 0m1.720s sys 0m0.012s В случае использования только некорректных строк, время выполнения bench_char практически не меняется, а вот bench_str выполняется немного дольше.В целом преимущество strcmp падает примерно до 10%:
$ time ./bin/bench_char /dev/null
real 0m2.986s user 0m2.936s sys 0m0.044s
$ time ./bin/bench_str /dev/null
real 0m2.722s user 0m2.676s sys 0m0.032s Картинка к этому делу:
Case #1: только правильные строкиCase #2: миксCase #3: только неправильные
Если кто-то знает почему я не прав и в каком случае будет обратная картина — будет очень интересно расширить кругозор.Но если кто-то подробно расскажет почему так, будет вообще суперски!
Спасибо за внимание!
