Comments 52
так что под CASE мы её всё равно не загоним
Легко, через escape-последовательности. Например:
ullong const h1 = str_hash("\x03\x01", 2);
ullong const h2 = str_hash("\x01\x01\x01", 3);Кстати, о коллизиях — эти строки дают одинаковый хэш.
Про хэш прошу прощения, поторопился, успел поиграться с кодом и сломать.
Переписал raise_128_to покороче и потерял множитель:
constexpr ullong raise_128_to(const uchar power)
{
return 0x1ULL << 7*power;
}
Кстати, да — ведь при возведении 128 в степень и впрямь можно использовать битовую арифметику, хотя на результат это не повлияет. Я про это что-то не подумал, спасибо за уточнение. Надо будет файл обновить.
Что касается эскейп-последовательностей в case — лично у меня GCC на них кидает варнинг при компиляции, так что программист их заметит. В крайнем случае, можно изменить функцию str_is_correct на диапазон 0-126 — тогда точно можно быть спокойным.
Что касается эскейп-последовательностей в case — лично у меня GCC на них кидает варнинг при компиляции, так что программист их заметит. В крайнем случае, можно изменить функцию str_is_correct на диапазон 0-126 — тогда точно можно быть спокойным.
Вообще звучит очень правильно использовать функцию хеширования.
До пустим возьмем строку 'FIBONACI_STRING_REPLACE' ( ее размер 24 байта если это только MBC строка). Ее нужно сравнить с многими другими строками как например с 'MACLIACI_STRING_REPLACE' итд. Правда одно дело когда строк всего пару для сравнения, другое дело когда количество строк переваливает за 10 тысяч.
Куда проще будет вычислить Хешкод (в итоге у нас будет 4 байта для типа INT). И сравнить просто числа размером по 4 байта. у нас получится примерно 5 кратное увеличение производительности.
Господа как Вы думаете стоит ли перевести или написать статью про внутренности Хеш таблицы и про Хеширование ??
Мне сама это тема интересена так как я сечас работаю над оптимизацией кода в проекте связаного с хешированием и хеш таблицами!!!
До пустим возьмем строку 'FIBONACI_STRING_REPLACE' ( ее размер 24 байта если это только MBC строка). Ее нужно сравнить с многими другими строками как например с 'MACLIACI_STRING_REPLACE' итд. Правда одно дело когда строк всего пару для сравнения, другое дело когда количество строк переваливает за 10 тысяч.
Куда проще будет вычислить Хешкод (в итоге у нас будет 4 байта для типа INT). И сравнить просто числа размером по 4 байта. у нас получится примерно 5 кратное увеличение производительности.
Господа как Вы думаете стоит ли перевести или написать статью про внутренности Хеш таблицы и про Хеширование ??
Мне сама это тема интересена так как я сечас работаю над оптимизацией кода в проекте связаного с хешированием и хеш таблицами!!!
Конечно, пишите. Хорошие статьи про алгоритмы украшают Хабр.
Только не стоит забывать про коллизии, ведь для 2 разных строк может быть один и тот-же хэш код. Описанный способ одназначно лучше, если (а) нет коллизий в изначальном наборе строк и (б) на входе в функцию приходят строки, у которых нет коллизий с существующим набором. Однако, даже если эти условия не выполняются, для отдельных случаев можно придумать хитрое решение и минимизировать вероятность коллизий :)
конечно, понятно, что статья больше о constexpr и красоте кода, но для решения конкретной задачи лучше бы подошел perfect hash. А то ограничение на 10 символов как-то смущает.
Конечно, я рассматривал и perfect hash. С его применением ограничения вообще бы не чувствовались :)
Однако потом посчитал, что отсутствие коллизий важнее. Ведь данные макросы может использовать человек, который и не подозревает, что в них идёт вычисление хэша… И коллизии могут быть очень некстати, даже если вероятность их возникновения минимальна.
Хотя, конечно, функцию str_hash можно переделать на всё что угодно.
Однако потом посчитал, что отсутствие коллизий важнее. Ведь данные макросы может использовать человек, который и не подозревает, что в них идёт вычисление хэша… И коллизии могут быть очень некстати, даже если вероятность их возникновения минимальна.
Хотя, конечно, функцию str_hash можно переделать на всё что угодно.
Конечно, я рассматривал и perfect hash. Однако потом посчитал, что отсутствие коллизий важнее.
Вы что-то путаете. Perfect hash как раз коллизий не имеет. Его основная проблема — это то, что для создания конкретной функции необходимо иметь «на руках» весь начальный набор значений.
Да, извиняюсь, я спутал с шифрованием вроде MD5. А Perfect hash реализовать можно, но для этого придётся при добавлении строки в CASE заодно добавлять эту строку в функцию вычисления хэша.
Да не придётся же. perfect hash как раз и генерирует эту функцию.
Но как Вы в этом случае будете реализовывать функцию подсчёта хэша, работающую во время компиляции?
Ведь аргументы макроса CASE могут встречаться в коде где угодно…
Ведь аргументы макроса CASE могут встречаться в коде где угодно…
perfect hash не имеет коллизий для элементов первоначального множества. Т.е. если построить его для набора строк, то эти строки будут иметь разные хэши. Но об остальных строках ничего сказать нельзя.
Если хэши двух различных строк совпадут, то программа может перепрыгнуть со switch на ложную case-ветку.
Разве мы можем иметь пару одинаковых значений в switch? По стандарту вроде нет. Так что получим ошибку во время компиляции.
Разве мы можем иметь пару одинаковых значений в switch? По стандарту вроде нет. Так что получим ошибку во время компиляции.
сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно
Обычно «кейс по строкам» попадает в те 80% кода программы, которые вобще не влияют на производительность. Исключения невероятно редки, для них придуманы утилиты вроде gperf (подбирает совершенную хеш-функцию для заданного набора строк).
Afaik сделать такое не привлекая сторонних тулзов в процесс компиляции, даже в C++ последней ревизии, невозможно.
Похожий механизм есть в glib (хоть он и не имеет отношения к C++), называется GQuark. В glib есть что-то типа глобальной статической строковой коллекции, состоящей из массива и хэш-таблицы. При переводе строки в GQuark, если эта операция делается впервые, строка дописывается в массив, полученный индекс заносится в хеш-таблицу, и возвращается этот же индекс. Сам по себе GQuark просто является синонимом int. Повторная попытка приведения той же строки к GQuark приведёт к получению того же индекса. Обратная же операция сводится к получению элемента массива по индексу.
switch по ним не сделать, поскольку они не являются константами, но они позволяют минимизировать число операций сравнения строк, например, путём использования кварков в качестве ключей в ассоциативных массивах.
switch по ним не сделать, поскольку они не являются константами, но они позволяют минимизировать число операций сравнения строк, например, путём использования кварков в качестве ключей в ассоциативных массивах.
Посмотрите тут, как можно static_assert, заменив его на throw, перенести в constexpr функцию. Тогда можно обойтись без макросов:
case hash("string"):
Спасибо за ссылку, весьма интересное решение. Хотя там не хэш ищется, а иная информация по строкам (также в compile-time).
Про макросы — главное, что они здесь безопасны.
Про макросы — главное, что они здесь безопасны.
Кстати, когда я экспериментировал с constexpr-функциями, я обнаружил, что constexpr-функции также могут иметь "..." (троеточие) в своей сигнатуре, как и «обычные» функции.
То есть, если мы имеем заранее известный набор строк — мы все их можем загнать внутрь такой функции. И операция адресации (&) для переменных из сигнатуры будет внутри неё прекрасно работать.
Но вот организовать внутри неё цикл (для обращения ко всем этим переменным) у меня не получилось…
То есть, если мы имеем заранее известный набор строк — мы все их можем загнать внутрь такой функции. И операция адресации (&) для переменных из сигнатуры будет внутри неё прекрасно работать.
Но вот организовать внутри неё цикл (для обращения ко всем этим переменным) у меня не получилось…
Ну можно и без трех точек через variadic templates.
Ну а если с тремя точками, то нужно рассматривать стек как массив и уже бегать по массиву. Но там выравнивание и всякое такое. Хотя на этапе компиляции работа с памятью хорошо контролируется, в частности проверка границ.
Ну а если с тремя точками, то нужно рассматривать стек как массив и уже бегать по массиву. Но там выравнивание и всякое такое. Хотя на этапе компиляции работа с памятью хорошо контролируется, в частности проверка границ.
А не перестанет ли функция, гуляющая по стеку, быть constexpr?
....
template <std::size_t N>
struct Hash {
ullong value;
bool ok;
enum { size = N - 1 };
constexpr Hash(char const (&str)[N])
: value { str_hash(str,size) }
, ok { str_is_correct(str) }
{
static_assert((size <= MAX_LEN), "CASE string length is greater than 9");
};
};
} // namespace s_s
template <s_s::Hash H>
constexpr auto operator""_h()
{
static_assert(H.ok, "CASE string contains wrong characters");
return H.value;
}
....
case "april"_h:Я тоже не люблю макросы и немного подшаманил https://godbolt.org/z/j8q6fafrY
Если MAX_LEN=10, то есть 70 бит, то как они могут упаковаться в 64 бита?
В юникоде русская А имеет код 0x041A, оба символа 0x04 и 0x1A — из первых 128, так что, этот символ все-таки пройдет?
Лично у меня не проходит, static_assert срабатывает; в диапазон 0-127 кастятся только ASCII-символы.
0x04 и 0x1A это именно два символа. Не ASCII символы во всех кодировках будут иметь коды, большие 128. Например, в UTF-8 русская А (0x410, btw) кодируется как 0xC0 0x90.
В UTF-8 в символах, которые занимают больше одного байта, старший бит у первого байта всегда 0, а старший бит у всех последующих — всегда 1 (т.е. они заведомо будут больше или равны 128).
Важное замечание насчёт кодировок — Linux и Windows тут ни при чём, UTF-8 сейчас стандарт практически везде… кроме самого C++. Есть хорошее эмпирическое правило — не работать с юникодом в C++ без соответствующих библиотек вообще, слишком много подводных камней. Так что попытка скормить UTF-8 литерал куда попало абсолютно точно попадает под ошибочное использование.
Да, просто так уж повелось, что в Linux исторически используется Юникод, а в Windows другая кодировка (хотя и Юникод нынешние версии винды, конечно, держат). Лично я все исходники сохраняю в UTF-8, даже если работаю под виндой — потом зато меньше сложностей с перекомпиляцией. А в диапазон 0-127 могут каститься только ASCII-символы, поскольку Юникод по этой часть полностью совместим с ASCII.
Да, просто так уж повелось, что в 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», на самом деле, на сколько мне известно, это не так.
Извиняюсь насчёт «исторически». Я имел в виду то, что по умолчанию Windows предлагает сохранять всё в «ANSI» — хотя Юникод она, конечно же, поддерживает.
Вообще, в этих кодировках сам чёрт ногу сломит :) На Хабре как-то уже была отличная статья на эту тему.
Вообще, в этих кодировках сам чёрт ногу сломит :) На Хабре как-то уже была отличная статья на эту тему.
Windows предлагает сохранять всё в «ANSI» — хотя Юникод она, конечно же, поддерживает
Проверил и был удивлён тем, что это, можно сказать, действительно так. Но это не Windows, а Notepad, в котором, видимо, просто забыли/забили это менять. Visual Studio 2012 (других версий нет под рукой проверить) сохраняет в UTF-8, Word перещёл на Unicode с версии не то 97, не то 2000. Полагаю блокнотом пользуются только истинные ценители, а во всех нормальных редакторах (например NotePad++, Sublime 2 и т.п.) кодировка по-умолчанию либо сразу человеческая, либо настраивается).
Вообще, в этих кодировках сам чёрт ногу сломит :)
Лично я (в общем добрый и пушистый) призываю ломать ноги тем, кто в наши дни пишет программы без поддержки Unicode не имея на то веских уважительных причин.
Есть еще такая штука, как 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
}Причем сами авторы позиционируют данную библиотеку, как максимально быструю и эффективную.
Из практики, свитчи имеют тенденцию превращаться со временем в лапшу и в конце концов, как правило, заменяются подходящей конструкцией ООП. Поэтому подумайте сразу — будет ли расти количество case'ов со временем, и сложность внутренней логики каждого case'а.
Прежде всего — чтобы это был полноценный switch, а не его «эмуляция» путём скрытия if-операторов и функций для сравнения строк внутри макросов, поскольку сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно.
Пройдусь по пунктам.
То, что это реальный switch/case это хорошо, но есть ряд нюансов.
switch стоит использовать не из-за удобства, а из-за быстродействия.
Ветвление со сравнениями (if) плохо влияет на быстродействие.
Правильный switch позволяет его избежать — давая на выходе простые джампы без сравнения.
Неправильный switch, например, для значения более одного байта с неизвестным набором значений имеет чуть больше чем все шансы стать набором того же множества операций ветвления со сравнением. Об этом много где написано. На вскидку ссылку не дам — помню по тем временам, когда я длительное время разрабатывал алгоритмы для задач high-load на C/C++ после изменения кода всегда изучая, что получается в машинном коде.
Использование хэша в риалтайме добавит еще больше ветвления и лишнего оверхеда — длинна строк, циклы и ветвление.
Кстати, ради интереса — смотрели, какой машинный код получается на выходе?
Пройдусь по пунктам.
То, что это реальный switch/case это хорошо, но есть ряд нюансов.
switch стоит использовать не из-за удобства, а из-за быстродействия.
Ветвление со сравнениями (if) плохо влияет на быстродействие.
Правильный switch позволяет его избежать — давая на выходе простые джампы без сравнения.
Неправильный switch, например, для значения более одного байта с неизвестным набором значений имеет чуть больше чем все шансы стать набором того же множества операций ветвления со сравнением. Об этом много где написано. На вскидку ссылку не дам — помню по тем временам, когда я длительное время разрабатывал алгоритмы для задач high-load на C/C++ после изменения кода всегда изучая, что получается в машинном коде.
Использование хэша в риалтайме добавит еще больше ветвления и лишнего оверхеда — длинна строк, циклы и ветвление.
Кстати, ради интереса — смотрели, какой машинный код получается на выходе?
Когда строки заранее известны, то вместо хэша более быстрым может быть конечный автомат реализованный на том же switch, например (из старого кода):
У нас это для парсинга логов использовалось — вариант с if внутри 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 вышел быстрее на практике.
Тогда уж шли бы дальше: использовали бы генератор лексических анализаторов, который построил бы вам заведомо оптимальный автомат.
На самом деле тут много факторов, которые влияют на производительность решения. Например, такой код для 10000 заранее известных строк будет занимать очень много байтов. Такое раздутие может привести только к деградации производительности, из-за того что весь код может не содержаться в кэше процессора, и ему постоянно прийдётся подгружать его из памяти. В таком случае скорость подсчёта хэша и использование хэш-таблицы могут оказаться быстрее. Это только один из сценариев, их может быть уйма. И точно сказать что один подход всегда лучше другого — невозможно. Нужно отталкиваться от конкретного сценария.
Sign up to leave a comment.
Switch для строк в C++11