Пользователь
0,0
рейтинг
23 января 2013 в 08:01

Разработка → Switch для строк в C++11

К сожалению, стандарт C++ не допускает применения операторов switch-case к строковым константам. Хотя в других языках, вроде C#, такая возможность имеется прямо «из коробки». Поэтому, понятное дело, многие C++ программисты пытались написать свою версию «switch для строк» — и я не исключение.
Для C++03 решения не отличались красотой и лишь усложняли код, дополнительно нагружая приложение в рантайме. Однако с появлением C++11 наконец-то появилась возможность реализовать такой код:

   std::string month;
   std::string days;

   std::cout << "Enter month name: ";
   std::cin  >> month;

   SWITCH (month)
   {
   CASE("february"):
       days = "28 or 29";
       break;

   CASE("april"):
   CASE("june"):
   CASE("september"):
   CASE("november"):
       days = "30";
       break;

   CASE("january"):
   CASE("march"):
   CASE("may"):
   CASE("july"):
   CASE("august"):
   CASE("october"):
   CASE("december"):
       days = "31";
       break;

   DEFAULT:
       days = "?";
       break;
   }

   std::cout << month << " has " << days << " days." << std::endl;

Реализация этой конструкции весьма проста. Она основана на constexpr-функциях из C++11, благодаря чему почти все вычисления производятся ещё на этапе компиляции. Если кого-то интересуют её детали, добро пожаловать под кат — благо на Хабре о «switch для строк» почему-то ничего не сказано.


Чего же мы хотим?


Прежде всего — чтобы это был полноценный switch, а не его «эмуляция» путём скрытия if-операторов и функций для сравнения строк внутри макросов, поскольку сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно. Поэтому такое решение нас не устроит — к тому же, в нём неизбежно появляются непонятные макросы типа END_STRING_SWITCH.

Кроме того, очень желательно по-максимуму задействовать компилятор. Например, что будет с «обычным» switch-case в случае, когда аргументы двух case окажутся одинаковыми? Правильно, компилятор тут же обругает нас: «duplicate case value», и прекратит компиляцию. А в примере по вышеуказанной ссылке, разумеется, ни один компилятор не сможет заметить эту ошибку.

Важен и итоговый синтаксис, простой и без лишних конструкций. Именно поэтому известный вариант "std::map со строковым ключом" нас тоже не устраивает: во-первых, аргументы case в нём не выглядят наглядными — а во-вторых, он требует обязательной инициализации используемого std::map в рантайме. Функция этой инициализации может находиться где угодно, постоянно глядеть в неё слишком утомительно.


Начинаем вычислять хэш


Остаётся последний вариант: вычислять хэш строки в switch, и сравнивать его с хэшем каждой строки в case. То есть, всё сводится к сравнению двух целых чисел, для которых switch-case прекрасно работает. Однако стандарт C++ говорит, что аргумент каждого case должен быть известен ещё при компиляции — поэтому функция «вычисления хэша от строки» должна работать именно в compile-time. В C++03 её можно реализовать лишь с помощью шаблонов, наподобие вычисления CRC в этой статье. Но в C++11, к счастью, появились более понятные constexpr-функции, значения которых также могут вычисляться компилятором.

Итак, нам нужно написать constexpr-функцию, которая бы оперировала числовыми кодами char-символов. Как известно, тело такой функции представляет из себя "return <известное в compile-time выражение>". Попробуем реализовать самый «вырожденный» её вариант, а именно — функцию вычисления длины const char* строки. Но уже здесь нас поджидают первые трудности:

   constexpr unsigned char str_len(const char* const str)
   {
      return *str ? (1 + str_len(str + 1)) : 0;
   }
	
   std::cout << (int) str_len("qwerty") << " " << (int) str_len("йцукен") << std::endl;  // проверяем

Компилятор не ругается, функция корректна. Однако у меня она почему-то вывела не «6 6», а «6 12». Отчего так? А всё дело в том, что я набрал этот исходный код под Windows в «линуксовой» кодировке UTF-8, а не в стандартной Win-1251 — и поэтому каждый «кириллический» символ воспринялся как два. Вот если сменить кодировку на стандартную, тогда действительно выведется «6 6». Что ж получается, наша задумка потерпела крах? Ведь это не дело, когда при разных кодировках получаются разные хэши…


Проверяем содержимое строки


Но зачем нам кириллица или азиатские иероглифы? В подавляющем большинстве случаев, для исходников достаточно лишь английских букв и стандартных знаков пунктуации — то есть символов, умещающихся в диапазоне от 0 до 127 в ASCII-таблице. А их char-коды при смене кодировки не изменятся — и поэтому хэш от строки, составленной лишь из них, всегда будет одинаков. Но как быть, если программист случайно всё же введёт один из таких символов? На помощь нам приходит следующая compile-time функция:

   constexpr bool str_is_correct(const char* const str)
   {
      return (static_cast<signed char>(*str) > 0) ? str_is_correct(str + 1) : (*str ? false : true);
   }

Она проверяет, содержит ли известная на стадии компиляции строка только символы из диапазона 0-127, и возвращает false в случае нахождения «запретного» символа. Зачем нужен принудительный каст к signed char? Дело в том, что в стандарте C++ не определено, чем же именно является тип char — он может быть как знаковым, так и беззнаковым. А вот его sizeof всегда будет равен 1, отчего мы смещаемся вправо на единицу. Таким образом, нужный нам макрос CASE будет иметь вид:

   #define CASE(str)  static_assert(str_is_correct(str), "CASE string contains wrong characters");\
   case str_hash(...)

Тут используется ещё одна фича C++11 — assert при компиляции. То есть, если строка-аргумент макроса CASE будет содержать хотя бы один «запретный» символ — компиляция остановится со вполне понятной ошибкой. Иначе, будет вычислен хэш, значение которого подставится в case. Это решение избавит нас от проблем с кодировкой. Осталось лишь написать саму функцию str_hash(), которая и вычислит нужный хэш.


Возвращаемся к вычислению хэша


Выбрать хэш-функцию можно по-разному, и самый главный вопрос тут — это возможность коллизий. Если хэши двух различных строк совпадут, то программа может перепрыгнуть со switch на ложную case-ветку. И спутник упадёт в океан… Поэтому будем использовать хэш-функцию, не имеющую коллизий вообще. Так как уже установлено, что все символы строки расположены в диапазоне 0-127, то функция будет иметь вид: image. Её реализация такова:

   typedef unsigned char uchar;
   typedef unsigned long long ullong;

   constexpr ullong str_hash(const char* const str, const uchar current_len)
   {
      return *str ? (raise_128_to(current_len - 1) * static_cast<uchar>(*str)
      + str_hash(str + 1, current_len - 1)) : 0;
   }

Здесь raise_128_to() — это compile-time функция возведения 128 в степень, а current_len — это длина текущей строки. Конечно, длину можно вычислять и на каждом шаге рекурсии, но это лишь замедлит компиляцию — лучше сосчитать её до первого запуска str_hash(), и затем всегда подставлять как дополнительный аргумент. При какой же максимальной длине строки эта функция не будет иметь коллизий? Очевидно, лишь тогда, когда полученное ею значение всегда уместится в диапазоне типа unsigned long long (также окончательно введённого в C++11), то есть если оно не превышает 264-1.

Можно подсчитать, что эта максимальная длина будет равна 9 (обозначим это число как MAX_LEN). А вот максимально возможное значение хэша составит ровно 263 для строки, все символы которой имеют код 127 (и являются нечитаемыми в ASCII, так что под CASE мы её всё равно не загоним). Но как быть, если под CASE будет стоять строка из 10 символов? Если мы действительно не хотим возникновения коллизий, то нужно запретить и такую возможность — то есть, расширить уже используемый нами static_assert:

   #define CASE(str)  static_assert(str_is_correct(str) && (str_len(str) <= MAX_LEN),\
   "CASE string contains wrong characters, or its length is greater than 9");\
   case str_hash(str, str_len(str))


Производим финальные штрихи


Всё, с макросом CASE покончено. Он либо выдаст нам ошибку компиляции, либо вычислит уникальное значение хэша. Вот для подсчёта хэша в макросе SWITCH нам придётся сделать отдельную функцию, поскольку она будет работать уже в рантайме. А если её строка-аргумент будет иметь длину более 9 символов, то договоримся возвращать 264-1 (обозначим это число как N_HASH). Итак:

   #define SWITCH(str)  switch(str_hash_for_switch(str))
   const ullong N_HASH = static_cast<ullong>(-1);  // по аналогии с std::string::npos
	
   inline ullong str_hash_for_switch(const char* const str)
   {
      return (str_is_correct(str) && (str_len(str) <= MAX_LEN)) ? str_hash(str, str_len(str)) : N_HASH;
   }

Собственно, вот и всё. В рантайме вычислится хэш для строки в SWITCH, и если одна строк в CASE имеет такой же хэш, исполнение пойдёт на неё. Если какая-то строка из CASE содержит «запретные» символы, или её длина больше 9 символов — мы получим надёжную ошибку компиляции. Нагрузки в рантайме почти нет (за исключением однократного вычисление хэша для SWITCH), читаемость кода не страдает. Осталось лишь перегрузить функцию str_hash_for_switch() для строк std::string, и заключить всё внутрь namespace.

Итоговый h-файл исходников лежит на Гитхабе. Он подойдёт для любого компилятора с поддержкой C++11. Для использования «switch для строк» просто сделайте инклуд str_switch.h куда хотите, и всё — макросы SWITCH, CASE и DEFAULT перед вами. Не забудьте про ограничение на длину строки в CASE (9 символов).
В общем — надеюсь, что кому-нибудь эта реализация пригодится ;)

  P. S. Upd: в коде была обнаружена пара неточностей — поэтому сейчас он обновлён, вместе со статьёй. В комментариях также предлагалось использовать другую функцию для вычисления хэша — разумеется, каждый может написать свою её реализацию.
Константин @Efrit
карма
22,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (50)

  • +9
    так что под CASE мы её всё равно не загоним

    Легко, через escape-последовательности. Например:
    ullong const h1 = str_hash("\x03\x01", 2);
    ullong const h2 = str_hash("\x01\x01\x01", 3);

    Кстати, о коллизиях — эти строки дают одинаковый хэш.
    • +1
      Про хэш прошу прощения, поторопился, успел поиграться с кодом и сломать.
      • 0
        Переписал raise_128_to покороче и потерял множитель:
        constexpr ullong raise_128_to(const uchar power)
        {
            return 0x1ULL << 7*power;
        }
        • 0
          Кстати, да — ведь при возведении 128 в степень и впрямь можно использовать битовую арифметику, хотя на результат это не повлияет. Я про это что-то не подумал, спасибо за уточнение. Надо будет файл обновить.

          Что касается эскейп-последовательностей в case — лично у меня GCC на них кидает варнинг при компиляции, так что программист их заметит. В крайнем случае, можно изменить функцию str_is_correct на диапазон 0-126 — тогда точно можно быть спокойным.
  • +1
    Вообще звучит очень правильно использовать функцию хеширования.

    До пустим возьмем строку 'FIBONACI_STRING_REPLACE' ( ее размер 24 байта если это только MBC строка). Ее нужно сравнить с многими другими строками как например с 'MACLIACI_STRING_REPLACE' итд. Правда одно дело когда строк всего пару для сравнения, другое дело когда количество строк переваливает за 10 тысяч.

    Куда проще будет вычислить Хешкод (в итоге у нас будет 4 байта для типа INT). И сравнить просто числа размером по 4 байта. у нас получится примерно 5 кратное увеличение производительности.

    Господа как Вы думаете стоит ли перевести или написать статью про внутренности Хеш таблицы и про Хеширование ??
    Мне сама это тема интересена так как я сечас работаю над оптимизацией кода в проекте связаного с хешированием и хеш таблицами!!!

    • +5
      Конечно, пишите. Хорошие статьи про алгоритмы украшают Хабр.
    • +1
      Только не стоит забывать про коллизии, ведь для 2 разных строк может быть один и тот-же хэш код. Описанный способ одназначно лучше, если (а) нет коллизий в изначальном наборе строк и (б) на входе в функцию приходят строки, у которых нет коллизий с существующим набором. Однако, даже если эти условия не выполняются, для отдельных случаев можно придумать хитрое решение и минимизировать вероятность коллизий :)
  • +1
    конечно, понятно, что статья больше о constexpr и красоте кода, но для решения конкретной задачи лучше бы подошел perfect hash. А то ограничение на 10 символов как-то смущает.
    • –1
      Конечно, я рассматривал и perfect hash. С его применением ограничения вообще бы не чувствовались :)
      Однако потом посчитал, что отсутствие коллизий важнее. Ведь данные макросы может использовать человек, который и не подозревает, что в них идёт вычисление хэша… И коллизии могут быть очень некстати, даже если вероятность их возникновения минимальна.
      Хотя, конечно, функцию str_hash можно переделать на всё что угодно.
      • +1
        Конечно, я рассматривал и perfect hash. Однако потом посчитал, что отсутствие коллизий важнее.

        Вы что-то путаете. Perfect hash как раз коллизий не имеет. Его основная проблема — это то, что для создания конкретной функции необходимо иметь «на руках» весь начальный набор значений.
        • 0
          Да, извиняюсь, я спутал с шифрованием вроде MD5. А Perfect hash реализовать можно, но для этого придётся при добавлении строки в CASE заодно добавлять эту строку в функцию вычисления хэша.
          • 0
            Да не придётся же. perfect hash как раз и генерирует эту функцию.
            • 0
              Но как Вы в этом случае будете реализовывать функцию подсчёта хэша, работающую во время компиляции?
              Ведь аргументы макроса CASE могут встречаться в коде где угодно…
              • 0
                Функцию вам реализует gperf или другой инструмент типа него. Вот как собрать ему все кейсы одного свитча — это вопрос.
                А, ну и кстати, с perfect hash возможны коллизии для строк не из первоначального набора.
                • 0
                  gperf её реализовать сможет — но хочется переложить всю работу на компилятор, не прибегая к каким-либо сторонним средствам.
        • +2
          perfect hash не имеет коллизий для элементов первоначального множества. Т.е. если построить его для набора строк, то эти строки будут иметь разные хэши. Но об остальных строках ничего сказать нельзя.
  • +1
    Если хэши двух различных строк совпадут, то программа может перепрыгнуть со switch на ложную case-ветку.

    Разве мы можем иметь пару одинаковых значений в switch? По стандарту вроде нет. Так что получим ошибку во время компиляции.
    • +2
      Имелся ввиду хэш сравниваемой строки в самом switch'e (который вычисляется в рантайме) и хэш строки в одном из case'ов.
    • +1
      надо обновлять страницу перед отправкой :)
  • +2
    сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно

    Обычно «кейс по строкам» попадает в те 80% кода программы, которые вобще не влияют на производительность. Исключения невероятно редки, для них придуманы утилиты вроде gperf (подбирает совершенную хеш-функцию для заданного набора строк).

    Afaik сделать такое не привлекая сторонних тулзов в процесс компиляции, даже в C++ последней ревизии, невозможно.
  • +2
    Похожий механизм есть в glib (хоть он и не имеет отношения к C++), называется GQuark. В glib есть что-то типа глобальной статической строковой коллекции, состоящей из массива и хэш-таблицы. При переводе строки в GQuark, если эта операция делается впервые, строка дописывается в массив, полученный индекс заносится в хеш-таблицу, и возвращается этот же индекс. Сам по себе GQuark просто является синонимом int. Повторная попытка приведения той же строки к GQuark приведёт к получению того же индекса. Обратная же операция сводится к получению элемента массива по индексу.

    switch по ним не сделать, поскольку они не являются константами, но они позволяют минимизировать число операций сравнения строк, например, путём использования кварков в качестве ключей в ассоциативных массивах.
  • +1
    Посмотрите тут, как можно static_assert, заменив его на throw, перенести в constexpr функцию. Тогда можно обойтись без макросов:
    case hash("string"):
    
    • 0
      Спасибо за ссылку, весьма интересное решение. Хотя там не хэш ищется, а иная информация по строкам (также в compile-time).
      Про макросы — главное, что они здесь безопасны.
      • +1
        Сишные макросы никогда не бывают безопасными :)
        И если есть возможность, то лучше без них обойтись.
    • 0
      Кстати, когда я экспериментировал с constexpr-функциями, я обнаружил, что constexpr-функции также могут иметь "..." (троеточие) в своей сигнатуре, как и «обычные» функции.
      То есть, если мы имеем заранее известный набор строк — мы все их можем загнать внутрь такой функции. И операция адресации (&) для переменных из сигнатуры будет внутри неё прекрасно работать.
      Но вот организовать внутри неё цикл (для обращения ко всем этим переменным) у меня не получилось…
      • 0
        Ну можно и без трех точек через variadic templates.
        Ну а если с тремя точками, то нужно рассматривать стек как массив и уже бегать по массиву. Но там выравнивание и всякое такое. Хотя на этапе компиляции работа с памятью хорошо контролируется, в частности проверка границ.
      • 0
        А не перестанет ли функция, гуляющая по стеку, быть constexpr?
        • 0
          Ну лично у меня компилятор (GCC) на это не ругается — видимо, там какая-то хитрая отпимизация.
  • 0
    Если MAX_LEN=10, то есть 70 бит, то как они могут упаковаться в 64 бита?
    • 0
      Да, Вы правы, должно быть 9. Спасибо за уточнение. Перебил константу в файле, обновил статью.
  • –1
    В юникоде русская А имеет код 0x041A, оба символа 0x04 и 0x1A — из первых 128, так что, этот символ все-таки пройдет?
    • 0
      Лично у меня не проходит, static_assert срабатывает; в диапазон 0-127 кастятся только ASCII-символы.
    • +2
      0x04 и 0x1A это именно два символа. Не ASCII символы во всех кодировках будут иметь коды, большие 128. Например, в UTF-8 русская А (0x410, btw) кодируется как 0xC0 0x90.
    • +2
      В UTF-8 в символах, которые занимают больше одного байта, старший бит у первого байта всегда 0, а старший бит у всех последующих — всегда 1 (т.е. они заведомо будут больше или равны 128).
  • +3
    Важное замечание насчёт кодировок — Linux и Windows тут ни при чём, UTF-8 сейчас стандарт практически везде… кроме самого C++. Есть хорошее эмпирическое правило — не работать с юникодом в C++ без соответствующих библиотек вообще, слишком много подводных камней. Так что попытка скормить UTF-8 литерал куда попало абсолютно точно попадает под ошибочное использование.
    • –2
      Да, просто так уж повелось, что в Linux исторически используется Юникод, а в Windows другая кодировка (хотя и Юникод нынешние версии винды, конечно, держат). Лично я все исходники сохраняю в UTF-8, даже если работаю под виндой — потом зато меньше сложностей с перекомпиляцией. А в диапазон 0-127 могут каститься только ASCII-символы, поскольку Юникод по этой часть полностью совместим с ASCII.
      • +3
        Да, просто так уж повелось, что в Linux исторически используется Юникод, а в Windows другая кодировка

        Чô?? В Windows NT (к коим, если вдруг кто не знает, относятся все современные версии Windows) Unicode используется с самой первой версии — Windows NT 3.1 (1993-й год) (начиная с Windows 2000 используется формат UTF-16, до 2000 — UCS-2). Когда я начинал пробовать Linux (во времена Windows NT 4 и 2000) в Linux ещё во всю использовалась KOI-8.

        Существует заблуждение, что само слово «Unicode» означает «Unix code», на самом деле, на сколько мне известно, это не так.
        • 0
          Извиняюсь насчёт «исторически». Я имел в виду то, что по умолчанию Windows предлагает сохранять всё в «ANSI» — хотя Юникод она, конечно же, поддерживает.
          Вообще, в этих кодировках сам чёрт ногу сломит :) На Хабре как-то уже была отличная статья на эту тему.
          • +1
            Windows предлагает сохранять всё в «ANSI» — хотя Юникод она, конечно же, поддерживает

            Проверил и был удивлён тем, что это, можно сказать, действительно так. Но это не Windows, а Notepad, в котором, видимо, просто забыли/забили это менять. Visual Studio 2012 (других версий нет под рукой проверить) сохраняет в UTF-8, Word перещёл на Unicode с версии не то 97, не то 2000. Полагаю блокнотом пользуются только истинные ценители, а во всех нормальных редакторах (например NotePad++, Sublime 2 и т.п.) кодировка по-умолчанию либо сразу человеческая, либо настраивается).

            Вообще, в этих кодировках сам чёрт ногу сломит :)

            Лично я (в общем добрый и пушистый) призываю ломать ноги тем, кто в наши дни пишет программы без поддержки Unicode не имея на то веских уважительных причин.
  • +5
    Есть еще такая штука, как typeswitch, исходный код можно найти здесь. Правда эта библиотека делает немного другое, она позволяет осуществить диспетчеризацию по типам, вот пример использования:
    int eval(const Expr& e)
    {
        Match(e)
        {
            Case(const Value&  x) return x.value;
            Case(const Plus&   x) return eval(x.e1) + eval(x.e2);
            Case(const Minus&  x) return eval(x.e1) - eval(x.e2);
            Case(const Times&  y) return eval(y.e1) * eval(y.e2);
            Case(const Divide& z) return eval(z.e1) / eval(z.e2);
        }
        EndMatch
    }
    Или здесь

    Причем сами авторы позиционируют данную библиотеку, как максимально быструю и эффективную.
    • 0
      Ага=)
      Пишут, что догоняет Хаксел и Окамл :-D
    • 0
      А она является кросс-платформенной?
      • +1
        Я собирал только под linux, но насколько я понял, поддерживается несколько платформ
  • –1
    Из практики, свитчи имеют тенденцию превращаться со временем в лапшу и в конце концов, как правило, заменяются подходящей конструкцией ООП. Поэтому подумайте сразу — будет ли расти количество case'ов со временем, и сложность внутренней логики каждого case'а.
    • 0
      Здесь дело не в этом — отпишусь ниже немного.
  • +1
    Прежде всего — чтобы это был полноценный switch, а не его «эмуляция» путём скрытия if-операторов и функций для сравнения строк внутри макросов, поскольку сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно.

    Пройдусь по пунктам.

    То, что это реальный switch/case это хорошо, но есть ряд нюансов.

    switch стоит использовать не из-за удобства, а из-за быстродействия.

    Ветвление со сравнениями (if) плохо влияет на быстродействие.

    Правильный switch позволяет его избежать — давая на выходе простые джампы без сравнения.

    Неправильный switch, например, для значения более одного байта с неизвестным набором значений имеет чуть больше чем все шансы стать набором того же множества операций ветвления со сравнением. Об этом много где написано. На вскидку ссылку не дам — помню по тем временам, когда я длительное время разрабатывал алгоритмы для задач high-load на C/C++ после изменения кода всегда изучая, что получается в машинном коде.

    Использование хэша в риалтайме добавит еще больше ветвления и лишнего оверхеда — длинна строк, циклы и ветвление.

    Кстати, ради интереса — смотрели, какой машинный код получается на выходе?
    • 0
      Согласен со всем. У меня в рантайме происходит лишь однократное вычисление хэша для switch, так что считал, что с производительностью всё должно быть в порядке… Хотя насчёт «более одного байта» я не был в курсе — а у меня явно больше.
      Машинный код не смотрел, но попробую.
  • +1
    Когда строки заранее известны, то вместо хэша более быстрым может быть конечный автомат реализованный на том же switch, например (из старого кода):

    /* Jan-Dec to 1-12 */
    unsigned long time_parse_month(unsigned char *b)
    {
    	switch(*b)
    	{
    		case 'j':
    		case 'J':
    			if((b[1]=='a')||(b[1]=='A'))
    			{
    				return(1);
    			}
    			if((b[2]=='n')||(b[2]=='N'))
    			{
    				return(6);
    			}
    			return(7);
    		case 'f':
    		case 'F':
    			return(2);
    		case 'm':
    		case 'M':
    			if((b[2]=='r')||(b[2]=='R'))
    			{
    				return(3);
    			}
    			return(5);
    		case 'a':
    		case 'A':
    			if((b[1]=='p')||(b[1]=='P'))
    			{
    				return(4);
    			}
    			return(8);
    		case 's':
    		case 'S':
    			return(9);
    		case 'o':
    		case 'O':
    			return(10);
    		case 'n':
    		case 'N':
    			return(11);
    		case 'd':
    		case 'D':
    			return(12);
    		default:
    			break;
    	}
    	return(0);
    }
    


    У нас это для парсинга логов использовалось — вариант с if внутри switch вышел быстрее на практике.
    • +1
      Тогда уж шли бы дальше: использовали бы генератор лексических анализаторов, который построил бы вам заведомо оптимальный автомат.
    • 0
      На самом деле тут много факторов, которые влияют на производительность решения. Например, такой код для 10000 заранее известных строк будет занимать очень много байтов. Такое раздутие может привести только к деградации производительности, из-за того что весь код может не содержаться в кэше процессора, и ему постоянно прийдётся подгружать его из памяти. В таком случае скорость подсчёта хэша и использование хэш-таблицы могут оказаться быстрее. Это только один из сценариев, их может быть уйма. И точно сказать что один подход всегда лучше другого — невозможно. Нужно отталкиваться от конкретного сценария.

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