Библиотека Generic классов - ошибки, описание, вопросы, особенности использования и предложения - страница 10

Новый комментарий
 

О хеш-функциях

Из предыдущих примеров становится ясно, что основную нагрузку берет на себя хеш-функция. Хеш функцию можно сделать максимально быстрой, но скорее всего в этом случае она будет сильно подвержена коллизиям. И наоборот, хеш-функцию можно сделать максимально устойчивой к появлению коллизий, но ее вычислительная сложность будет неадекватна к выполняемой задачи. Разберем два крайних примера. Пример 1, максимально быстрая хеш-функция:

int GetHashCode(string word)
{
   return 0;
}

Всегда будет возвращать одно и тоже число. Если наш словарь будет хранить только одно слово, то ее работы будет достаточно, т.к. это слово будет находится по индексу 0. Однако если слов будет 10, тогда все десять слов будут находится в нулевом индексе (не забываем, что у нас массив массивов).

Для второго примера обратимся к обратимому шифрованию, например на основе сети Фейстеля с количеством раундов N. Это не хеш-функция, и она не подвержена коллизиям совсем. Т.е. для двух разных строк мы получим гарантированно разные числа. Длина полученных чисел будет равна длине строки. Следовательно для строки длиной 1000 символов мы получим массив uchar размерностью 1000. Если нам нужно хранить эту строку в словаре размером 3 элемента, то согласитесь странно вычислять такой сложный код, для поиска слова всего из трех элементов.

