Great theoretical example! In practice, has anyone ever operated thousands of transactions?
p.s. I'm not trying to prove that it's crap and nobody needs it. I'm trying to understand the value for real trading. I'm not a theorist in general, but a pure practitioner.
It's not about 1,000 trades or just 10. The point is that we write short code that works equally effectively with both 10 and 1000000..... trades.
Briefly about the current implementation ofCHashMap:
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 we need to find out whatEntry<TKey,TValue> is. Basically it's a Node like in CLinkedList, which contains:
- placed in a key and value container - hash hashed value for key - hash_code - next - "pointer" to the nextEntry<TKey,TValue> in order to eliminate collisions through one-way list
m_entries[] - array of "cells" where added key and value, hash_code, next are placed. The size of the array corresponds to Capacity. m_count - specifies the 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.
Without collisions, adding a unique value in theCHashMap 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 the element just added in m_entries[] (this is m_count).
Increase m_count by +1
Without collisions, get value by key inCHashMap container:
Compute hash by key, get hash_code
Using the hash_code % (ArraySize(m_buckets)) from m_buckets[], get the value which is an index of the array m_entries[]
From array m_entries[] we obtain our value value from the obtained index m_buckets[hash_code % (ArraySize(m_buckets)).
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 in a single linked list via next (seeEntry<TKey,TValue> structure) And m_buckets[] always points to the index of the first head element in that collision list. You get not one big list with collisions, but many small lists.
Collision, getting value by key inCHashMap container:
Calculate hash by key, get hash_code
Using the hash_code % (ArraySize(m_buckets)) from m_buckets[], get the value, which is an index of the m_entries[] array
We see that the value of next is not equal to -1, which indicates the presence of a collision
Walk through the single-link list consisting of elements of m_entries[] and compare the sought value and the saved keys for equality
Deleting the value from theCHashMap container:
- when deleting a cell in m_entries[] no deletion occurs, the cell is marked as free and hash_code = -1. - free cells form their own list of free cells (through the same next of Entry<TKey,TValue>), for the head index of the list is responsible -m_free_list - free cells are first used when adding new values to the container. -m_free_count is used to control the current number of free cells
Rebuild hash table (process of increasing Capacity) :
- rebuild only when Capacity is 100% full. - next size of Capacity is taken from the list:
- m_entries[] and m_buckets[] arrays sizes are increased. - m_buckets[] is cleared and completely refilled based on data from m_entries[] (cached hash value for key - hash_code)
Got acquainted withCHashMap implementation Honestly, I liked it.
There are several suggestions for possible improvement:
1) In my humble opinion, the implementation contains not quite correct choice of capacity - both initial size 3 and subsequent ones when rebuilding the hash table. Yes, it is true that you need to choose a prime number for uniformity of distribution. However, the CPrimeGenerator implementation does not meet expectations and contains omissions of prime numbers. The purpose of such a "generator" is clear - to provide an increment factor of the order of 1.2 with automatic generation of prime numbers. However, isn't this too small a coefficient? In C++ for vectors, the coefficient is usually 1.5-2.0, depending on the library (because it strongly affects the average complexity of the operation). The way out could be a constant coefficient followed by rounding the number to prime via a binary search of a list of prime numbers. And an initial size of 3 is way too small, we don't live in the last century.
2) Hash table rebuilding (Resize) is currently performed only when 100% capacity is filled (all m_entries[] are filled). In this regard, there may be a significant number of collisions for keys with not very evenly distributed. As an option, consider introducing a fill factor that reduces 100% by the necessary limit to perform hash table rebuilding.
Sending orders by hft algorithm and raising them later for analysis are different things. These hashes are not needed for sending, and they are not needed for analysis, since we analyze something else entirely.
Sending orders by hft algorithm and raising them later for analysis are different things. These hashes are not needed for sending, and they are not needed for analysis either, since they are analyzed for something else entirely.
So, no offense. We also need theory.
I do not use dishwasher, I use sponge. No offense meant. Dishwashers are lame, what are they for.
Sending orders by hft algorithm and raising them later for analysis are different things. You don't need these hashes to submit them and you don't need them to analyze them, since you will analyze something else entirely.
The thing is, I don't use the subject offered here and I'm trying to understand whether I'm right or not. I'm satisfied with ordinary associative arrays, but I always want to be better.
//+------------------------------------------------------------------+//| Gets the element at the specified index. |//+------------------------------------------------------------------+template<typename T>
bool CArrayList::TryGetValue(constint index,T &value) const
Please fix something like this throughout Generic.
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.
Great theoretical example! In practice, has anyone ever operated thousands of transactions?
p.s. I'm not trying to prove that it's crap and nobody needs it. I'm trying to understand the value for real trading. I'm not a theorist in general, but a pure practitioner.
Briefly about the current implementation ofCHashMap:
First we need to find out whatEntry<TKey,TValue> is.
Basically it's a Node like in CLinkedList, which contains:
m_entries[] - array of "cells" where added key and value, hash_code, next are placed. The size of the array corresponds to Capacity.
m_count - specifies the 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.
Without collisions, adding a unique value in theCHashMap container:
Without collisions, get value by key inCHashMap container:
Collision resolving:
Collision, getting value by key inCHashMap container:
Deleting the value from theCHashMap container:
Rebuild hash table (process of increasing Capacity) :
Forum on trading, automated trading systems and strategy testing
Generic Class Library - bugs, description, questions, usage and suggestions
Sergey Dzyublik, 2017.12.09 01:12
Got acquainted withCHashMap implementation
Honestly, I liked it.
There are several suggestions for possible improvement:
1) In my humble opinion, the implementation contains not quite correct choice of capacity - both initial size 3 and subsequent ones when rebuilding the hash table.
Yes, it is true that you need to choose a prime number for uniformity of distribution.
However, the CPrimeGenerator implementation does not meet expectations and contains omissions of prime numbers.
The purpose of such a "generator" is clear - to provide an increment factor of the order of 1.2 with automatic generation of prime numbers.
However, isn't this too small a coefficient? In C++ for vectors, the coefficient is usually 1.5-2.0, depending on the library (because it strongly affects the average complexity of the operation).
The way out could be a constant coefficient followed by rounding the number to prime via a binary search of a list of prime numbers.
And an initial size of 3 is way too small, we don't live in the last century.
2) Hash table rebuilding (Resize) is currently performed only when 100% capacity is filled (all m_entries[] are filled).
In this regard, there may be a significant number of collisions for keys with not very evenly distributed.
As an option, consider introducing a fill factor that reduces 100% by the necessary limit to perform hash table rebuilding.
In practice, has anyone ever operated thousands of transactions?
Yes, millions of references to history on one pass is practiced by many.
On Forts every first.
It's clear.
Sending orders by hft algorithm and raising them later for analysis are different things. These hashes are not needed for sending, and they are not needed for analysis, since we analyze something else entirely.
So, no offense. You also need theory.
It's clear.
Sending orders by hft algorithm and raising them later for analysis are different things. These hashes are not needed for sending, and they are not needed for analysis either, since they are analyzed for something else entirely.
So, no offense. We also need theory.
I do not use dishwasher, I use sponge.
No offense meant. Dishwashers are lame, what are they for.
It's clear.
Sending orders by hft algorithm and raising them later for analysis are different things. You don't need these hashes to submit them and you don't need them to analyze them, since you will analyze something else entirely.
So, no offense. We also need theory.
What grudges? Keep writing your crutches.
Briefly about the current implementation ofCHashMap
Thank you, I will use when parsing the source code.
What grudges? Keep writing your crutches.
Thank you, I will use when parsing the sources.
Omitted checking for existence of key in container when adding new key-value pair, executed first.
But it is not important.
Please fix something like this throughout Generic.