Модераторы: Daevaorn

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> string hashing in compile-time, хеш 
V
    Опции темы
mes
Дата 14.2.2011, 16:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250
Цитата(boostcoder @  14.2.2011,  02:00 Найти цитируемый пост)
можно подробнее? ;)

вот примерно:
Код

template<size_t N, size_t I=0>
struct hash_calc
{
    static constexpr size_t apply (const char (&s)[N])
    {
       return  (hash_calc<N, I+1>::apply(s) ^ s[I]) * 16777619u;
    };
};
template<size_t N>
struct hash_calc<N,N>
{
    static constexpr size_t apply (const char (&s)[N])
    {
       return  2166136261u;
    };
};
template<size_t N>
constexpr size_t hash ( const char (&s)[N] )
{
    return hash_calc<N>::apply(s);
}

допиливайте  smile



--------------------
http://opendots.net
PM MAIL WWW   Вверх
mes
Дата 14.2.2011, 21:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250
Цитата(boostcoder @  14.2.2011,  02:00 Найти цитируемый пост)
  static_assert(N<130, "maximum 64 symbols allowed!"...

нельзя ли прокомментировать, откуда взялось 130 ?! smile

Добавлено через 1 минуту и 13 секунд
Цитата(boostcoder @  14.2.2011,  02:00 Найти цитируемый пост)
 чтоб избавиться от баяна чаров?

а кто такой "баян" в данном контексте ?


--------------------
http://opendots.net
PM MAIL WWW   Вверх
boostcoder
Дата 14.2.2011, 21:47 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
Цитата(mes @  14.2.2011,  21:36 Найти цитируемый пост)
нельзя ли прокомментировать, откуда взялось 130 ?!

не уверен, но полагаю, что это из-за нулевого символа добавляемого в конец хешируемой строки, и того = 129. или что?
Цитата(mes @  14.2.2011,  21:36 Найти цитируемый пост)
а кто такой "баян" в данном контексте ?

вот. ну чем не баян? ;)
Цитата(boostcoder @  14.2.2011,  03:00 Найти цитируемый пост)
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \
      "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" "\0\0\0\0" \




--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
mes
Дата 14.2.2011, 21:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250
Цитата(boostcoder @  14.2.2011,  20:47 Найти цитируемый пост)
не уверен, но полагаю,

все дошло.. я  "баян" забыл посчитать..  smile

Добавлено через 1 минуту и 7 секунд
а пример тремя постами выше с шаблонной рекурсией подошел ? или еще не пробовали ?



--------------------
http://opendots.net
PM MAIL WWW   Вверх
boostcoder
Дата 14.2.2011, 22:03 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
Цитата(mes @  14.2.2011,  21:59 Найти цитируемый пост)
или еще не пробовали ?

завтра буду пробовать. сегодня повод, как ни как smile

Добавлено через 11 минут и 55 секунд
вот.
проверил.
ничего не пришлось допиливать smile
Код

#include <iostream>

template<size_t N, size_t I=0>
struct hash_calc
{
    static constexpr size_t apply (const char (&s)[N])
    {
       return  (hash_calc<N, I+1>::apply(s) ^ s[I]) * 16777619u;
    };
};
template<size_t N>
struct hash_calc<N,N>
{
    static constexpr size_t apply (const char (&s)[N])
    {
       return  2166136261u;
    };
};
template<size_t N>
constexpr size_t hash ( const char (&s)[N] )
{
    return hash_calc<N>::apply(s);
}

int main() {
   char a[] = "1234";
   std::cout << std::hex << hash(a) << std::endl;
   std::cout << std::hex << hash("1234") << std::endl;
}




--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
GoldFinch
Дата 14.2.2011, 22:17 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата



****


Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: 15
Всего: 26
кстати да, FNV1-a не лучший хеш для этой задачи, надо бы поискать что получше
PM MAIL ICQ   Вверх
boostcoder
Дата 14.2.2011, 22:19 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
Цитата(GoldFinch @  14.2.2011,  22:17 Найти цитируемый пост)
FNV1-a не лучший хеш для этой задачи

гугл меня вчера завел на какой-то сайт, и там была куча его разновидностей, и букв. потому не осилил smile

Добавлено через 5 минут и 58 секунд
тему переименовал. не теряйтесь smile


--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
Abyx
Дата 16.2.2011, 01:29 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 601
Регистрация: 3.11.2009

Репутация: 1
Всего: 10
нда.. похоже что кроме как генерацией кучи шаблонов, циклов для constexpr не получить.


насчет хеширования строк:
http://bretm.home.comcast.net/~bretm/hash/7.html - если верить этой статье, Bob Jenkins' hash достаточно хорош для строк (а crc32 очень плох)
надо будет попробовать реализовать его для constexpr.

код: http://burtleburtle.net/bob/c/lookup3.c
PM MAIL   Вверх
Abyx
Дата 16.2.2011, 13:11 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 601
Регистрация: 3.11.2009

Репутация: 1
Всего: 10
также надо бы подумать о надежном применении хешей для switch
как минимум надо чтобы небыло коллизий между хешами меток в одном switch'e
можно также потребовать чтобы коллизий не было во всей единице трансляции, это слишком строгое требование, но возможно его проще реализовать
PM MAIL   Вверх
mes
Дата 16.2.2011, 20:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


любитель
****


Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250
Цитата(Abyx @  16.2.2011,  12:11 Найти цитируемый пост)
как минимум надо чтобы небыло коллизий между хешами меток в одном switch'e

ну switch, насколько я знаю, просто напросто не нужен.. а для проверки коллизий, можно использовать карту соответствий, которая так и так составляется.. исхожу из ранее приведенных boostcoder`ом данных. 
smile


--------------------
http://opendots.net
PM MAIL WWW   Вверх
boostcoder
Дата 16.2.2011, 20:15 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


pattern`щик
****


Профиль
Группа: Завсегдатай
Сообщений: 5458
Регистрация: 1.4.2010

Репутация: 49
Всего: 110
Цитата(Abyx @  16.2.2011,  13:11 Найти цитируемый пост)
как минимум надо чтобы небыло коллизий между хешами меток в одном switch'e

не понимаю в чем проблема... если коллизия произойдет, компилятор вам об этом скажет:
Цитата

error: duplicate case value
error: previously used here



--------------------
компилятор онлайн с поддержкой C++11
сборки компиляторов MinGW
PM WWW   Вверх
Abyx
Дата 16.2.2011, 20:28 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 601
Регистрация: 3.11.2009

Репутация: 1
Всего: 10
хм.. действительно
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1372 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.