Попробуйте использовать стандартный CObject CDictionary для разруливания коллизий - Общее обсуждение

fxsaber 2018.11.02 08:14 #221

//+------------------------------------------------------------------+
//|                                              CompareFunction.mqh |
//|                   Copyright 2016-2017, MetaQuotes Software Corp. |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#include <Generic\Interfaces\IComparable.mqh>
//+------------------------------------------------------------------+
//| Compares two objects and returns a value indicating whether one  |
//| is less than, equal to, or greater than the other.               |
//+------------------------------------------------------------------+
int Compare(const bool x,const bool y)
  {
   if(x>y)
      return(1);
   else if(x<y)
      return(-1);
   else
      return(0);
  }

Функция объявлена на глобальном уровне. По этой причине идет конфликт со своими Compare у пользователей.

'Compare' - function already defined and has body

Чтобы уменьшить количество конфликтов с именами, мог бы Автор все глобальные вспомогательные Generic-функции сделать public-static-методами?

A100 2018.11.02 14:21 #222

fxsaber:

Чтобы уменьшить количество конфликтов с именами, мог бы Автор все глобальные вспомогательные Generic-функции сделать public-static-методами?

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

Баг компилятора: 'operator=' - structure have objects and cannot be copied

fxsaber 2018.09.10 11:00 2018.09.10 10:00:13 #7 RU

Alexey Navoykov:
Это до поры до времени. Когда всё свалено в одну кучу, то крах неизбежен ) Захотите подключить чью-то библиотеку, а тут окажется что автор пишет так же "примитивно" как и вы, используя такие же имена классов и функций.

Макросами прибью.Макросами прибью.

А как же макросы?

Бета-версия платформы MetaTrader 5 Ошибки, баги, вопросы Обмен данными между программами

fxsaber 2018.11.02 14:22 #223

A100:

А как же макросы?

Вел речь не о себе.

Vladimir Pastushak 2018.11.02 21:01 #224

Прочитал все страницы дискуссии но так и не понял как использовать ?

Может кто нибудь привести примеры ?

Vasiliy Sokolov 2018.11.06 10:26 #225

Vladimir Pastushak:

Прочитал все страницы дискуссии но так и не понял как использовать ?

Может кто нибудь привести примеры ?

Забейте. В том виде в котором сейчас это есть использовать нельзя. Вместо этого пользуйтесь стандартным CObject + CDictionary. Для большинства задач этого хватает.

fxsaber 2018.11.22 05:39 #226

Vasiliy Sokolov:

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

Класс

Описание

CHashMap

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

Вопрос о получении значения по ключу. В коде библиотеки этот метод выглядит так

//+------------------------------------------------------------------+
//| Find index of entry with specified key.                          |
//+------------------------------------------------------------------+
template<typename TKey,typename TValue>
int CHashMap::FindEntry(TKey key)
  {
   if(m_capacity!=NULL)
     {
      //--- get hash code from key
      int hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
      //--- search pair with specified key
      for(int i=m_buckets[hash_code%m_capacity]; i>=0; i=m_entries[i].next)
         if(m_entries[i].hash_code==hash_code && m_comparer.Equals(m_entries[i].key,key))
            return(i);
     }
   return(-1);
  }

Средства навигации ME (ALT+G и CTRL+-) по исходнику отказываются работать в этой библиотеке. Поэтому очень сложно проследить логику. В частности, пока не выяснил начальное значение в выделенном цикле. Но есть понимание, что если имеется скорость, то это значение должно быть много меньше количества ключей.

Просьба пояснить идею, за счет чего достигается скорость в этой функции? Перебор явно присутствует. Но, видимо, он по какой-то причине короткий.

ЗЫ Прошелся пошагово дебагером. Все стало понятно на примере TKey = int: m_bucket[Array[i]] = i. Не разобрался только с коллизиями, когда Array[i] == Array[j] (i != j).

[АРХИВ]Любой вопрос новичка, чтоб Вопросы от начинающих MQL5 MT4 to MT5

Sergey Dzyublik 2018.11.22 06:48 #227

fxsaber:

Вопрос о получении значения по ключу. В коде библиотеки этот метод выглядит так
Просьба пояснить идею, за счет чего достигается скорость в этой функции? Перебор явно присутствует. Но, видимо, он по какой-то причине короткий.

В свое время разбирал и описывал принцип работы CHashMap
Нужно поискать записи, скорее всего в этой ветке.

Sergey Dzyublik 2018.11.22 06:57 #228

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

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

Sergey Dzyublik, 2017.12.11 13:41

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

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

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

По key вычисляем хеш, получаем hash_code
Из m_buckets[] по индексу hash_code % (ArraySize(m_buckets)) получаем значение, которое является индексом от массива m_entries[]
Из массива 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:

По key вычисляем хеш, получаем hash_code
Из m_buckets[] по индексу hash_code % (ArraySize(m_buckets)) получаем значение, которое является индексом от массива m_entries[]
Видим, что значение next не равно -1, что свидетельствует о наличии коллизии
Проходим по односвязному списку из элементов 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)

Описанное поведение от 2017.12.11
На текущий момент, могли добавить/изменить некоторые детали/коэффициенты.

Ошибки, баги, вопросы Новая версия платформы MetaTrader Библиотеки: MT4Orders

fxsaber 2018.11.22 07:18 #229

Sergey Dzyublik:

В свое время я разбирал и описывал принцип работы CHashMap
Нужно поискать записи, скорее всего в этой ветке.

Нашел

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

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

Sergey Dzyublik, 2017.12.07 14:21

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

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

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

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

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

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

Sergey Dzyublik, 2017.12.08 14:40

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

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

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

Непонятки с CHashMap из Мошенники в маркете Вопросы от начинающих MQL5

fxsaber 2018.11.22 07:34 #230

Sergey Dzyublik:

Описанное поведение от 2017.12.11

На текущий момент, могли добавить/изменить некоторые детали/коэффициенты.

Спасибо огромное! Сильно помогли доразобраться своим описанием.

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