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

New comment
 

Here is the code along with the input field. (Maybe someone will be useful. You can refine).

//+------------------------------------------------------------------+
//|                                                   Dictionary.mq5 |
//|                                                      Peter Konow |
//|                                             https://www.mql5.com |
//+------------------------------------------------------------------+
#property copyright "Peter Konow"
#property link      ""
#property version   "1.00"
#property strict
//+------------------------------------------------------------------+
//| Expert initialization function                                   |
//+------------------------------------------------------------------+
#define  Max_possible_collisions    100
#define  Max_letters_in_word        100
#define  All_letters_in_alphabet    255 
//------------------------------------
string Dictionary[Max_possible_collisions][All_letters_in_alphabet][Max_letters_in_word];
//-------------------------------------------------------------------
int OnInit()
  {
//---
   Create_text_box();
//---
   return(INIT_SUCCEEDED);
  }
//+------------------------------------------------------------------+
//| Expert deinitialization function                                 |
//+------------------------------------------------------------------+
void OnDeinit(const int reason)
  {
   ObjectDelete(0,"Text_box");
  }
//+------------------------------------------------------------------+
//+------------------------------------------------------------------+
//| ChartEvent function                                              |
//+------------------------------------------------------------------+
void OnChartEvent(const int id,
                  const long &lparam,
                  const double &dparam,
                  const string &sparam)
  {
    if(id == CHARTEVENT_OBJECT_ENDEDIT)
      { 
       //-----------------------
       string Text;     
       //---------------------
       ObjectGetString(0,"Text_box",OBJPROP_TEXT,0,Text);
       //-------------------------------------
       Add(Text);
      } 
  }
//+------------------------------------------------------------------+

void Add(string word)
{
 uchar First_letter = (uchar)StringGetCharacter(word,0) - 97;
 //-----------------------
 int All_letters_in_word = StringLen(word);
 //-----------------------
 for(int a1 = 0; a1 < Max_possible_collisions; a1++)
   {
     string word_inside = Dictionary[a1][First_letter][All_letters_in_word];
     //-----------------------   
    if(word_inside == NULL)
      {
       Dictionary[a1][First_letter][All_letters_in_word] = word;
       Print("Your word has been added to our dictionary!");
       break;
      }
    if(word_inside == word)
      {
       Print("This word already exists in our dictionary");
       break;
      } 
   }   
 //------------------------   
}
//--------------------------------------------------------------------+


//--------------------------------------------------------------------
void Create_text_box()
{
  ObjectCreate(0,"Text_box",OBJ_EDIT,0,0,0);
  ObjectSetInteger(0,"Text_box",OBJPROP_XDISTANCE,500);
  ObjectSetInteger(0,"Text_box",OBJPROP_YDISTANCE,250);
  ObjectSetInteger(0,"Text_box",OBJPROP_XSIZE,400);
  ObjectSetInteger(0,"Text_box",OBJPROP_YSIZE,30);
  ObjectSetString(0,"Text_box",OBJPROP_TEXT,"Please enter your word here...");
  ObjectSetString(0,"Text_box",OBJPROP_FONT,"TimesNewRoman");
  ObjectSetInteger(0,"Text_box",OBJPROP_STATE,1);
  //----------------------------------------------
  ObjectSetInteger(0,"Text_box",OBJPROP_FONTSIZE,12);
  ObjectSetInteger(0,"Text_box",OBJPROP_BGCOLOR,clrWhite);
  ObjectSetInteger(0,"Text_box",OBJPROP_COLOR,clrBlack);
  ObjectSetInteger(0,"Text_box",OBJPROP_BORDER_COLOR,clrBlack);
  ObjectSetInteger(0,"Text_box",OBJPROP_ALIGN,ALIGN_CENTER);
  //----------------------------------------------
  ObjectSetInteger(0,"Text_box",OBJPROP_CORNER,CORNER_LEFT_UPPER);
  ObjectSetInteger(0,"Text_box",OBJPROP_ANCHOR,ANCHOR_LEFT_UPPER);  
  //---------------------------------------------- 
}
//-----------------------------------------------------------------------

Only for some reason, fully works on the four. On the five of the field does not arise. I searched for the reason and did not find it.

 
fxsaber:

I.e. for each task you need to find the golden mean between dictionary size (RAM) and computational complexity of the hash function (CPU).


