Сравнение строк в C

[BratSinot]

Доброго времени суток!

Можно ли как-нибудь сравнить строки посредством оператора switch? Или это можно только в C++ посредством переменной string? В принципе можно и if-then-else+strcmp обойтись, но switch поприличнее смотриться.

[watashiwa_daredeska]

Можно ли как-нибудь сравнить строки посредством оператора switch?

Имеется в виду использование строк в case? Нельзя.

Или это можно только в C++ посредством переменной string?

И это тоже нельзя. Тот, кто Вам это сказал — жестоко обманул.

[drBatty]

В принципе можно и if-then-else+strcmp обойтись, но switch поприличнее смотриться.

case смотрится уродливо на уровне кода. (в х86 во всяком случае).

строки можно сравнивать strcmp() & stricmp() & strncmp() и т.д.

Или это можно только в C++ посредством переменной string?

И это тоже нельзя. Тот, кто Вам это сказал — жестоко обманул.

наверное имелась ввиду STL...
ей можно, но, насколько я знаю, это обёртка над strcmp().

[eddy]

ей можно, но, насколько я знаю, это обёртка над strcmp().

Так и switch является оберткой над if(x==xi) goto yi; // ассемблера не знаю, поэтому сишный аналог пишу

[watashiwa_daredeska]

наверное имелась ввиду STL...
ей можно

М-м-м… Покажите, пожалуйста. А то я за 10 лет так и не узнал, как использовать строки (хоть и STL) в селекторах switch. Или это какая-то нвомодная фишка C++0x?

[Lan4]

есть два варианта, но не напрямую.
вот тут рас: http://forum.sources.ru/index.php?showtopic=72650
второй вариант - сравнивать не строки, а хеш-коды этих строк.

[watashiwa_daredeska]

вот тут рас

Там сразу целых 2. std::map — это хорошо, но ведь не строки же в switch, правда? Да и в C можно аналогичный вариант провернуть, особенно если воспользоваться какой-нибудь GLib.
Вариант с заменой switch на if вообще никуда не годится, ибо каждый, кто хоть раз в жизни видел, во что компилится switch, знает, что эти записи не эквивалентны.

сравнивать не строки, а хеш-коды этих строк.

Никуда не годится. Выигрыш от варианта с map минимален, но теряется 100% гарантия совпадения.

[Lan4]

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

согласен.

Никуда не годится. Выигрыш от варианта с map минимален, но теряется 100% гарантия совпадения.

как вариант можно написать хорошую хеш-функцию, особенно зная "структуру" исходных строк.

[eddy]

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

А разве он не в if ... goto преобразуется?

[watashiwa_daredeska]

как вариант можно написать хорошую хеш-функцию, особенно зная "структуру" исходных строк.

А в чем бенефит?

std::hash_map/std::map IMHO лучший вариант. Использование switch подразумевает перечислимость, а значит эти строки, по хорошему, нужно конвертировать в enum как можно раньше, а не каждый раз перед switch. Т.е. завести пару конверторов: строка→enum и enum→строка (если нужен) и счастливо жить внутри программы с enum'ом.

[NickLion]

Никуда не годится. Выигрыш от варианта с map минимален, но теряется 100% гарантия совпадения.

как вариант можно написать хорошую хеш-функцию, особенно зная "структуру" исходных строк.

Уж лучше заюзать расширение hash_map - такое решение хоть надёжно (правда могут быть проблемы с переносом на другой компилер).

[watashiwa_daredeska]

А разве он не в if ... goto преобразуется?

В некотором роде да, но с особенностями. Обычный if…else if… — это линейный поиск, O(n), а switch преобразуется в бинарный поиск, O(log n). Т.е. при, скажем, 16 case'ах в первом случае (if) получим ~8 сравнений в среднем, а во втором (switch) ~4 сравнения. В предположении равновероятности каждого варианта, естественно.

[NickLion]

А разве он не в if ... goto преобразуется?

В некотором роде да, но с особенностями. Обычный if…else if… — это линейный поиск, O(n), а switch преобразуется в бинарный поиск, O(log n). Т.е. при, скажем, 16 case'ах в первом случае (if) получим ~8 сравнений в среднем, а во втором (switch) ~4 сравнения. В предположении равновероятности каждого варианта, естественно.

Более того, если идут значение по порядку (например, от 0 до 15), то генерируется просто таблица указателей, с асимптотикой O(1). Но это всё, естественно, зависит от оптимизаций компилятора.

[drBatty]

Так и switch является оберткой над if(x==xi) goto yi;

никто не заставляет использовать if(...) goto ..., можно использовать например массив указателей на функцию.

М-м-м… Покажите, пожалуйста. А то я за 10 лет так и не узнал, как использовать строки (хоть и STL) в селекторах switch. Или это какая-то нвомодная фишка C++0x?

речь шла об if конечно. насколько я знаю, по стандарту case работает только с целыми числами типа int.

сравнивать не строки, а хеш-коды этих строк.

Никуда не годится. Выигрыш от варианта с map минимален, но теряется 100% гарантия совпадения.

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

А разве он не в if ... goto преобразуется?

в том-то и дело, что switch/case преобразуется в jmp всегда, а вот if может и оптимизироваться (насколько я знаю, конструкцию case компиляторы оптимизируют хуже, если вообще её оптимизируют).

а switch преобразуется в бинарный поиск

то генерируется просто таблица указателей

да ладно! что, gcc уже ТАКОЕ умеет? правда?
а я и не знал...

[eddy]

да ладно! что, gcc уже ТАКОЕ умеет? правда?
а я и не знал...

Я тоже думаю, что gcc просто преобразует switch в последовательность операторов условных переходов. Т.е. поиск идет линейно.

[watashiwa_daredeska]

а с коллизиями можно работать, это не настолько страшно.

Это как это?

во всяком случае куда как быстрее сравнить 2 целых числа, чем 2 строчки неограниченной длинны.

А hash_map не? А раз уж речь идет об использовании в switch, то можно предположить, что набор строк постоянен, а значит можно заранее сгенерить вообще DFA, который без лишних накладных расходов будет работать за O(max(len(const))).

Я тоже думаю, что gcc просто преобразует switch в последовательность операторов условных переходов. Т.е. поиск идет линейно.

Нет. Я смотрел :)

[drBatty]

Это как это?

ну скажем у вас есть строка в 100 байтов, и вам надо её сравнить со 100 образцами (тоже в 100 байт). Очевидно, вам надо обработать 100*100 == 10000 байт, что-бы найти образец, или установить, что строка не подходит (конечно на практике нужно обработать намного меньше, т.к. сравнение часто можно закончить на первом или втором символе, и тем не менее, асимптота именно такая).

Попробуйте иначе - посчитайте хеш от строки длинной в 1 байт. Вам понадобится обработать всего 100 байт для этого. Теперь достаточно написать 100 функций обработки, и массив этих функций, по одной на каждый хеш образца (плюс ещё 156 указателей на функцию, которая выполняется в случае несовпадения). Переход будет осуществлён одной ассемблерной командой - косвенный вызов подпрограммы.

Возможна (но мало вероятна) коллизия - две строки имеют один и тот-же хеш. Ничего страшного, у нас будет не 101, а 100 функций, одна из которых обрабатывает 2 образца. (проверяет например той-же strcmp() строчку).

Т.о. мы уменьшили максимальное время выполнения в 100 раз. Разве это плохой результат?

Среднее время выполнения также резко уменьшится (хотя и не в 100 раз).

А hash_map не?

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

[NickLion]

да ладно! что, gcc уже ТАКОЕ умеет? правда?
а я и не знал...

Код программы:

Код: Выделить всё

#include <stdio.h>

