//+------------------------------------------------------------------+//| 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(constbool x,constbool y)
{
if(x>y)
return(1);
elseif(x<y)
return(-1);
elsereturn(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?
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.
A 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 keyint hash_code=m_comparer.HashCode(key)&0x7FFFFFFF;
//--- search pair with specified keyfor(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.
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.
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:
Calculate hash by key, get hash_code
Put key, value, hash_code in m_entries[] by index m_count. (next = -1 because the example has no collisions)
Put in m_buckets[] by hash_code % (ArraySize(m_buckets)) the index value of just added element in m_entries[] (this is m_count).
Increase m_count by +1
Without collisions, get value by key inCHashMap container:
Compute hash from key, get hash_code
From m_buckets[], by hash_code % (ArraySize(m_buckets)) get the value which is an index of the array m_entries[]
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:
On the key we calculate the hash, get hash_code
Using the index hash_code % (ArraySize(m_buckets)), get the value from m_entries[] array
We can see that the value of next is not equal to -1, which indicates that there is a collision
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:
- 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.
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.
Allow the use of cookies to log in to the MQL5.com website.
Please enable the necessary setting in your browser, otherwise you will not be able to log in.
You are signed in. Two-factor authentication has been disabled. Set it up again and scan a new QR code, or continue with two-factor authentication disabled.
The function is declared globally. For this reason there is a conflict with their Compare by users.
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
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.
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?
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.
Question about retrieving a value by key. In the library code, this method looks like this
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.
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:
First, let's find out what isEntry<TKey,TValue>.
Essentially it is a Node as in CLinkedList which contains:
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:
Without collisions, get value by key inCHashMap container:
Collision resolving:
Collision, get value by key inCHashMap container:
Removing a value from theCHashMap container:
Rebuild the hash table (increase capacity process) :
Described behaviour from2017.12.11
Currently, may have added/changed some details/coefficients.
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...
As of now, may have added/changed some details/coefficients.
Thank you very much! Helped a lot with your description.