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

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

Отличный теоретический пример! На практике кто-нить когда-нить оперировал тысячами сделок ?

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

Дело не в том, 1000 сделок или только 10. Фишка в том, что мы пишем короткий код, который одинаково эффективно работает как с 10, так и с 1000000..... сделками. 
 

Кратко о текущей реализации 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;

     .................................

     .................................

  }

Сперва нужно разобраться что такое Entry<TKey,TValue>
По сути это Node как в CLinkedList, который содержит: 

- помещенный в контейнер key и value
- закешированое значение хеша для key - hash_code
- next - "указатель" на следующий Entry<TKey,TValue> c целью разруливания коллизий через односвязный список


m_entries[] - массив "ячеек", куда помещаются добавленные  key и value, hash_code, next. Размер массива соответствует Capacity.
m_count - указывает индекс первой не использованной ячейки в m_entries. Начальное значение 0, растет до Capacity, дальше идет перестройка всех массивов с увеличением Capacity и размера всех массивов.
m_buckets[] - массив индексов на m_entries[]. Значение по умолчанию -1. Размер массива соответствует Capacity.


Без коллизий, добавление уникального значения в контейнер CHashMap:

  1. По key вычисляем хеш, получаем hash_code
  2. Помещаем в m_entries[] по индексу m_count  значения key, value, hash_code. (next = -1 так как пример без коллизий)
  3. Помещаем в m_buckets[] по индексу hash_code % (ArraySize(m_buckets)) значение индекса только что добавленного элемента в m_entries[] (это m_count).
  4. Увеличиваем значение m_count на +1

Без коллизий, получение значения по ключу в контейнере CHashMap:

  1. По key вычисляем хеш, получаем hash_code
  2. Из m_buckets[]  по индексу hash_code % (ArraySize(m_buckets)) получаем значение, которое является индексом от массива m_entries[] 
  3. Из массива m_entries[] по полученному индексу  m_buckets[hash_code % (ArraySize(m_buckets))] получаем наше значение value.

Разрешение коллизий:

Для разных key может получиться так, что hash_code_key_1 % (ArraySize(m_buckets))  будет равным hash_code_key_2 % (ArraySize(m_buckets)). Это называется коллизией.
Все добавленные в m_entries[] элементы с коллизией связываются между собой односвязным списком через next (смотри структуру Entry<TKey,TValue>)
А m_buckets[]  всегда указывает на индекс первого элемента head (головы) в этом списке коллизий.
Получается не один большой список с коллизиями, а множество маленьких списков.


Коллизия, получение значения по ключу в контейнере CHashMap:

  1. По key вычисляем хеш, получаем hash_code
  2. Из m_buckets[]  по индексу hash_code % (ArraySize(m_buckets)) получаем значение, которое является индексом от массива m_entries[] 
  3. Видим, что значение next не равно -1, что свидетельствует о наличии коллизии
  4. Проходим по односвязному списку из элементов m_entries[] и сравниваем на равенство искомое значение с сохраненными key


Удаление значения из контейнера CHashMap:

- при удалении ячейка в m_entries[]  ни какого удаления не происходит, ячейка обозначается как свободная и hash_code = -1. 
- свободные ячейки формируют собственный список свободных ячеек (через тот же next из Entry<TKey,TValue>), за индекс головы списка отвечает - m_free_list
- свободные ячейки первыми используются при добавлении новых значений в контейнер.
- для контроля текущего количества свободных ячеек используется m_free_count


Перестройка хеш-таблицы (процесс увеличения Capacity) :

- перестройка происходит только при 100% заполнении Capacity.
- следующий размер Capacity берется из списка:

const static int  CPrimeGenerator::s_primes[]=
  {
   3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,
   1103,1327,1597,1931,2333,2801,3371,4049,4861,5839,7013,8419,10103,12143,14591,
   17519,21023,25229,30293,36353,43627,52361,62851,75431,90523,108631,130363,156437,
   187751,225307,270371,324449,389357,467237,560689,672827,807403,968897,1162687,1395263,
   1674319,2009191,2411033,2893249,3471899,4166287,4999559,5999471,7199369
  };

- увеличиваются размеры массивов m_entries[] и m_buckets[].
- m_buckets[] очищается и полностью перезаполняется на основе данных от m_entries[] (закешированое значение хеша для key - hash_code)



Форум по трейдингу, автоматическим торговым системам и тестированию торговых стратегий

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

Sergey Dzyublik, 2017.12.09 01:12

Ознакомился с реализацией CHashMap
Честно, понравилась.


Есть несколько предложений по возможному улучшению:

1) По скромному мнению реализация содержит не совсем корректный выбор capacity - как начальный размер 3, так и последующие при перестройке хеш-таблицы.
Да, все верно, что нужно выбирать простое число для равномерности распределения. 
Однако реализация CPrimeGenerator не отвечает ожиданиям и содержит пропуски простых чисел.
Цель такого "генератора" понятна - обеспечить коэффициент прироста порядка 1.2 с автоматическим получением простых чисел.
Однако, разве это не слишком маленький коэффициент? В C++ для vectors обычно коэффициент составляет 1.5-2.0 в зависимости от библиотеки (так как сильно влияет на среднюю сложность операции).
Выходом может быть константный коэффициент с последующим округлением числа до простого через бинарный поиск в списку простых чисел.
И начальный размер capacity в 3 - это уж слишком мало, мы же не в прошлом веке живем.

2) На данный момент перестройка хеш-таблицы (Resize) выполняется исключительно при 100% заполнении capacity (заполнении всех m_entries[])
В связи с чем возможно значительное количество коллизий для ключей с не очень равномерным распределением.
Как вариант рассмотреть возможность введение коэффициента заполнения, который уменьшит 100% на необходимый лимит для выполнения перестройки хеш-таблицы.


 
Alexey Oreshkin:

На практике кто-нить когда-нить оперировал тысячами сделок ?

Да, миллионы обращений к истории на одном проходе практикуют многие.

 
Vasiliy Sokolov:

На Forts каждый первый.

Всё ясно.

Отправить ордера  hft алгоритмом и поднять их потом для анализа это разные вещи. Для отправки эти хеши не нужны, для анализа тоже, так как анализируется потом совсем другое.

Вообщем без обид. Теория тоже нужна.

 
Alexey Oreshkin:

Всё ясно.

Отправить ордера  hft алгоритмом и поднять их потом для анализа это разные вещи. Для отправки эти хеши не нужны, для анализа тоже, так как анализируется потом совсем другое.

Вообщем без обид. Теория тоже нужна.


Посудомойкой не пользуюсь - есть губка.
Вообщем без обид. Посудомойки галимые, зачем они только нужны.

 
Alexey Oreshkin:

Всё ясно.

Отправить ордера  hft алгоритмом и поднять их потом для анализа это разные вещи. Для отправки эти хеши не нужны, для анализа тоже, так как анализируется потом совсем другое.

Вообщем без обид. Теория тоже нужна.

Какие обиды? Пишите свои костыли дальше.

 
Sergey Dzyublik:

Кратко о текущей реализации CHashMap

Спасибо, буду использовать при разборе исходников.

 
Vasiliy Sokolov:

Какие обиды? Пишите свои костыли дальше.

В том то и дело что предложенную здесь тему я не использую и стараюсь понять прав я или нет. Мне хватает обычных ассоциативных массивов, но всегда хочется быть лучше.
 
fxsaber:

Спасибо, буду использовать при разборе исходников.


Опустил проверку на существование key в контейнере при добавлении новой key-value пары, выполняется в первую очередь.
Но не суть важно.

 
Столкнулся с сообщением об ошибке, вызванным отсутствием этого
//+------------------------------------------------------------------+
//| Gets the element at the specified index.                         |
//+------------------------------------------------------------------+
template<typename T>
bool CArrayList::TryGetValue(const int index,T &value) const

Просьба исправить подобное во всей Generic.

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