3687 / 964 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
|
|||||||||||
1 | |||||||||||
hash строк16.01.2010, 17:36. Показов 11578. Ответов 23
Метки нет (Все метки)
Доброго времени суток! =)
Зачем: Для игры понадобилась база данных стандартных строк типа как данные для удобного перевода (всмысле весь текст вне игры). Чтобы в коде было удобнее обращаться к строкам хотелось бы ввести простые имена вида D12.S10 который допустим будет указывать на то что строка будет для диалога 12 и это будет 10 реплика. Это только пример и впринципе эти простые имена будут очень разные. Но чтобы обратиться к элементам массива строк нужен числовой индекс (иначе - смещение). В качестве этого индекса я буду использовать число возвращаемого из массива key в котором по индексу возвращаемого хэшем хранится реальный индекс где число лежит. Все это демонстрируется кодом:
Пока я написал что то вроде того, но помоему плохо очень
0
|
16.01.2010, 17:36 | |
Ответы с готовыми решениями:
23
Получить hash MD5 Hash посредством WinApi Hash+++ Hash - таблица |
16.01.2010, 18:17 | 2 |
А нельзя просто посчитать сумму байтов, из которых состоит строка и сделать её по модулю x (тогда результат будет в диапазоне от 0 до x). Как вариант из каждого байта ещё вычесть 32 (что соответствует пробелу), чтобы не пропадал диапазон начальных символов, которые не используются. Делаешь такую тупую реализацию, а потом проверяешь, насколько равномерно оно улеглось
Ну и вопрос на всякий случай: а стОит оно того? Если у тебя несколько сотен различных строк, то не проще ли забить соответствие в массив, отсортировать и дальше искать бинарным поиском?
1
|
3687 / 964 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
|
||||||
16.01.2010, 18:31 [ТС] | 3 | |||||
Скорее всего строк будет много. С другой стороны если их много вероятность коллизии ключа строки возрастает... просто мне хочется предпочесть скорость последующего обращения к строкам, пожертвовав небольшим количеством памяти. Если использовать поиск скорость обращения упадет. Хм, даже не знаю... не думаю что на много.
В общем я щас попробовал CRC вроде разные числа выдает
0
|
2924 / 1274 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
|
|
16.01.2010, 18:44 | 4 |
"Все уже украдено до нас!" (с)
У тебя написано class - стало быть, это C++. Что мешает использовать boost ? Там есть и эффективные (скоростные и отлаженные!) хешированные контейнеры, и готовые генераторы хешей.....
1
|
16.01.2010, 18:51 | 5 | |||||
> Скорее всего строк будет много
Тут главное не количество строк, а количество РАЗНЫХ строк > Мне кажется тогда для строк "АБ" и "БА" будут выдаваться одинаковые значения, хм... В книжке нашёл вот такой пример, ориентированный на строки
3
|
3687 / 964 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
|
|
16.01.2010, 18:52 [ТС] | 6 |
А оттуда точно можно их "изъять" без головомучительного трехгодового изучения запутаных мануалов на китайском?) Мне просто не нравится принцип по типу "нужно пройти одну остановку поэтому купим (украдем) вертолет") А вообще спасибо попробую, хотя интереснее самому реализовать, своё оно дороже, да и опыт. Кодю "для себя". В смысле самосовершенствуюсь.
Интересно, я обязательно попробую =) Не по теме: А я в какой то книжке читал что 42 лучше))
0
|
depict1
281 / 146 / 4
Регистрация: 11.07.2009
Сообщений: 606
|
|
16.01.2010, 18:59 | 8 |
в случае с бустом - вертолёт бесплатный. и летать на нём можно хоть до посинения.
0
|
16.01.2010, 18:59 | 9 |
> А я в какой то книжке читал что 42 лучше))
Да не суть, какое лучше. Это же зависит от того, что за строки. Имена переменных - одно, полные пути файлов - другое, интернетовские ссылки - третье. Просто экспериментальным путём можно прогнать несколько разных значений и выявить то, которое даёт наиболее ровное распределение в твоём случае
0
|
3687 / 964 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
|
|
16.01.2010, 19:53 [ТС] | 10 |
А топливо для вертолета, ремонтировать его... опятже ставить куда то надо)) Я в смысле зачем пушкой по мошкам) Ладно в любом случае я попробую потом посмотрим)
Добавлено через 40 минут Нашёл вот такую интересную вещь ещё http://www.azillionmonkeys.com/qed/hash.html Чтобы она возвращала unsigned short нужно сделать с результатом ^ (sizeof(unsigned short int)*8)?
0
|
2924 / 1274 / 114
Регистрация: 27.05.2008
Сообщений: 3,465
|
|
16.01.2010, 21:42 | 11 |
Вот как раз буст (как, впрочем, и STL) - вещь весьма нетривиальная в дизайне и внутреннем устройстве, но - очень и очень простая в использовании. Примерно как современный автомобиль - весьма сложно устроен "под капотом", но достаточно сесть, повернуть ключ и нажать газ......
Что же касается "изъять" - так в дистрибутив буста входит и специальная утилита bcp, которая автоматически извлекает из недр буста нужный тебе заголовок и все его зависимости впридачу.
1
|
3687 / 964 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
|
||||||
17.01.2010, 00:11 [ТС] | 13 | |||||
Ссылка работала и работает) Впрочем неважно
А если указать тип результата то наверное просто лишние биты обрежутся? мне нужно сжать большее число в меньшее число... хм
0
|
17.01.2010, 00:26 | 14 |
Если изменить тип процедуры с uint32_t на uint16_t, то отрежутся старшие части. Если такое не канает, то можно просто взять и выкинуть каждый чётный (или нечётный) бит и уплотнить оставшиеся 16 бит
0
|
3687 / 964 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
|
||||||
17.01.2010, 01:15 [ТС] | 15 | |||||
О, ещё понравилось вот это // источник http://rsdn.ru/article/alg/bintree/hash.xml
0
|
3687 / 964 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
|
|||||||||||
19.01.2010, 21:44 [ТС] | 17 | ||||||||||
К тому же Strings["any_key"] может использоваться в конктексте забора строки, так что она должна возвращать const char*. Возможно ли?
0
|
3687 / 964 / 114
Регистрация: 10.01.2010
Сообщений: 2,550
|
||||||||||||||||
20.01.2010, 00:19 [ТС] | 19 | |||||||||||||||
По смыслу мне надо вернуть ссылку на указатель char* но мне кажется это невозможно(( Создам пожалуй, если в ближайшее время сам не разберусь)
Добавлено через 40 минут отлично, чтобы вернуть ссылку на указатель нужно написать так const char*& operator[] (const char* newKey); и все ОК =) Добавлено через 26 минут однако, как выделить возвращаемой ссылке память? мне нужно выделить память под const char [] а строку взять из std::string т.е. нечто подобное
Добавлено через 44 минуты Потерял надежду на const char* сделал так, однако после memcpy никакого толку нет.
0
|
109 / 95 / 9
Регистрация: 19.02.2009
Сообщений: 312
|
|
16.08.2010, 14:16 | 20 |
Здесь можно найти простые, быстрые и понятные алгоритмы хэширования строк - в сравнении с тестированием на разных текстах.
0
|
16.08.2010, 14:16 | |
16.08.2010, 14:16 | |
Помогаю со студенческими работами здесь
20
Std::hash<.> PERFECT HASH FUNCTION Hash. Не получается написать хэш списки, вектора, map, Hash Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |