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

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

Хеши в среднем O(1), если размер словаря к количеству ожидаемых элементов разрешает.
А дальше идет зависимость от реализаций по разруливанию коллизий, это может быть через список, может быть еще подхеш....

Мое терминологическое невежество мешает процессу вникания. Дождусь примеров. Хотелось бы лаконичных и по делу - ордера, тики и подобное.

 
fxsaber:

Мое терминологическое невежество мешает процессу вникания. Дождусь примеров. Хотелось бы лаконичных и по делу - ордера, тики и подобное.


Ордера в топку. Интересуют сделки.

 
fxsaber:

Прочел на вики. Тот случай, когда совсем не понимаешь логику интуитивных рассуждений.


365 дней - это лимит на размер словаря
количество учеников в классе - это ожидаемое количество элементов в коллекции
совпадения дней рождения - это коллизия

 
Sergey Dzyublik:

365 дней - это лимит на размер словаря
количество учеников в классе - это ожидаемое количество элементов в коллекции
совпадения дней рождения - это коллизия

Спасибо, такое терминологическое определение понятнее. Только не понимаю, какое отношение данный "парадокс" имеет к теме ветки?

 
Sergey Dzyublik:

365 дней - это лимит на размер словаря
количество учеников в классе - это ожидаемое количество элементов в коллекции
совпадения дней рождения - это коллизия


В данном примере хеш - это день рождения ученика.
У нас есть шкаф с 365 полочками в которых лежат дневники учеников.
Мы положили каждый дневник на полочку отвечающую дню рождения ученика.

Нам нужен дневник ученика Петрова и мы знаем когда он народился.
Теперь по дню рождения за O(1) мы легко можем найти дневник Петрова, как и дневник любого другого ученика.
Исключением являются случаи когда два ученика имеют один и тот же день рождения - это называется коллизия.

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


Если интересует тема - советую курс от MailRu на youtube об алгоритмах и структурах данных.

 
Sergey Dzyublik:

В данном примере хеш - это день рождения ученика.
У нас есть шкаф с 365 полочками в которых лежат дневники учеников.
Мы положили каждый дневник на полочку отвечающую дню рождения ученика.

Нам нужен дневник ученика Петрова и мы знаем когда он народилсяю
Теперь по дню рождения за O(1) мы легко можем найти дневник Петрова как и другого ученика.
Исключением являются случаи когда два ученика имеют один и тот же день рождения - это называется коллизия.

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


Если интересует тема - советую курс от MailRu на youtube об алгоритмах и структурах данных.

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

 
fxsaber:

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


Выделенное это словесные опечатки)) И уже подправлены.
Хеш является индексом. Он приводится к размеру словаря.

Каждая полочка имеет одинаковую высоту и по номеру полочки можно точно знать на какой высоте ее искать. O(1)

 

Максимально просто об ассоциативном массиве #1

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

Разберем словарь мы на очень простом примере: обычном словаре слов. Предположим, что у нас есть всего несколько таких слов, и все они начинаются на разные буквы алфавита:

string words[] = {"apple", "cat", "fog", "dog", "walk", "zero"};

Английский алфавит содержит 26 символов. Создадим массив строк, размерностью 26 элементов:

string dictionary[26];

Теперь, если договориться хранить слова в индексах соответствующим их первой букве мы получим простейший словарь. Индексацию будем делать с нуля. Слово "apple" будет храниться у нас по индексу 0, потому что символ 'a' - первая буква алфавита, "cat" - по индексу 1, "dog" - по индексу 3, fog - будет занимать индекс  4, walk - индекс 24 и zero - последний 25 индекс. 

Замечу что индексы с 5 по 23 не будут использованы. Это дополнительный расход памяти, зато мы можем мгновенно обратиться например к слову "walk", потому что знаем, что если оно есть, то находится по индексу 24.

Напишем первый наш пустой словарь:

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
string words[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   if(words[index] == NULL)
   {
      words[index] = word;
      return true;
   }
   return false;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   Add("apple");
   if(Contains("apple"))
      printf("Словарь содержит слово apple");
   else
      printf("Словарь не содержит слово apple");
  }
//+------------------------------------------------------------------+

