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

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

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

Коллизия при любом уровне эффективности - плохо. Спасибо за ответ. Учту.

 
fxsaber:

Коллизия при любом уровне эффективности - плохо. Спасибо за ответ. Учту.

Хешмапов без коллизий по определению не бывает.

 
fxsaber #:

Вопрос по коллизиям. Возможно ли нарваться на коллизию в таком случае?

Если было произведено 27 000 записей.

Постоянно будете нарыватся, особенно при росте (ресайзе) коллекции. Так как хешь дополнительно обрезается до номера банда, а их всегда ограниченное количество (в идеале равное capacity).

От сюда выводы:

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

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

3. Колизии - это штатный механизм compaction. Через коллизии реализуется возможность хранения трех записей с id допустим 159, 4'569'209, 29'459'876 в массиве длины три, а не длины 30 000 000, пусть даже последние два значения оба попадут в банд с индексом 2.

 
Vasiliy Sokolov #:

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

Пожалуйста, покажите на примере.

Использую пока только это.

//+------------------------------------------------------------------+
//| Adds the specified key and value to the map.                     |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::Add(TKey key,TValue value);
//+------------------------------------------------------------------+
//| Gets the value associated with the specified key.                |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
bool CHashMap::TryGetValue(TKey key,TValue &value);
 
fxsaber #:

Пожалуйста, покажите на примере.

Использую пока только это.

Когда создаете коллекцию CHashMap используйте один из конструкторов, принимающий параметр capacity. Что происходит с производительностью при ресайзе смотрите мою статью про CDicionary. Там полный разбор этого алгоритма.

 

Обнаружил очень необычное поведение CHashMap.

// Демонстрация невозможности доступа по ключу после первого добавления.

#include <Generic\HashMap.mqh>

void OnStart()
{
  // Отсортированный массив неповторяющихся цен.
  const double Array[] =
{1.70682, 1.70691, 1.70700, 1.70709, 1.70710, 1.70717, 1.70721, 1.70742, 1.70749, 1.70752, 1.70757, 1.70766, 1.70768, 1.70769, 1.70771, 1.70773, 1.70774, 1.70777,
 1.70782, 1.70785, 1.70786, 1.70797, 1.70804, 1.70808, 1.70813, 1.70850, 1.70868, 1.70879, 1.70881, 1.70883, 1.70895, 1.70905, 1.70918, 1.70921, 1.70936, 1.70962,
 1.70966, 1.71022, 1.71027, 1.71047, 1.71056, 1.71080, 1.71081, 1.71093, 1.71096, 1.71109, 1.71112, 1.71119, 1.71120, 1.71127, 1.71128, 1.71135, 1.71136, 1.71138,
 1.71145, 1.71147, 1.71148, 1.71150, 1.71155, 1.71159, 1.71162, 1.71164, 1.71168, 1.71172, 1.71203, 1.71204, 1.71210, 1.71269, 1.71289, 1.71293, 1.71299, 1.71334,
 1.71337, 1.71343, 1.71357, 1.71358, 1.71367, 1.71371, 1.71374, 1.71380, 1.71402, 1.71410, 1.71414, 1.71425, 1.71426, 1.71427, 1.71429, 1.71430, 1.71446, 1.71474,
 1.71477, 1.71518, 1.71521, 1.71558, 1.71587, 1.71588, 1.71617, 1.71620, 1.71624, 1.71626, 1.71629, 1.71635, 1.71644, 1.71654, 1.71655, 1.71658, 1.71661, 1.71664,
 1.71689, 1.71700, 1.71712, 1.71718, 1.71727, 1.71752, 1.71769, 1.71775, 1.71780, 1.71782, 1.71786, 1.71792, 1.71795, 1.71797, 1.71798, 1.71801, 1.71815, 1.71827,
 1.71832, 1.71835, 1.71841, 1.71869, 1.71895, 1.71908, 1.71951, 1.71984, 1.71992, 1.72008, 1.72086, 1.72132, 1.72147, 1.72204, 1.72208, 1.72212, 1.72215, 1.72227,
 1.72230, 1.72233, 1.72234, 1.72336, 1.72374, 1.72378, 1.72381, 1.72405, 1.72454, 1.72464, 1.72477, 1.72488, 1.72541, 1.72553, 1.72562, 1.72588, 1.72625, 1.72651,
 1.72653, 1.72671, 1.72679, 1.72685, 1.72720, 1.72783, 1.72849, 1.72852, 1.72854, 1.72925, 1.72927, 1.72938, 1.72953, 1.72956, 1.72960, 1.72970, 1.72975, 1.72979,
 1.72996, 1.73014, 1.73028, 1.73034, 1.73050, 1.73056, 1.73084, 1.73085, 1.73119, 1.73137, 1.73176, 1.73278, 1.73328, 1.73337, 1.73344, 1.73345, 1.73362, 1.73377,
 1.73385, 1.73399, 1.73401, 1.73405, 1.73425, 1.73432, 1.73445, 1.73446, 1.73447, 1.73451, 1.73458, 1.73468, 1.73491, 1.73512, 1.73515, 1.73516, 1.73537, 1.73545,
 1.73553, 1.73580, 1.73581, 1.73598, 1.73611, 1.73630, 1.73635, 1.73643, 1.73658, 1.73678, 1.73694, 1.73695, 1.73698, 1.73712, 1.73713, 1.73721, 1.73746, 1.73748,
 1.73750, 1.73751, 1.73781, 1.73782, 1.73789, 1.73821, 1.73843, 1.73845, 1.73854, 1.73857, 1.73858, 1.73861, 1.73874, 1.73892, 1.74003, 1.74060, 1.74062};

  CHashMap<double, int> Index; // Будем по double-ключу хранить int-значения.
  
  for (int i = ArraySize(Array) - 1; i >= 0; i--)
    Index.Add(NormalizeDouble(Array[i], 5), 0); // Каждую цену массива используем в качестве ключа.
    
  // Все это было подготовкой, чтобы продемонстрировать поведение ниже.
  
  const double Price = 1.75141; // Берем новую цену.
  
  if (Index.Add(Price, 0)) // Если получилось добавить ее в качестве ключа.
  {
    int Value = 0;

    Print(Index.TryGetValue(Price, Value)); // (false) Проверяем, получается ли посмотреть данные по этому ключу.
    
    if (Index.Add(Price, 0)) // Пробуем повторно добавить в качестве ключа
      Print(Index.TryGetValue(Price, Value)); // (true) Проверяем, получается ли посмотреть данные по этому ключу.
  }
}


false
true

Получается, что идет якобы добавление ключа, но прочесть по нему ничего нельзя. Однако, стоит ключ добавить повторно, как он становится читаемым!

Это БАГ?


Если в примере цену 1.75141 заменить на другую, то будет работать правильно.


ЗЫ Было адски тяжело без дебага выявить это поведение в огромном коде и создать столь лаконичный пример.

 
Vasiliy Sokolov #:

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

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

Но думаю, это совпадение.

 
fxsaber #:

Обнаружил очень необычное поведение CHashMap.


Получается, что идет якобы добавление ключа, но прочесть по нему ничего нельзя. Однако, стоит ключ добавить повторно, как он становится читаемым!

Это БАГ?


Если в примере цену 1.75141 заменить на другую, то будет работать правильно.


ЗЫ Было адски тяжело без дебага выявить это поведение в огромном коде и создать столь лаконичный пример.

Исправлено, будет в сегодняшнем релизе.
 
MetaQuotes #:
Исправлено, будет в сегодняшнем релизе.

Спасибо! Вижу правку.


 
fxsaber #:

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

Но думаю, это совпадение.

Да там глюк на глюке. Я бы настоятельно не рекомендовал использовать Generic.

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