Добро пожаловать на Pro Pawn - Портал о PAWN-скриптинге.
Показано с 1 по 9 из 9
  1. #1
    Аватар для Anve
    Пользователь

    Статус
    Оффлайн
    Регистрация
    04.01.2018
    Сообщений
    15
    Репутация:
    0 ±

    hashmap.inc - реализация хеш-карты в Pawn

    hashmap.inc
    github
    Что это?
    Инклуд, позволяющий создавать и работать с хеш-картой. Подробнее о хеш-карте вы можете прочитать здесь.

    Преимущества:
    • Легко в использовании
    • Нет зависимостей
    • Много функций


    Как это работает?
    Создаётся массив с размером 256(MAX_HASHMAP_SIZE) ячеек. При добавлении строка(ключ) хешируется и этот хеш является индексом массива. Во всех последующих операциях(поиск/удаление и т.д.) со строкой происходит тоже самое, однако размер массива довольной маленький, из-за чего могут возникнуть коллизии. Решением данной проблемы является увеличение макроса MAX_HASHMAP_SIZE.

    Возможные предупреждения, выводимые в консоль & Ошибки
    Ошибки
    Инклуд имеет следующие замакросенные ошибки:

    HASHMAP_ERROR_OK
    Описание: Обозначает, что ошибок нет, и всё выполнено успешно.

    HASHMAP_ERROR_OCCUPIED
    Описание: Обозначает, что в ячейке массива уже записано значение, ошибка возможна при возникновении коллизии.

    HASHMAP_ERROR_NOT_FOUND
    Описание: Обозначает, что значение не было найдено.

    Предупреждения
    Если консоле вы заметили следующее предупреждение: "[HashMap] Element "%s" already registered", то это говорит о следующем:
    1. Произошла коллизия при добавлении, и значение не было записано
    2. Вы указали строку, с помощью которой уже было записано ранее значение, и произойдёт выше написанное


    Конфигурационные макросы

    Название По умолчанию Описание
    MAX_HASHMAP_SIZE 256 Максимальный размер массива хеш-карты

    Callbacks & Функции
    Callbacks

    OnHashMapFind
    Определяется как: OnHashMapFind(error, value)
    Описание: Вызывается после поиска значения.
    Параметры:
    • error - передается в виде одной из вышеприведённых ошибок
    • value - найденное(или нет) значение


    Пример использования
    PHP код:
    public OnHashMapFind(errorvalue)
    {
      switch(
    error)
      {
        case 
    HASHMAP_ERROR_OKprintf("Value: %d",value);
      }

    Функции & Операции

    HashMap_Emplace - Добавление нового элемента в хеш-карту
    Параметры:
    • Хеш-карта
    • Ключ
    • Значение

    Возвращаемое значение: одна из вышеприведённых ошибок.

    Пример использования
    PHP код:
    public OnGameModeInit()
    {
      new 
    HashMap:Map<>;
      
    HashMap_Emplace(Map,"key",10); // Добавит новый элемент с ключом "key" и значением 10


    HashMap_Find - Поиск элемента по ключу
    Параметры:
    • Хеш-карта
    • Ключ

    Возвращаемое значение: значение элемента / ошибку HASHMAP_ERROR_NOT_FOUND.

    Пример использования
    PHP код:
    public OnGameModeInit()
    {
      new 
    HashMap:Map<>;
      
    HashMap_Emplace(Map,"key",10);
      new 
    value HashMap_Find(Map,"key");
      
    printf("Value: %d",value);


    HashMap_Erase - Удаление элемента из хеш-карты
    Параметры:
    • Хеш-карта
    • Ключ

    Возвращаемое значение: одна из вышеприведённых ошибок.

    Пример использования
    PHP код:
    public OnGameModeInit()
    {
      new 
    HashMap:Map<>;
      
    HashMap_Emplace(Map,"key",10);
      
    HashMap_Erase(Map,"key"); // Удалит элемент с ключом "key"


    HashMap_Count - Получение кол-ва записанных в хеш-карту элементов
    Параметры:
    • Хеш-карта

    Возвращаемое значение: кол-во элементов записанных в хеш-карту.

    Пример использования
    PHP код:
    public OnGameModeInit()
    {
      new 
    HashMap:Map<>;
      
    HashMap_Emplace(Map,"key",10);
      
    HashMap_Count(Map); // Вернёт 1


    HashMap_Size - Получение размера хеш-карты
    Параметры:
    • -

    Возвращаемое значение: MAX_HASHMAP_SIZE (вернёт в любом случае, ниже показан пример).

    Пример использования
    PHP код:
    public OnGameModeInit()
    {
      new 
    size HashMap_Size();
      
    printf("%d",size);


    HashMap_Clear - Очищение хеш-карты
    Параметры:
    • Хеш-карта

    Возвращаемое значение: HASHMAP_ERROR_OK.

    Пример использования
    PHP код:
    public OnGameModeInit()
    {
      new 
    HashMap:Map<>;
      
    HashMap_Emplace(Map,"key",10);
      
    HashMap_Clear(Map); // Очистит все созданные раннее элементы


    HashMap_Empty - Проверить, пуста ли хеш-карта
    Параметры:
    • Хеш-карта

    Возвращаемое значение: true или false.

    Пример использования
    PHP код:
    public OnGameModeInit()
    {
      new 
    HashMap:Map<>;
      
    HashMap_Emplace(Map,"key",10);
      
    HashMap_Empty(Map); // Вернёт 0, т.к. мы только что создали элемент
      
    HashMap_Clear(Map);
      
    HashMap_Empty(Map); // Вернёт 1, т.к. мы очистили хеш-карту

    Change Log

    Первая версия
    01/02/2018


    Версия 1.1
    02/02/2018


    • Добавлены функции HashMap_Clear и HashMap_Empty
    Последний раз редактировалось Anve; 02.02.2018 в 21:26.

  2. #2
    Аватар для Daniel_Cortez
    "Это не хак, это фича"

    Статус
    Оффлайн
    Регистрация
    06.04.2013
    Адрес
    Novokuznetsk, Russia
    Сообщений
    2,192
    Репутация:
    2589 ±
    https://github.com/AnveSamp/HashMap/...ashmap.inc#L40
    PHP код:
    #define HashMap_Hash(%1,%8new%2) \
            
    new%2; \
            for(new 
    i@HM 0; %1[i@HM]; i@HM++) %= (%37) ^ %1[i@HM]; \
    %
    = %MAX_HASHMAP_SIZE 
    И вместо хеш-функции опять самоделка с частыми коллизиями. Уже не смешно.
    Индивидуально в ЛС по скриптингу не помогаю. Задавайте все свои вопросы здесь (click).

  3. #3
    Аватар для Anve
    Пользователь

    Статус
    Оффлайн
    Регистрация
    04.01.2018
    Сообщений
    15
    Репутация:
    0 ±
    Цитата Сообщение от Daniel_Cortez Посмотреть сообщение
    https://github.com/AnveSamp/HashMap/...ashmap.inc#L40
    PHP код:
    #define HashMap_Hash(%1,%8new%2) \
            
    new%2; \
            for(new 
    i@HM 0; %1[i@HM]; i@HM++) %= (%37) ^ %1[i@HM]; \
    %
    = %MAX_HASHMAP_SIZE 
    И вместо хеш-функции опять самоделка с частыми коллизиями. Уже не смешно.
    Даже не смотря на то, что это не супер-мега хеш-функция, коллизия может возникнуть лишь из-за последней операции, и в топике написано по какой причине и как её решить. Если же вы считаете, что я ошибаюсь, я предлагаю вам показать пример строк, из-за которых может возникнуть коллизия, дабы не быть пустословом (Действительно, не смешно брать пример из юмористического командного процессора)
    Последний раз редактировалось Anve; 02.02.2018 в 16:07.

  4. #4
    Аватар для Anve
    Пользователь

    Статус
    Оффлайн
    Регистрация
    04.01.2018
    Сообщений
    15
    Репутация:
    0 ±
    Версия 1.1 - добавлены новые функции
    Добавлены функции HashMap_Clear и HashMap_Empty.
    Подробнее об этих функциях вы можете узнать в первом посте.

  5. #5
    Аватар для VVWVV
    ?

    Статус
    Оффлайн
    Регистрация
    09.07.2015
    Сообщений
    731
    Репутация:
    353 ±
    Все же лучше делать хеш-таблицы в Pawn через плагины.

  6. #6
    Аватар для Anve
    Пользователь

    Статус
    Оффлайн
    Регистрация
    04.01.2018
    Сообщений
    15
    Репутация:
    0 ±
    Цитата Сообщение от VVWVV Посмотреть сообщение
    Все же лучше делать хеш-таблицы в Pawn через плагины.
    Конечно ты прав, но тем не менее я попытался сделать что-то подобное не в виде костыля.
    Кстати на моём гите лежит хеш-таблица в виде плагина.

  7. #7
    Аватар для Geebrox
    Пользователь

    Статус
    Оффлайн
    Регистрация
    24.08.2015
    Адрес
    Ташкент
    Сообщений
    375
    Репутация:
    97 ±
    Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется коллизией. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50%
    То есть при использование этого инклюда есть вероятность, что каждый второй элемент может быть коллизией?

    И ещё можно было бы переименовать HashMap_Empty на HashMap_IsEmpty, было бы логичнее, ибо такое название больше подходит для очисти, а не проверки. Ну это просто предложение.
    Последний раз редактировалось Geebrox; 02.02.2018 в 19:07.

  8. #8
    Аватар для Anve
    Пользователь

    Статус
    Оффлайн
    Регистрация
    04.01.2018
    Сообщений
    15
    Репутация:
    0 ±
    Цитата Сообщение от Geebrox Посмотреть сообщение
    То есть при использование этого инклюда есть вероятность, что каждый второй элемент может быть коллизией?
    Всё зависит от кол-ва уже записанных элементов и размера.
    Цитата Сообщение от Anve Посмотреть сообщение
    Решением данной проблемы является увеличение макроса MAX_HASHMAP_SIZE.

    Цитата Сообщение от Geebrox Посмотреть сообщение
    И ещё можно было бы переименовать HashMap_Empty на HashMap_IsEmpty, было бы логичнее, ибо такое название больше подходит для очисти, а не проверки. Ну это просто предложение.
    Переименую в следующей версии.
    Последний раз редактировалось Anve; 02.02.2018 в 19:29.

  9. #9
    Аватар для Daniel_Cortez
    "Это не хак, это фича"

    Статус
    Оффлайн
    Регистрация
    06.04.2013
    Адрес
    Novokuznetsk, Russia
    Сообщений
    2,192
    Репутация:
    2589 ±
    Цитата Сообщение от Anve Посмотреть сообщение
    Действительно, не смешно брать пример из юмористического командного процессора
    Хорошая попытка перевести стрелки.


    Цитата Сообщение от Anve Посмотреть сообщение
    Даже не смотря на то, что это не супер-мега хеш-функция
    Так я и не говорю, что эта функция должна быть какой-то "супер-мега". Всякие "мегасложные" функции типа MurmurHash2, CityHash etc. сделаны так, чтобы обрабатывать данные блоками по 4 или 8 байт за итерацию, чтобы максимально эффективно использовать ресурсы ЦП.
    Однако, в Pawn своя VM, свой набор инструкций, да и строки по умолчанию кодируются по 1 символу на ячейку (4 байта), поэтому понты с обработкой по 4 символа из строки вместо 1 за раз ничего хорошего не принесут. Самыми эффективными в Pawn будут хеш-функции, которые в то же время и самые простые, обрабатывающие по 1 символу за итерацию, вроде хеша Дженкинса (one-at-a-time) или FNV1a - кстати говоря, именно эти функции и были реализованы в y_stringhash.


    Цитата Сообщение от Anve Посмотреть сообщение
    коллизия может возникнуть лишь из-за последней операции, и в топике написано по какой причине и как её решить.
    Дело не в "урезании" хеша под размер таблицы, а в том, что функция сама по себе выдаёт много коллизий, даже без вычисления остатка от деления в конце.


    Цитата Сообщение от Anve Посмотреть сообщение
    Если же вы считаете, что я ошибаюсь, я предлагаю вам показать пример строк, из-за которых может возникнуть коллизия, дабы не быть пустословом
    Получите, распишитесь: https://github.com/Daniel-Cortez/hash-collision-test

    Код:
    Loading the dictionary from file "../words_alpha.txt"...
    Loaded 370099 words
    
    Testing: std::unordered_map hash function...
    Found 14 collisions
    
    Testing: MurmurHash2A...
    Found 15 collisions
    
    Testing: MurmurHash3_x86_32...
    Found 13 collisions
    
    Testing: lookup3...
    Found 15 collisions
    
    Testing: one-at-a-time...
    Found 25 collisions
    
    Testing: FNV1a_32...
    Found 13 collisions
    
    Testing: AnveCMD_Hash...
    Found 248222 collisions
    
    Testing: AnveHashMap_Hash...
    Found 97932 collisions
    Я использовал этот фреймворк для выбора хеш-функции в одной из последних версий DC_CMD; даже не думал, что он мне ещё когда-нибудь пригодится.
    Как можно увидеть из лога, я использовал словарь из 370 тыс. слов на английском. Скажете, слишком много? Взгляните на результаты - у всех нормальных функций из этих 370 тысяч слов нашлось всего 13-25 пар с одинаковыми хешами. Ожидаемо отличились только ваши хеш-функции из "шуточного" AnveCMD и hashmap.inc - 248 и 98 тыс. коллизий соответственно. Конечно, в hashmap.inc наблюдается прогресс по сравнению с AnveCMD, но совпадающих хешей всё ещё очень много.


    Цитата Сообщение от Anve Посмотреть сообщение
    Конечно ты прав, но тем не менее я попытался сделать что-то подобное не в виде костыля.
    Кстати на моём гите лежит хеш-таблица в виде плагина.
    Плагин с потенциалом предоставления возможностей C/C++ в Pawn - костыль.
    Инклуд на Pawn с ограниченным размером таблицы - хорошее решение.
    Л - логика.


    Вообще сам релиз едва ли походит на что-то хоть немного серьёзное - скорее то ли на очередную унылую "шутку", то ли на попытку выложить откровенную чепуху, чтобы спровоцировать спор. Ни то, ни другое на форуме не приветствуется.

    Тема закрыта.


    P.S.: Мне пришлось потратить полтора часа личного времени на подготовку к публикации исходников и написание этого поста. Можете собой гордиться.
    Индивидуально в ЛС по скриптингу не помогаю. Задавайте все свои вопросы здесь (click).

  10. Пользователь сказал cпасибо:
    $continue$ (03.02.2018)
 

 

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •