эффективный и переносимый strcmp для обратных строк

strcmp, по крайней мере, с использованием g++, имеет множество оптимизаций для многих архитектур. На моем компьютере Core2Duo E8400 strcmp в два раза быстрее, чем использование прямой реализации.

Мой вопрос, существует ли какая-то библиотека, которая предоставляет функцию, которая сравнивает две «обратные строки». Обратная строка char *s1 начинается в s1 и заканчивается в некотором s1-n таком, что s1-n == '\0' (где n >= 0 и для всех 0 <= n' < n, s1-n' != '\0').

Конечно, требования заключаются в том, что эта функция должна быть такой же эффективной и переносимой, как strcmp.

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


c performance strcmp
person user1476999    schedule 24.09.2012    source источник
comment
Готов поспорить, что ответ НЕТ. Строки с завершающим нулем распространены. Строки, которые начинаются с \0, практически не встречаются. Итак, кто пишет библиотеку для таких необычных вещей?   -  person MSalters    schedule 24.09.2012
comment
Это одно из самых странных требований, которые я видел! :)   -  person unwind    schedule 24.09.2012
comment
Я уверен, что это можно сделать, но не могу найти такую ​​реализацию. Удачи.   -  person Bob Jarvis - Reinstate Monica    schedule 24.09.2012
comment
Почему вы не можете взять существующий исходный код для strcmp() и уменьшить два указателя ввода вместо увеличения? fossies.org/dox/glibc-2.16.0/strcmp_8c_source.html   -  person Alex Reynolds    schedule 24.09.2012
comment
@AlexReynolds, это не оптимизированная версия. Читая исполняемый файл с помощью objdump, strcmp (с -O3 в моей среде), я вижу, что получают прибыль от векторных расширений (на самом деле, сначала сделайте некоторую проверку, чтобы узнать, какие из них доступны).   -  person user1476999    schedule 24.09.2012
comment
@MSalters предполагает, что вам нужно сравнить множество строк, и вы знаете, что с высокой вероятностью они имеют длинный префикс-запятую. Тогда лучшая стратегия — начать сравнивать с конца к началу. Я думаю, что это не необычная проблема.   -  person user1476999    schedule 24.09.2012
comment
@ user1476999: О, конечно нет. Но все же вы бы сохранили эти строки с \0 LAST. т.е. X-xiferp\0, Y-xiferp\0 и т.д. И тогда можно использовать обычный strcmp.   -  person MSalters    schedule 24.09.2012
comment
Или, если вам разрешено изменять представление, возможно, вы могли бы хранить указатели на начало и конец строки (эквивалентно начало и длина). Спасает от необходимости реверсировать его, как в представлении MSalter. Затем напишите в обратном порядке memcmp. Компилятор может лучше справиться с автоматической векторизацией, чем ваш обратный strcmp (я предполагаю, что он не удался на вашем обратном-strcmp).   -  person Steve Jessop    schedule 24.09.2012

Ответы (2)


arrow_upward
1
arrow_downward

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

person fkl    schedule 24.09.2012

arrow_upward
0
arrow_downward

Если бы у меня была твоя проблема, обратная strcmp, я бы просто написал. Не беспокойтесь о скорости по нескольким причинам.

Во-первых, программы, имеющие strcmp в качестве существенного "узкого места", встречаются редко.

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

person Mike Dunlavey    schedule 24.09.2012
comment
Я уже написал обратный strcmp. Я измерил производительность своей программы, и если я смогу использовать функцию, оптимизированную как strcmp, я уменьшу загрузку процессора примерно на 5%, не больше, но без отрицательных аналогов. - person user1476999; 24.09.2012
comment
С того места, где я сижу, 5% — это довольно мало. Скорее всего, есть что-то большее, чтобы исправить. - person Mike Dunlavey; 24.09.2012