Relatively, yes.
When the number of elements is small, the optimal size of the dictionary is the number of elements squared (as far as I remember from the course of 3 years ago, but it's always better to double-check).
When it is impossible to choose the optimal size because of the large number of elements, then take the size of the dictionary several times the number of expected elements and optimize collision handling, for example, through the internal hash tables for each of the collisions.

The hash tables are chosen to search as quickly as possible, but they also provide a uniform distribution of the obtained results over the wordlist size.
Uniformity of distribution is connected with the use of prime numbers in hashes.

 
Konow tag:
I had to increase the size of the array, because capital letters have a different code and "fall out" of the array.

The code of the character "A" differs from the code of the character "a" by exactly 32. Accordingly, all the others also have a difference of 32.

Maybe it was not necessary to increase the size of the array, but just replace the first character.
 
Alexey Viktorov:

The code of the character "A" differs from the code of the character "a" by exactly 32. Accordingly, all others also have a difference of 32.

Maybe it was not necessary to increase the size of the array, but just replace the first character.

I agree. The algorithm is incomplete in this regard.

The array size is too large. Yesterday I did not entirely understand the letter codes.

 
Tag Konow:

Here is the code along with the input field. (It may come in handy for someone. You can refine it).

Only for some reason it works perfectly on 4. The field doesn't appear on 5. I searched for the reason and haven't found it.

One more remark: In Vasiliy's example there is a mention of an array

Forum on trading, automated trading systems & strategy testing

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

Vasiliy Sokolov, 2017.12.07 14:30

As simple as possible about the associative array #1

A lot of algorithms that are presented in Generic are based on associative array or dictionary. It's also one of the two most commonly used algorithms. I think I would be close to the truth if I said that 90% of all programming tasks are covered with arrays and dictionaries. Before moving on to practice, let us describe the work of the dictionary as simple and clear as possible, deliberately simplifying some of the details.

We will work with a very simple example: a regular wordlist. Suppose we have just a few of those words and they all start with different letters of the alphabet:

string words[] = {"apple", "cat", "fog", "dog", "walk", "zero"};

The English alphabet contains 26 characters. Let's create an array of strings, of size 26 elements:

string dictionary[26];

Now, if we agree to store words in indexes corresponding to their first letter we will get a simple dictionary. We will do the indexing from scratch. The word 'apple' will be stored in our index 0, because the character 'a' is the first letter of the alphabet, 'cat' - in index 1, 'dog' - in index 3, fog - will occupy index 4, walk - index 24 and zero - the last index 25.

Note that indexes from 5 to 23 will not be used. This is an additional waste of memory, but we can instantly access, for example, the word "walk", because we know that if it exists, it is located at index 24.

Let's write our first empty dictionary:



And in your example. 

#define  Max_possible_collisions    100
#define  Max_letters_in_word        100
#define  All_letters_in_alphabet    255 
//------------------------------------
string Dictionary[Max_possible_collisions][All_letters_in_alphabet][Max_letters_in_word];

How much memory does a 3-dimensional array take? And if you also have to increase the dimensionality?

 
Alexey Viktorov:

One more note: In Vasiliy's example, there is a mention of an array


And in your example.

How much memory does a 3-dimensional array take? And if we have to increase the dimensionality?

The size of the array is too big because:

1. I decided that the maximum number of letters in a word can be 100. This is obviously too much. We can reduce it to 30.

2. The number of possible letters is also excessive. I decided to take the space for the maximum number of different characters. Can be reduced.

3. The number of "collisions", that is matches of words by the first letter and the number of letters in the word, is set to 100. That's too much too. You could go down to 50.


I don't see the point of increasing the dimensionality any more. You can just make another dictionary.

 
Tag Konow:

The size of the array is too big because:

1. I decided that the maximum number of letters in a word can be 100. Clearly overkill. You could reduce it to 30.

2. The number of possible letters is also excessive. I decided to take the space for the maximum number of different characters. Can be reduced.

3. The number of "collisions", that is matches of words by the first letter and the number of letters in the word is set to 100. That's too much too. You can go down to 50.


I don't see the point in increasing the dimensionality. You can just make another dictionary.

The question is not about the dictionary. Dictionary is just an example of how to build an algorithm. And the elements can be not 100 as in your example, but 1e10 and more... In this case, what will be the size of the array?

For example, collect in an array all available history of ticks. There may be more than one tick in one millisecond, so the array cannot be one-dimensional... How many ticks were there in one millisecond at most? Two or five??? What should be the dimensionality of the array in this case??? How much memory would be wasted?

 
Alexey Viktorov:

For example, collect in an array all available tick history.

After writing all this, I thought that there is no practical task to store ticks in the way discussed in the branch. They are sorted by time and stored in a simple array.

It's the same with the History Orders/Deals. If we judge by HistorySelect, they are stored in an array by time. And I think, there is nothing there (in the current implementation), that would allow to search for records by ticket or ID.

And all because in case of the named history it is not reasonable to make something like this. A simple array is quite enough for practice.

That is why I am interested in practical wording of the trading problems.


When you speed up HistorySelect, I'm sure you solved the problem through caching, not through dictionaries with hashes.

 
fxsaber:

After writing all this, I thought that there is no practical task to store ticks in the way discussed in the branch. They are sorted by time and stored in a simple array.

It is the same with History Orders/Deals. If we judge by HistorySelect, they are stored in an array by time. And I think, there is nothing there (in the current implementation), that would allow to search for records by ticket or ID.

And all because in case of the named history it is not reasonable to make something like this. A simple array is enough for practice.

That is why I am interested in practical wording of the trading problems.


When you speed up HistorySelect, I'm sure you solved it with caching, not with hash dictionaries.

No argument, but if someone wants to implement some task this way, then the flag in their hands...

Someone thinks that there's no point, someone can't master it... In both cases, there are simpler implementations. But who knows how trading will develop "tomorrow"... Probably, it is better to let it be and remain unclaimed than to be necessary in its absence.

 
Alexey Viktorov:

The question is not about the dictionary. The dictionary is just an example of algorithm construction. And the elements can be not 100 as in your example, but 1e10 and more... In this case, what will be the size of the array?

For example, collect all available tick history in an array. There may be more than one tick in one millisecond, so the array cannot be one-dimensional... How many ticks are there in one millisecond at most? Two or five??? What should be the dimensionality of the array in this case??? How much memory will be wasted?

I was solving the problem of constructing a convenient dictionary.

Ticks or other elements have their own specific properties, which can be successfully indexed for quick access to storage location.

The essence of the task of fast access to data, is to identify several classifiable properties of an element and index them.

An element is taken, convenient properties are found from which you can get indexes, and through indexes, you get access to the storage location.

If indexes are not enough (for example, for word we can index first letter and number of letters, but other properties don't provide a usable index), we do a direct search of elements inside the area around it.

The principle is universal, implementations may vary.

123456789101112131415...37
New comment