Если в него добавить слово "apple" а потом найти его, то операция поиска доступа к этому слову будет мгновенной. Потому что мы заранее знаем индекс, по которому это слово может находится. Других вариантов индекса быть не может, поэтому перебор всего списка не требуется. Примерно на этом свойстве основаны все словари.

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

 

Максимально просто об ассоциативном массиве #2

Бывает так, что разные слова начинаются на одну и туже букву алфавита. Если в наш предыдущий словарь мы поместим слово "apple", а затет попытаемся поместить туда "application" то ничего не выйдет. Индекс 0 уже будет занят словом apple. В данном случае говорят о коллизии хеш-функции. Наша хеш-функция очень простая - она возвращает номер первого символа слова, поэтому коллизии в этой функции будут очень часты. Что бы хранить разные слова начинающиеся на одинаковую букву, сделаем дополнение: будем хранить элементы не в массиве, а в массиве массивов. Тогда по индексу 0 будет еще один массив содержащий два слова: "apple" и "application":

//+------------------------------------------------------------------+
//|                                                         Dict.mq5 |
//|                        Copyright 2017, MetaQuotes Software Corp. |
//|                                              http://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Copyright 2017, MetaQuotes Software Corp."
#property link      "http://www.mql5.com"
#property version   "1.00"
#include <Arrays\ArrayObj.mqh>
#include <Arrays\ArrayString.mqh>
CArrayString* WordsArray[26];

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words = WordsArray[index];
   if(words == NULL)
      return false;
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return true;
   return false;
}
bool Add(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   CArrayString* words;
   if(WordsArray[index] == NULL)
      WordsArray[index] = new CArrayString();
   words = WordsArray[index];
   for(int i = 0; i < words.Total(); i++)
      if(word == words.At(i))
         return false;
   words.Add(word);
   return true;
}
//+------------------------------------------------------------------+
//| Script program start function                                    |
//+------------------------------------------------------------------+
void OnStart()
  {
//---
   //ArrayResize(WordsArray, 26);
   Add("apple");
   Add("application");
   if(Contains("application"))
      printf("Словарь содержит слово application");
   else
      printf("Словарь не содержит слово application");
  }
//+------------------------------------------------------------------+

Теперь наш словарь хранит слова, даже начинающиеся на одну и туже букву. Но вот цена доступа к словам с одинаковой первой буквы возрастает. Потому что теперь требуется полный перебор всех слов, начинающихся на 'a', что бы понять, есть слово 'application' в словаре или нет. Если бы наша хеш функция выдавала бы разные числа даже если слова различались на один символ, тогда вероятность перебора слов с одинаковыми индексами стремилась бы к нулю, и доступ к произвольному элементу стремился бы к o(1). В настоящих словарарях именно так и присходят, функции которые там используются устойчивы к появлениям коллизций, поэтому мы с определенностью можем утверждать, что доступ к элементам в этих коллекциях происходит очень быстро и практически без перебора.

 
Vasiliy Sokolov:

Максимально просто об ассоциативный массиве

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

Разберем словарь мы на очень простом примере: обычном словаре слов. Предположим, что у нас есть всего несколько таких слов, и все они начинаются на разные буквы алфавита:

Английский алфавит содержит 26 символов. Создадим массив строк, размерностью 26 элементов:

Теперь, если договориться хранить слова в индексах соответствующим их первой букве мы получим простейший словарь. Индексацию будем делать с нуля. Слово "apple" будет храниться у нас по индексу 0, потому что символ 'a' - первая буква алфавита, "cat" - по индексу 1, "dog" - по индексу 3, fog - будет занимать индекс  4, walk - индекс 24 и zero - последний 25 индекс. 

Замечу что индексы с 5 по 23 не будут использованы. Это дополнительный расход памяти, зато мы можем мгновенно обратиться например к слову "walk", потому что знаем, что если оно есть, то находится по индексу 24.

Напишем первый наш пустой словарь:

Если в него добавить слово "apple" а потом найти его, то операция поиска доступа к этому слову будет мгновенной. Потому что мы заранее знаем индекс, по которому это слово может находится. Других вариантов индекса быть не может, поэтому перебор всего списка не требуется. Примерно на этом свойстве основаны все словари.

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

Решение идеально. Все максимально просто. Только функции, массивы и правильная организация данных. Я про это и говорил.
123456789101112...37
Новый комментарий
Причина обращения: