Generic Class Library - bugs, description, questions, usage and suggestions - page 23

New comment
  
//+------------------------------------------------------------------+
//|                                              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);
  }


The function is declared globally. For this reason there is a conflict with their Compare by users.

'Compare' - function already defined and has body

To reduce naming conflicts, could the author make all global auxiliary Generic functions public-static-methods?

 

fxsaber:

To reduce naming conflicts, could the author make all global auxiliary Generic functions public-static-methods?

Forum on trading, automated trading systems and strategy testing

Compiler bug: 'operator=' - structure has objects and cannot be copied

fxsaber 2018.09.10 11:00 2018.09.10 10:00:13 RU
Alexey Navoykov:
This is for the time being. If you want to include someone's library, you will find out that the author writes as "primitive" as you do, using the same names of classes and functions.

I will nail them with macros.

What about macros?
 
A100:
What about macros?

I wasn't talking about myself.

 

I've read all the pages of the discussion but still don't understand how to use it ?

Can anyone give me some examples?

 
Vladimir Pastushak:

I've read all the pages of the discussion but still don't understand how to use it ?

Can anyone give me some examples?

Forget it. You can't use it as it is now. Use the standard CObject + CDictionary instead. For most tasks, it is enough.

 
Vasiliy Sokolov:


ClassDescription
CHashMapA key-value set. Allows you to efficiently insert, retrieve and search for items based on their key. The key must be unique. For example, CHashMap can instantly find an order with a specified number, where the number is used as a key.

Question about retrieving a value by key. In the library code, this method looks like this

//+------------------------------------------------------------------+
//| 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 navigation tools (ALT+G and CTRL+-) by source refuse to work in this library. Therefore it is very difficult to trace the logic. In particular, I haven't figured out the initial value in the highlighted loop yet. But there is an understanding that if there is a speed, this value should be much less than the number of keys.


Please clarify the idea, what is the speed achieved in this function? Overkill is clearly present. But apparently it's short for some reason.


SZ I went through my debugger step by step. All clear on example TKey = int: m_bucket[Array[i]] = i. Only collisions when Array[i] == Array[j] (i != j) are unclear.

 
fxsaber:

The question is about getting the value by the key. In the library code this method looks like this
Please clarify the idea, what makes this function fast? The overshoot is obviously present. But apparently it's short for some reason.

At one time I was reviewing and describing howCHashMap works
You need to search for entries, probably in this thread.

 

Forum on trading, automated trading systems and trading strategy testing

Generic classes library - bugs, description, questions, peculiarities of usage and suggestions

Sergey Dzyublik, 2017.12.11 13:41

Briefly about currentCHashMap implementation:

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;

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

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

  }

First, let's find out what isEntry<TKey,TValue>.
Essentially it is a Node as in CLinkedList which contains:

- placed in the container key and value
- hash_code - a cached hash value for key
- next - "pointer" to the nextEntry<TKey,TValue> with the purpose of collision resolving through single-connected list


m_entries[] - array of "cells" where added key and value, hash_code, next are placed. Size of the array corresponds to Capacity.
m_count - specifies index of the first unused cell in m_entries. Initial value is 0, growing to Capacity, next is rebuilding all arrays with increasing Capacity and size of all arrays.
m_buckets[] - index array on m_entries[]. The default value is -1. Array size corresponds to Capacity.


No collision, adding unique value toCHashMap container:

  1. Calculate hash by key, get hash_code
  2. Put key, value, hash_code in m_entries[] by index m_count. (next = -1 because the example has no collisions)
  3. Put in m_buckets[] by hash_code % (ArraySize(m_buckets)) the index value of just added element in m_entries[] (this is m_count).
  4. Increase m_count by +1

Without collisions, get value by key inCHashMap container:

  1. Compute hash from key, get hash_code
  2. From m_buckets[], by hash_code % (ArraySize(m_buckets)) get the value which is an index of the array m_entries[]
  3. Using the obtained index m_buckets[hash_code % (ArraySize(m_buckets))], obtain our value value from array m_entries[].

Collision resolving:

For different keys it can happen that hash_code_key_1 % (ArraySize(m_buckets)) is equal to hash_code_key_2 % (ArraySize(m_buckets)) This is called a collision.
All elements with collision added to m_entries[] are linked through the one-connected list with next (seeEntry<TKey,TValue> structure)
And m_buckets[] always points to the index of the first head element in this collision list.
We get not one big list with collisions, but many small lists.


Collision, get value by key inCHashMap container:

  1. On the key we calculate the hash, get hash_code
  2. Using the index hash_code % (ArraySize(m_buckets)), get the value from m_entries[] array
  3. We can see that the value of next is not equal to -1, which indicates that there is a collision
  4. Walk through the single-entry list consisting of elements of m_entries[] and compare the sought value and the saved key for equality


Removing a value from theCHashMap container:

- When deleting a cell in m_entries[], no deletion is done; the cell is marked as free and hash_code = -1.
- free cells form their own list of free cells (using the same next from Entry<TKey,TValue>),m_free_list
- free cells are first used to add new values to the container.
-m_free_count is used to control the current number of free cells


Rebuild the hash table (increase capacity process) :

- rebuild only when Capacity is 100% full.
- next Capacity size is taken from the list:

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[] and m_buckets[] arrays are incremented.
- m_buckets[] is cleared and completely refilled, based on data from m_entries[] (cached hash value for key - hash_code)


Described behaviour from2017.12.11
 Currently, may have added/changed some details/coefficients.

 
Sergey Dzyublik:

I have at one time disassembled and described howCHashMap works
You need to look for entries, probably in this thread.

I found it on

Forum on trading, automated trading systems and strategy testing

Generic classes library - errors, descriptions, questions, peculiarities of use and suggestions

Sergey Dzyublik, 2017.12.07 14:21


In this example the hash is the student's birthday.
We have a cupboard with 365 shelves containing the students' diaries.
We put each diary on the shelf corresponding to the student's birthday.

We need the diary of the pupil Petrov and we know when he was born.
Now by the date of birth in O(1) we can easily find Petrov's journal, as well as the journal of any other student.
The exception is when two students have the same birthday - this is called a collision.

Solving a collision is using the extra information to find out which of two or more journals we need.
Collision resolving through a list is simply going through all the entries in the collision one by one to find a match. Tear off each diary and see whose it is.
A subhash is to organize a hash table of the items involved in the collision, but by a different criterion. For example by the hour the student was born.


If you are interested in the topic - I advise a course from MailRu on youtube about algorithms and data structures.

Forum on trading, automated trading systems and trading strategy testing

Generic classes library - errors, description, questions, peculiarities of usage and suggestions

Sergey Dzyublik, 2017.12.08 14:40

The basics on this topic are for the lazy ones:
https://www.slideshare.net/mkurnosov/6-32402313

In reality it is much more complicated and is discussed in the relevant literature or in good "algorithms and data structures" courses.


Thanks, debug helped. There are small lists for collisions. Ran through the thread and was horrified. Turns out to have been on topic...

 
Sergey Dzyublik:
Described behaviour from2017.12.11

As of now, may have added/changed some details/coefficients.

Thank you very much! Helped a lot with your description.

1...161718192021222324252627282930...37
New comment