int main()
{
    int n;
    scanf( "%d", &n );
    switch( n ) {
    case 0:
        printf( "Hello Zero!\n" );
        break;
    case 1:
        printf( "Hello One!\n" );
        break;
    case 2:
        printf( "Hello Two!\n" );
        break;
    case 3:
        printf( "Hello Three!\n" );
        break;
    case 4:
        printf( "Hello Four!\n" );
        break;
    case 5:
        printf( "Hello Five!\n" );
        break;
    case 6:
        printf( "Hello Six!\n" );
        break;
    case 7:
        printf( "Hello Seven!\n" );
        break;
    case 8:
        printf( "Hello Eight!\n" );
        break;
    case 9:
        printf( "Hello Nine!\n" );
        break;
    case 10:
        printf( "Hello Ten!\n" );
        break;
    case 11:
        printf( "Hello Eleven!\n" );
        break;
    case 12:
        printf( "Hello Twelve!\n" );
        break;
    }
    return 0;
}

Компилилось g++ -O3 -g0

Получено из gdb (коменты мои):

Код: Выделить всё

Dump of assembler code for function main:
   0x00000000004005f0 <+0>:     sub    $0x18,%rsp
   0x00000000004005f4 <+4>:     xor    %eax,%eax
   0x00000000004005f6 <+6>:     mov    $0x4007ec,%edi
   0x00000000004005fb <+11>:    lea    0xc(%rsp),%rsi
вызываем scanf
   0x0000000000400600 <+16>:    callq  0x4004e8 <scanf@plt>
проверям на диапазон
   0x0000000000400605 <+21>:    cmpl   $0xc,0xc(%rsp)
   0x000000000040060a <+26>:    ja     0x400630 <main+64>
загружаем значение из памяти в регистр
   0x000000000040060c <+28>:    mov    0xc(%rsp),%eax
а вот и переход по табличке
   0x0000000000400610 <+32>:    jmpq   *0x400890(,%rax,8)
   0x0000000000400617 <+39>:    nopw   0x0(%rax,%rax,1)
   0x0000000000400620 <+48>:    mov    $0x400880,%edi
   0x0000000000400625 <+53>:    callq  0x4004c8 <puts@plt>
   0x000000000040062a <+58>:    nopw   0x0(%rax,%rax,1)
   0x0000000000400630 <+64>:    xor    %eax,%eax
   0x0000000000400632 <+66>:    add    $0x18,%rsp
   0x0000000000400636 <+70>:    retq
   0x0000000000400637 <+71>:    nopw   0x0(%rax,%rax,1)
   0x0000000000400640 <+80>:    mov    $0x400872,%edi
   0x0000000000400645 <+85>:    callq  0x4004c8 <puts@plt>
   0x000000000040064a <+90>:    jmp    0x400630 <main+64>
   0x000000000040064c <+92>:    nopl   0x0(%rax)
   0x0000000000400650 <+96>:    mov    $0x4007ef,%edi
   0x0000000000400655 <+101>:   callq  0x4004c8 <puts@plt>
   0x000000000040065a <+106>:   jmp    0x400630 <main+64>
   0x000000000040065c <+108>:   nopl   0x0(%rax)
   0x0000000000400660 <+112>:   mov    $0x4007fb,%edi
   0x0000000000400665 <+117>:   callq  0x4004c8 <puts@plt>
   0x000000000040066a <+122>:   jmp    0x400630 <main+64>
   0x000000000040066c <+124>:   nopl   0x0(%rax)
   0x0000000000400670 <+128>:   mov    $0x400806,%edi
   0x0000000000400675 <+133>:   callq  0x4004c8 <puts@plt>
   0x000000000040067a <+138>:   jmp    0x400630 <main+64>
   0x000000000040067c <+140>:   nopl   0x0(%rax)
   0x0000000000400680 <+144>:   mov    $0x400811,%edi
   0x0000000000400685 <+149>:   callq  0x4004c8 <puts@plt>
   0x000000000040068a <+154>:   jmp    0x400630 <main+64>
   0x000000000040068c <+156>:   nopl   0x0(%rax)
   0x0000000000400690 <+160>:   mov    $0x40081e,%edi
   0x0000000000400695 <+165>:   callq  0x4004c8 <puts@plt>
   0x000000000040069a <+170>:   jmp    0x400630 <main+64>
   0x000000000040069c <+172>:   nopl   0x0(%rax)
   0x00000000004006a0 <+176>:   mov    $0x40082a,%edi
   0x00000000004006a5 <+181>:   callq  0x4004c8 <puts@plt>
   0x00000000004006aa <+186>:   jmp    0x400630 <main+64>
   0x00000000004006ac <+188>:   nopl   0x0(%rax)
   0x00000000004006b0 <+192>:   mov    $0x400836,%edi
   0x00000000004006b5 <+197>:   callq  0x4004c8 <puts@plt>
   0x00000000004006ba <+202>:   jmpq   0x400630 <main+64>
   0x00000000004006bf <+207>:   nop
   0x00000000004006c0 <+208>:   mov    $0x400841,%edi
   0x00000000004006c5 <+213>:   callq  0x4004c8 <puts@plt>
   0x00000000004006ca <+218>:   jmpq   0x400630 <main+64>
   0x00000000004006cf <+223>:   nop
   0x00000000004006d0 <+224>:   mov    $0x40084e,%edi
   0x00000000004006d5 <+229>:   callq  0x4004c8 <puts@plt>
   0x00000000004006da <+234>:   jmpq   0x400630 <main+64>
   0x00000000004006df <+239>:   nop
   0x00000000004006e0 <+240>:   mov    $0x40085b,%edi
   0x00000000004006e5 <+245>:   callq  0x4004c8 <puts@plt>
   0x00000000004006ea <+250>:   jmpq   0x400630 <main+64>
   0x00000000004006ef <+255>:   nop
   0x00000000004006f0 <+256>:   mov    $0x400867,%edi
   0x00000000004006f5 <+261>:   callq  0x4004c8 <puts@plt>
   0x00000000004006fa <+266>:   jmpq   0x400630 <main+64>
End of assembler dump.

PS с g++ -O2 -g0 та же картина

[BratSinot]

Блин, можно сделать все проще, не strcmp сравнивать, а 1 сравнивать с strcmp. Т.е.:

Код: Выделить всё

switch(1)
{
 case strcmp("qwe", "qwe"):
 break;
}

[eddy]

case strcmp("qwe", "qwe"):

Не будет работать, там константы должны быть.

[drBatty]

Блин, можно сделать все проще, не strcmp сравнивать, а 1 сравнивать с strcmp. Т.е.:

это маздайный подход:

RETURN VALUE
The strcmp() and strncmp() functions return an integer less than, equal to, or greater than zero if s1
(or the first n bytes thereof) is found, respectively, to be less than, to match, or be greater than s2.

не написано, что возвращает 1. а значит, в некоторых версиях может быть и не 1.
(ЕМНИП в MSVC6 было не 1. точнее не всегда 1)

[BratSinot]

Блин, можно сделать все проще, не strcmp сравнивать, а 1 сравнивать с strcmp. Т.е.:

это маздайный подход:

RETURN VALUE
The strcmp() and strncmp() functions return an integer less than, equal to, or greater than zero if s1
(or the first n bytes thereof) is found, respectively, to be less than, to match, or be greater than s2.

не написано, что возвращает 1. а значит, в некоторых версиях может быть и не 1.
(ЕМНИП в MSVC6 было не 1. точнее не всегда 1)

А я сделаю (_Bool)<переменная> =)
В конце концов сделать небольшую обертку для strcmp не сложно.
Хотя, зараза, не работает.

[drBatty]

А я сделаю (_Bool)<переменная> =)

а разве где-то сказано, что true == 1? Логичнее считать, что -1. ИМХО.

Хотя, зараза, не работает.

если-бы работало, компилятор не смог-бы сворачивать case'ы в jamp'ы. видимо потому и сделано было только константы. и только целые числа.