Следовательно, всегда нужно искать золотую середину (как это было верно подмечено fxsaber'ом): нам необходима такая функция, которая быстро вычисляла бы хеш и как правило не давала бы коллизий. Давайте прикинем вероятность появления коллизий у нашей предыдущей хеш-функции:

int GetHashCode(string word)
{
   int index = StringGetCharacter(word, 0)-'a';
}

В алфавите 26 символов. Будем считать, что количество слов начинающихся на символ 'a' равна количеству слов начинающихся на любой другой символ. Тогда если в нашем словаре 988 слов, то 38 из них будут начинаться на букву a, 38 - на букву b, 38 - на букву c, ... 38 - на букву w и 38 на букву - z. Вероятность возникновения коллизии в каждом случае будет 1/26 или 3.8461%. Если у нас 988 слов, тогда получим 988*3.8461 = 37.999 слов на каждый индекс.

Понятно, что чем больше слов на одну и туже букву, тем сложнее найти конкретное слово. В нашем случае потребуется не только вычислить индекс первой буквы, но и перебрать все слова, которые также начинаются на эту же букву, что бы уже сравнить слова точно. Что бы этого не было, можем усложнить хеш-функцию:

int GetHashCode(string word)
{
   uchar i1 = (uchar)word[0]-'a';
   uchar i2 = (uchar)word[1]-'a';
   int hash = i1<<(sizeof(uchar)*8);
   hash += i2;
   return hash;
}

Т.е. мы берем уже два первых символа одного слова. Тогда возможных комбинаций будет не 26, а 26^2 = 676. Замечу, что сложность второго варианта вычисления хеш функции возросла линейно, грубо говоря в два раза, в том время как ее стойкость к коллизиям возросла нелинейно, в квадрате. 

Для второго варианта, в среднем будет одна коллизия на каждые 676 слов. В нашем случае, для 988 слов будет 988/676 = 1.4615 коллизии на каждый индекс. Т.е. каждый индекс будет содержать в среднем либо одно слово, либо 2 слова. Т.е. в среднем перебора не будет вовсе (одно сравнение), либо он будет очень коротким (два сравнения).

Если отношение размер словаря к кобминациям хеш-функции стремиться к 1.0000000, то в среднем, никакого перебора не понадобиться, т.к. каждый элемент будет располагаться по своему индексу в одиночестве. Если хеш-функция будет выдавать очень большой диапазон значений, то отношение размер словаря к возможным комибинациям хеш функции всегда будет даже меньше 1.0. Например если хеш-функция будет выдвать 2^32 комбинаций тогда для любого размера N меньше 2^32 будет выполняться отношение N/2^32 < 1.0. Если N очень мало, то мы просто нормируем число полученное хеш-функцией, таким образом, что бы оно всегда находилось в пределе N:

int index = GetHashCode(word)%ArraySize(m_array);

Если хеш-функция выдает результаты равномерно, то в среднем, мы будем получать отношение 1.000. т.е. в одном индексе массива будет располагаться только одно слово. Таким образом можно сказать, что словарь это частный случай массива, в котором вместо индекса указывается ключ.

 
Реter Konow:

Размер массива можно легко менять под размер словаря.

Бесконечные варианты в расчет не брал.

В том то и дело, что размер словаря часто не известен. Простой пример, допустим, у нас торгует советник. Он отслеживает совершенные сделки. После появления сделки в истории, требуется связать эту сделку допустим с меджиком эксперта. Для этого логично использовать словарь. Где в качестве ключа (уникального идентификатора) используется номер сделки, а в качестве значения - магический номер эксперта. Проблема в том, что при запуске советника ни как нельзя определить заранее будут ли у нас 100 сделок, 1000 или вообще ни одной. Сколько памяти за ранее не выделяй, ее все равно будет либо мало, либо слишком много.

 
Vasiliy Sokolov:

В том то и дело, что размер словаря часто не известен. Простой пример, допустим, у нас торгует советник. Он отслеживает совершенные сделки. После появления сделки в истории, требуется связать эту сделку допустим с меджиком эксперта. Для этого логично использовать словарь. Где в качестве ключа (уникального идентификатора) используется номер сделки, а в качестве значения - магический номер эксперта. Проблема в том, что при запуске советника ни как нельзя определить заранее будут ли у нас 100 сделок, 1000 или вообще ни одной. Сколько памяти за ранее не выделяй, ее все равно будет либо мало, либо слишком много.

Ну так понятно, что задачи разные бывают.

Я решал задачу в которой нужно было создать удобный словарь для одного человеческого языка. Размер моего массива не точен, но в чем проблема подогнать его под количество слов определенного языка? Он там легко поместится.

Например русский язык. Допустим содержит 10 000 основных слов. Все эти слова можно прекрасно поместить в моем массиве.

Первое измерение - 66 букв (малые и большие), второе измерение - количество букв в слове (до 25 например), третье измерение - совпадения по первой букве и количеству букв - 50.

Весь язык поместиться.

//----------------------------

Изначально, я решал именно эту задачу. Вы сейчас подменяете исходную задачу другой и говорите, что решение не годится.

 
Vasiliy Sokolov:

 Сколько памяти за ранее не выделяй, ее все равно будет либо мало, либо слишком много.

Верно.

Также верно как и то, что небывает универсального решения для всех задач.

 
Реter Konow:

Верно.

Также верно как и то, что небывает универсального решения для всех задач.

Совершенно бесспорно.

 
Sergey Dzyublik:

Потише товарищ. От ошибок никто не застрахован, даже ты. Поэтому будь добр, указывай на ошибки других в более мягком тоне. Сейчас исправлю.

 
Alexey Viktorov:

А правильный вариант останется в секрете???


Правильного варианта хеш-таблиц и хешей в принципе быть не может - все зависит от конкретных целей и условий применения.
Это как приготовление бутерброда. Может кто-то не есть майонез или кетчуп, или он веган....
Но намазывать кетчуп на стол и ложить на него хлеб - тут как бы понятно, что это не то....


Основы по теме для ленивых:
https://www.slideshare.net/mkurnosov/6-32402313

В реальности все намного сложнее и обсуждается в соответсвующей литературе или на хороших курсах "алгоритмы и структуры данных".

Лекция 6: Хеш-таблицы
Лекция 6: Хеш-таблицы
  • 2014.03.17
  • Mikhail Kurnosov, Associate Professor (Docent) Follow
  • www.slideshare.net
Лекция 6 Хеш-таблицы Курносов Михаил Георгиевич к.т.н. доцент Кафедры вычислительных систем Сибирский государственный университет телекоммуникаций и информатик…
 

Короче, хеш-функция должна работать первое: быстро, второе - нет надобности придумывать что-то совсем сложное, т.к. появление одних и тех же значений нормально разруливается внутри словаря прямым перебором. Главное, что бы не было слишком частых коллизий вот и все. В Generic за хеш функции базовых типов отвечает набор функций в файле HashFunction.mqh. Что бы убедиться, что там все просто, посмотрим как он устроен:

//+------------------------------------------------------------------+
//|                                                 HashFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
//+------------------------------------------------------------------+
//| Unioun BitInterpreter.                                           |
//| Usage: Provides the ability to interpret the same bit sequence in|
//|        different types.                                          |
//+------------------------------------------------------------------+
union  BitInterpreter
  {
   bool              bool_value;
   char              char_value;
   uchar             uchar_value;
   short             short_value;
   ushort            ushort_value;
   color             color_value;
   int               int_value;
   uint              uint_value;
   datetime          datetime_value;
   long              long_value;
   ulong             ulong_value;
   float             float_value;
   double            double_value;
  };
//+------------------------------------------------------------------+
//| Returns a hashcode for boolean.                                  |
//+------------------------------------------------------------------+
int GetHashCode(const bool value)
  {
   return((value)?true:false);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for character.                                |
//+------------------------------------------------------------------+
int GetHashCode(const char value)
  {
   return((int)value | ((int)value << 16));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned character.                       |
//+------------------------------------------------------------------+
int GetHashCode(const uchar value)
  {
   return((int)value | ((int)value << 16));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for short.                                    |
//+------------------------------------------------------------------+
int GetHashCode(const short value)
  {
   return(((int)((ushort)value) | (((int)value) << 16)));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned short.                           |
//+------------------------------------------------------------------+
int GetHashCode(const ushort value)
  {
   return((int)value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for color.                                    |
//+------------------------------------------------------------------+
int GetHashCode(const color value)
  {
   return((int)value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for integer.                                  |
//+------------------------------------------------------------------+
int GetHashCode(const int value)
  {
   return(value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned integer.                         |
//+------------------------------------------------------------------+ 
int GetHashCode(const uint value)
  {
   return((int)value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for datetime.                                 |
//+------------------------------------------------------------------+
int GetHashCode(const datetime value)
  {
   long ticks=(long)value;
   return(((int)ticks) ^ (int)(ticks >> 32));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for long.                                     |
//+------------------------------------------------------------------+
int GetHashCode(const long value)
  {
   return(((int)((long)value)) ^ (int)(value >> 32));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for unsigned long.                            |
//+------------------------------------------------------------------+  
int GetHashCode(const ulong value)
  {
   return(((int)value) ^ (int)(value >> 32));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for float.                                    |
//+------------------------------------------------------------------+
int GetHashCode(const float value)
  {
   if(value==0)
     {
      //--- ensure that 0 and -0 have the same hash code
      return(0);
     }
   BitInterpreter convert;
   convert.float_value=value;
   return(convert.int_value);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for string.                                   |
//+------------------------------------------------------------------+
int GetHashCode(const double value)
  {
   if(value==0)
     {
      //--- ensure that 0 and -0 have the same hash code
      return(0);
     }
   BitInterpreter convert;
   convert.double_value=value;
   long lvalue=convert.long_value;
   return(((int)lvalue) ^ ((int)(lvalue >> 32)));
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for string.                                   |
//| The hashcode for a string is computed as:                        |
//|                                                                  |
//| s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]                     |
//|                                                                  |
//| using int arithmetic, where s[i] is the ith character of the     |
//| string, n is the length of the string, and ^ indicates           |
//| exponentiation. (The hash value of the empty string is zero.)    |
//+------------------------------------------------------------------+
int GetHashCode(const string value)
  {
   int len=StringLen(value);
   int hash=0;
//--- check length of string
   if(len>0)
     {
      //--- calculate a hash as a fucntion of each char
      for(int i=0; i<len; i++)
         hash=31*hash+value[i];
     }
   return(hash);
  }
//+------------------------------------------------------------------+
//| Returns a hashcode for custom object.                            |
//+------------------------------------------------------------------+
template<typename T>
int GetHashCode(T value)
  {
//--- try to convert to equality comparable object  
   IEqualityComparable<T>*equtable=dynamic_cast<IEqualityComparable<T>*>(value);
   if(equtable)
     {
      //--- calculate hash by specied method   
      return equtable.HashCode();
     }
   else
     {
      //--- calculate hash from name of object
      return GetHashCode(typename(value));
     }
  }
//+------------------------------------------------------------------+

Целочисленные типы либо возвращаются как есть, либо для коротких целочисленных типов используется не замысловатые битовые операции преобразования. Для типов не умещающихся в 32 разряда используется исключающее или с  последующим объединением правой и левой части. Для строк рассчитывается тоже не замысловатый хеш через прямой перебор. У вещественных чисел с помощью union берется битовое представление, и уже оно используется в качестве хеша.

 

Алгоритмы типа словарей условно делятся на две части:

  • Наборы пар ключ-значение, где ключ уникальный, а значение нет. В Generic это CHashMap
  • Наборы уникальных значений. В генерик это CHashSet.

Что такое CHashSet? Это коллекция (массив по своей сути) где каждый элемент уникален. Например в такой коллекции могут располагаться числа 2,5,1,7,10,15,1024. Но двух одинаковых чисел быть не может. Также в нем могут располагаться строки, вещественные числа и даже пользовательские сложные типы (об этом позже). Но для любого типа правило одно - другого такого же в словаре быть не может.

Что такое CHashMap? Это коллекция (тоже массив по своей сути), где каждым элементом является сложный тип ключ-значение:

template<typename TKey,typename TValue>
class CHashMap: public IMap<TKey,TValue>
  {
protected:
   int               m_buckets[];
   Entry<TKey,TValue>m_entries[];
   int               m_count;
   int               m_free_list;
   int               m_free_count;
   IEqualityComparer<TKey>*m_comparer;
   bool              m_delete_comparer;
};

Он устроен почти также как и CHashMap, но позволяет установить соответствие между двумя множествами так, что элемент множества 1 соответствует элементу множества 2. Это очень удобная штука, позволяющая писать очень эффективные алгоритмы запроса со среднем временем выполнения O(1). 

Позже на примерах разберем построение какого-нибудь соответствия.

Интересно, что любой словарь типа ключ - значение естественны образом устанавливает такое не тривиальное отношение как один ко многим. Например, у нас имеется куча исторических ордеров, и куча сделок, которые были выполнены на их основе. Каждой сделки соответствует только один ордер, но одному ордеру может соответствовать несколько сделок. Словарь такого отношения может хранить в качестве ключа номер сделки, а в качестве значения, номер ордера, который послужил для ее открытия.
 
Просьба не засорять ветку не по теме.
1...34567891011121314151617...37
Новый комментарий
Причина обращения: