Комментарии 52
так что под CASE мы её всё равно не загоним
Легко, через escape-последовательности. Например:
ullong const h1 = str_hash("\x03\x01", 2);
ullong const h2 = str_hash("\x01\x01\x01", 3);
Кстати, о коллизиях — эти строки дают одинаковый хэш.
+9
Про хэш прошу прощения, поторопился, успел поиграться с кодом и сломать.
+1
Переписал raise_128_to покороче и потерял множитель:
constexpr ullong raise_128_to(const uchar power)
{
return 0x1ULL << 7*power;
}
0
Кстати, да — ведь при возведении 128 в степень и впрямь можно использовать битовую арифметику, хотя на результат это не повлияет. Я про это что-то не подумал, спасибо за уточнение. Надо будет файл обновить.
Что касается эскейп-последовательностей в case — лично у меня GCC на них кидает варнинг при компиляции, так что программист их заметит. В крайнем случае, можно изменить функцию str_is_correct на диапазон 0-126 — тогда точно можно быть спокойным.
Что касается эскейп-последовательностей в case — лично у меня GCC на них кидает варнинг при компиляции, так что программист их заметит. В крайнем случае, можно изменить функцию str_is_correct на диапазон 0-126 — тогда точно можно быть спокойным.
0
Вообще звучит очень правильно использовать функцию хеширования.
До пустим возьмем строку '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 кратное увеличение производительности.
Господа как Вы думаете стоит ли перевести или написать статью про внутренности Хеш таблицы и про Хеширование ??
Мне сама это тема интересена так как я сечас работаю над оптимизацией кода в проекте связаного с хешированием и хеш таблицами!!!
+1
Конечно, пишите. Хорошие статьи про алгоритмы украшают Хабр.
+5
Только не стоит забывать про коллизии, ведь для 2 разных строк может быть один и тот-же хэш код. Описанный способ одназначно лучше, если (а) нет коллизий в изначальном наборе строк и (б) на входе в функцию приходят строки, у которых нет коллизий с существующим набором. Однако, даже если эти условия не выполняются, для отдельных случаев можно придумать хитрое решение и минимизировать вероятность коллизий :)
+1
конечно, понятно, что статья больше о constexpr и красоте кода, но для решения конкретной задачи лучше бы подошел perfect hash. А то ограничение на 10 символов как-то смущает.
+1
Конечно, я рассматривал и perfect hash. С его применением ограничения вообще бы не чувствовались :)
Однако потом посчитал, что отсутствие коллизий важнее. Ведь данные макросы может использовать человек, который и не подозревает, что в них идёт вычисление хэша… И коллизии могут быть очень некстати, даже если вероятность их возникновения минимальна.
Хотя, конечно, функцию str_hash можно переделать на всё что угодно.
Однако потом посчитал, что отсутствие коллизий важнее. Ведь данные макросы может использовать человек, который и не подозревает, что в них идёт вычисление хэша… И коллизии могут быть очень некстати, даже если вероятность их возникновения минимальна.
Хотя, конечно, функцию str_hash можно переделать на всё что угодно.
-1
Конечно, я рассматривал и perfect hash. Однако потом посчитал, что отсутствие коллизий важнее.
Вы что-то путаете. Perfect hash как раз коллизий не имеет. Его основная проблема — это то, что для создания конкретной функции необходимо иметь «на руках» весь начальный набор значений.
+1
Да, извиняюсь, я спутал с шифрованием вроде MD5. А Perfect hash реализовать можно, но для этого придётся при добавлении строки в CASE заодно добавлять эту строку в функцию вычисления хэша.
0
Да не придётся же. perfect hash как раз и генерирует эту функцию.
0
Но как Вы в этом случае будете реализовывать функцию подсчёта хэша, работающую во время компиляции?
Ведь аргументы макроса CASE могут встречаться в коде где угодно…
Ведь аргументы макроса CASE могут встречаться в коде где угодно…
0
Функцию вам реализует gperf или другой инструмент типа него. Вот как собрать ему все кейсы одного свитча — это вопрос.
А, ну и кстати, с perfect hash возможны коллизии для строк не из первоначального набора.
А, ну и кстати, с perfect hash возможны коллизии для строк не из первоначального набора.
0
perfect hash не имеет коллизий для элементов первоначального множества. Т.е. если построить его для набора строк, то эти строки будут иметь разные хэши. Но об остальных строках ничего сказать нельзя.
+2
Если хэши двух различных строк совпадут, то программа может перепрыгнуть со switch на ложную case-ветку.
Разве мы можем иметь пару одинаковых значений в switch? По стандарту вроде нет. Так что получим ошибку во время компиляции.
Разве мы можем иметь пару одинаковых значений в switch? По стандарту вроде нет. Так что получим ошибку во время компиляции.
+1
сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно
Обычно «кейс по строкам» попадает в те 80% кода программы, которые вобще не влияют на производительность. Исключения невероятно редки, для них придуманы утилиты вроде gperf (подбирает совершенную хеш-функцию для заданного набора строк).
Afaik сделать такое не привлекая сторонних тулзов в процесс компиляции, даже в C++ последней ревизии, невозможно.
+2
Похожий механизм есть в glib (хоть он и не имеет отношения к C++), называется GQuark. В glib есть что-то типа глобальной статической строковой коллекции, состоящей из массива и хэш-таблицы. При переводе строки в GQuark, если эта операция делается впервые, строка дописывается в массив, полученный индекс заносится в хеш-таблицу, и возвращается этот же индекс. Сам по себе GQuark просто является синонимом int. Повторная попытка приведения той же строки к GQuark приведёт к получению того же индекса. Обратная же операция сводится к получению элемента массива по индексу.
switch по ним не сделать, поскольку они не являются константами, но они позволяют минимизировать число операций сравнения строк, например, путём использования кварков в качестве ключей в ассоциативных массивах.
switch по ним не сделать, поскольку они не являются константами, но они позволяют минимизировать число операций сравнения строк, например, путём использования кварков в качестве ключей в ассоциативных массивах.
+2
Посмотрите тут, как можно static_assert, заменив его на throw, перенести в constexpr функцию. Тогда можно обойтись без макросов:
case hash("string"):
+1
Спасибо за ссылку, весьма интересное решение. Хотя там не хэш ищется, а иная информация по строкам (также в compile-time).
Про макросы — главное, что они здесь безопасны.
Про макросы — главное, что они здесь безопасны.
0
Кстати, когда я экспериментировал с constexpr-функциями, я обнаружил, что constexpr-функции также могут иметь "..." (троеточие) в своей сигнатуре, как и «обычные» функции.
То есть, если мы имеем заранее известный набор строк — мы все их можем загнать внутрь такой функции. И операция адресации (&) для переменных из сигнатуры будет внутри неё прекрасно работать.
Но вот организовать внутри неё цикл (для обращения ко всем этим переменным) у меня не получилось…
То есть, если мы имеем заранее известный набор строк — мы все их можем загнать внутрь такой функции. И операция адресации (&) для переменных из сигнатуры будет внутри неё прекрасно работать.
Но вот организовать внутри неё цикл (для обращения ко всем этим переменным) у меня не получилось…
0
Ну можно и без трех точек через variadic templates.
Ну а если с тремя точками, то нужно рассматривать стек как массив и уже бегать по массиву. Но там выравнивание и всякое такое. Хотя на этапе компиляции работа с памятью хорошо контролируется, в частности проверка границ.
Ну а если с тремя точками, то нужно рассматривать стек как массив и уже бегать по массиву. Но там выравнивание и всякое такое. Хотя на этапе компиляции работа с памятью хорошо контролируется, в частности проверка границ.
0
А не перестанет ли функция, гуляющая по стеку, быть constexpr?
0
....
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
+1
Если MAX_LEN=10, то есть 70 бит, то как они могут упаковаться в 64 бита?
0
В юникоде русская А имеет код 0x041A, оба символа 0x04 и 0x1A — из первых 128, так что, этот символ все-таки пройдет?
-1
Лично у меня не проходит, static_assert срабатывает; в диапазон 0-127 кастятся только ASCII-символы.
0
0x04 и 0x1A это именно два символа. Не ASCII символы во всех кодировках будут иметь коды, большие 128. Например, в UTF-8 русская А (0x410, btw) кодируется как 0xC0 0x90.
+2
В UTF-8 в символах, которые занимают больше одного байта, старший бит у первого байта всегда 0, а старший бит у всех последующих — всегда 1 (т.е. они заведомо будут больше или равны 128).
+2
Важное замечание насчёт кодировок — Linux и Windows тут ни при чём, UTF-8 сейчас стандарт практически везде… кроме самого C++. Есть хорошее эмпирическое правило — не работать с юникодом в C++ без соответствующих библиотек вообще, слишком много подводных камней. Так что попытка скормить UTF-8 литерал куда попало абсолютно точно попадает под ошибочное использование.
+3
Да, просто так уж повелось, что в Linux исторически используется Юникод, а в Windows другая кодировка (хотя и Юникод нынешние версии винды, конечно, держат). Лично я все исходники сохраняю в UTF-8, даже если работаю под виндой — потом зато меньше сложностей с перекомпиляцией. А в диапазон 0-127 могут каститься только ASCII-символы, поскольку Юникод по этой часть полностью совместим с ASCII.
-2
Да, просто так уж повелось, что в 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», на самом деле, на сколько мне известно, это не так.
+3
Извиняюсь насчёт «исторически». Я имел в виду то, что по умолчанию Windows предлагает сохранять всё в «ANSI» — хотя Юникод она, конечно же, поддерживает.
Вообще, в этих кодировках сам чёрт ногу сломит :) На Хабре как-то уже была отличная статья на эту тему.
Вообще, в этих кодировках сам чёрт ногу сломит :) На Хабре как-то уже была отличная статья на эту тему.
0
Windows предлагает сохранять всё в «ANSI» — хотя Юникод она, конечно же, поддерживает
Проверил и был удивлён тем, что это, можно сказать, действительно так. Но это не Windows, а Notepad, в котором, видимо, просто забыли/забили это менять. Visual Studio 2012 (других версий нет под рукой проверить) сохраняет в UTF-8, Word перещёл на Unicode с версии не то 97, не то 2000. Полагаю блокнотом пользуются только истинные ценители, а во всех нормальных редакторах (например NotePad++, Sublime 2 и т.п.) кодировка по-умолчанию либо сразу человеческая, либо настраивается).
Вообще, в этих кодировках сам чёрт ногу сломит :)
Лично я (в общем добрый и пушистый) призываю ломать ноги тем, кто в наши дни пишет программы без поддержки Unicode не имея на то веских уважительных причин.
+1
Есть еще такая штука, как 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
}
Или здесьПричем сами авторы позиционируют данную библиотеку, как максимально быструю и эффективную.
+5
Из практики, свитчи имеют тенденцию превращаться со временем в лапшу и в конце концов, как правило, заменяются подходящей конструкцией ООП. Поэтому подумайте сразу — будет ли расти количество case'ов со временем, и сложность внутренней логики каждого case'а.
-1
Прежде всего — чтобы это был полноценный switch, а не его «эмуляция» путём скрытия if-операторов и функций для сравнения строк внутри макросов, поскольку сравнение строк в рантайме — дорогостоящая операция, и проводить её для каждой строки из CASE слишком расточительно.
Пройдусь по пунктам.
То, что это реальный switch/case это хорошо, но есть ряд нюансов.
switch стоит использовать не из-за удобства, а из-за быстродействия.
Ветвление со сравнениями (if) плохо влияет на быстродействие.
Правильный switch позволяет его избежать — давая на выходе простые джампы без сравнения.
Неправильный switch, например, для значения более одного байта с неизвестным набором значений имеет чуть больше чем все шансы стать набором того же множества операций ветвления со сравнением. Об этом много где написано. На вскидку ссылку не дам — помню по тем временам, когда я длительное время разрабатывал алгоритмы для задач high-load на C/C++ после изменения кода всегда изучая, что получается в машинном коде.
Использование хэша в риалтайме добавит еще больше ветвления и лишнего оверхеда — длинна строк, циклы и ветвление.
Кстати, ради интереса — смотрели, какой машинный код получается на выходе?
Пройдусь по пунктам.
То, что это реальный switch/case это хорошо, но есть ряд нюансов.
switch стоит использовать не из-за удобства, а из-за быстродействия.
Ветвление со сравнениями (if) плохо влияет на быстродействие.
Правильный switch позволяет его избежать — давая на выходе простые джампы без сравнения.
Неправильный switch, например, для значения более одного байта с неизвестным набором значений имеет чуть больше чем все шансы стать набором того же множества операций ветвления со сравнением. Об этом много где написано. На вскидку ссылку не дам — помню по тем временам, когда я длительное время разрабатывал алгоритмы для задач high-load на C/C++ после изменения кода всегда изучая, что получается в машинном коде.
Использование хэша в риалтайме добавит еще больше ветвления и лишнего оверхеда — длинна строк, циклы и ветвление.
Кстати, ради интереса — смотрели, какой машинный код получается на выходе?
+1
Когда строки заранее известны, то вместо хэша более быстрым может быть конечный автомат реализованный на том же 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 вышел быстрее на практике.
+1
Тогда уж шли бы дальше: использовали бы генератор лексических анализаторов, который построил бы вам заведомо оптимальный автомат.
+1
На самом деле тут много факторов, которые влияют на производительность решения. Например, такой код для 10000 заранее известных строк будет занимать очень много байтов. Такое раздутие может привести только к деградации производительности, из-за того что весь код может не содержаться в кэше процессора, и ему постоянно прийдётся подгружать его из памяти. В таком случае скорость подсчёта хэша и использование хэш-таблицы могут оказаться быстрее. Это только один из сценариев, их может быть уйма. И точно сказать что один подход всегда лучше другого — невозможно. Нужно отталкиваться от конкретного сценария.
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Switch для строк в C++11