Download MetaTrader 5

comparing strings 'mathematically' - is this 'future-save'?

To add comments, please log in or register
Publish your article. Millions of traders are looking for good ideas!
Carl Schreiber
6609
Carl Schreiber 2013.11.20 11:24 

Hi,

in order to perform a quick (binary) search within a string array to get the index I compare strings like that

Symbols[mi] > sym

It works as this amended script shows (try yourself):

//+------------------------------------------------------------------+
//|                                                AllMarketData.mq4 |
//|                                 Copyright © 2011, MGAlgorithmics |
//|                                          http://www.mgaforex.com |
//+------------------------------------------------------------------+
#property copyright "Copyright © 2011, MGAlgorithmics"
#property link      "http://www.mgaforex.com"


//+------------------------------------------------------------------+
//| script program start function                                    |
//+------------------------------------------------------------------+
#include <stderror.mqh>
#include <stdlib.mqh>

#define LONG     0
#define SHORT    1
#define TYPE     2

#define SWAP     0
#define CURRENCY 1
#define DIR      2

#define SIZE     0   //Lot information
#define MIN      1
#define LOTSTEP  2
#define MAXLOT   3

#define VALUE    1  //Tick info

#define STARTING   0  //Timing info
#define EXPIRATION 1

#define ALLOWED    0  //Trade
#define MODE       1  //profit calc mode

#define CALC       0  //Margin
#define INIT       1
#define HEDGED     2
#define REQUIRED   3 
    
string Symbols[1000];
string Descr[1000];
double SyDigits[1000];
double Spread[1000];
double swap[1000][3];
double Stop[1000];
double Lot[1000][4];
double Tick[1000][2];
double Timing[1000][2];
double Trade[1000][2];
double Margin[1000][4];
double Freeze[1000];

int p, n, TotalSymbols, MAX=0;

int getSymbolIndex(string sym){
        //int i = ArraySize( Symbols ); while( i>0 ) { i--; if ( Symbols[i] == sym ) return(i); }       return(-1);
        int mi,le=0,ri=ArraySize( Symbols )-1;
        int cnt=0;
        while ( le<=ri ) {
                cnt++;
                mi = le + (ri - le) / 2;
                if ( Symbols[mi] == sym ) return(mi);
                if ( Symbols[mi] > sym ) ri = mi-1;
                else le = mi+1;
        }
        return(-1);    
}


void start() 
{
        string cmt; 
  TotalSymbols=FindSymbols();
  
  bool chg = sortSymbolFile();
  Comment("chg: ",chg,"\nEURUSD: ",getSymbolIndex("EURUSD"),"\nXAUUSD: ",getSymbolIndex("XAUUSD"));
  
  //PrintResult ("All Market Data", TotalSymbols);
}

int FindSymbols() 
{
  int    handle, i, r, TotalRecords;
  string fname, Sy, descr;
  //----->
  fname = "symbols.raw";
  handle=FileOpenHistory(fname, FILE_BIN | FILE_READ);
  if(handle<1)
    {
     Print("HTML Report generator - Unable to open file"+fname+", the last error is: ", GetLastError());
     return(false);
    }  
  TotalRecords=FileSize(handle) / 1936;
  ArrayResize(Symbols, TotalRecords);
    
  for(i=0; i<TotalRecords; i++) 
  {
    Sy=FileReadString(handle, 12);
    descr=FileReadString(handle, 75);
    FileSeek(handle, 1849, SEEK_CUR); // goto the next record
     
    Symbols[r]=Sy;
         if (r>1) { Comment("Sym[r]: ",Symbols[r],":",Symbols[r-1],"   >",(Symbols[r]>Symbols[r-1]),"   ==",(Symbols[r]==Symbols[r-1]),"   >",(Symbols[r]<Symbols[r-1])); Sleep(50); }


    Descr[r]=descr;
    SyDigits[r]=MarketInfo(Sy,MODE_DIGITS);
    
    Spread[r]=MarketInfo(Sy,MODE_SPREAD);
    
    swap[r][LONG]=MarketInfo(Sy,MODE_SWAPLONG);
    swap[r][SHORT]=MarketInfo(Sy,MODE_SWAPSHORT); 
    swap[r][TYPE]=MarketInfo(Sy,MODE_SWAPTYPE);
  
    Stop[r]=MarketInfo(Sy,MODE_STOPLEVEL);
  
    Lot[r][SIZE]=MarketInfo(Sy,MODE_LOTSIZE);
    Lot[r][MIN]= MarketInfo(Sy,MODE_MINLOT);
    Lot[r][LOTSTEP]=MarketInfo(Sy,MODE_LOTSTEP);
    Lot[r][MAXLOT]=MarketInfo(Sy,MODE_MAXLOT);
  
    Tick[r][VALUE]= MarketInfo(Sy,MODE_TICKVALUE);
    Tick[r][SIZE]=MarketInfo(Sy,MODE_TICKSIZE);
  
    Timing[r][STARTING]=MarketInfo(Sy,MODE_STARTING);
    Timing[r][EXPIRATION]=MarketInfo(Sy,MODE_EXPIRATION);
  
    Trade[r][ALLOWED]=MarketInfo(Sy,MODE_TRADEALLOWED);
    Trade[r][MODE]=MarketInfo(Sy,MODE_PROFITCALCMODE); 
    if (Trade[r][MODE]>MAX) MAX=Trade[r][MODE];
    
    
    // the script won't print the following items ... if you need them, amend yourself the PrintResult function below :)
    
    /*Margin[r][CALC]=MarketInfo(sSymbol,MODE_MARGINCALCMODE);
    Margin[r][INIT]=MarketInfo(sSymbol,MODE_MARGININIT);
    Margin[r][HEDGED]=MarketInfo(sSymbol,MODE_MARGINHEDGED);
    Margin[r][REQUIRED]=MarketInfo(sSymbol,MODE_MARGINREQUIRED);
    Freeze[r]=MarketInfo(sSymbol,MODE_FREEZELEVEL);*/
         
    // a different index for the count can be useful if you want to filter some elements from the whole list
    r++;
  }
 
  FileClose(handle);
  return(TotalRecords);
}
  
//+------------------------------------------------------------------+

int PrintResult (string title, int symbols)
 {
   int i, h;
   string fname, col="#E0E0E0";
   string sl, s0, fs;
//----
   fname = title+".html";
   h = FileOpen(fname,FILE_WRITE);
   if(h<1)
    {
     Print("HTML Report generator - Unable to open file"+fname+", the last error is: ", GetLastError());
     return(false);
    }
   
   s0="<!DOCTYPE HTML PUBLIC \"-//W3C//DTD HTML 4.01//EN\" \"http://www.w3.org/TR/html4/strict.dtd\">";FileWrite(h,s0);
   s0="<html><head><title>"+AccountCompany()+" "+title+"</title>" ;FileWrite(h,s0);
   s0="<meta name=\"generator\" content=\"MGAlgorithmics, forex software.\">" ;FileWrite(h,s0);
   s0="<link rel=\"help\" href=\"http://www.mgaforex.com\">" ;FileWrite(h,s0);

   s0="<style type=\"text/css\" media=\"screen\">" ;FileWrite(h,s0);
   s0="<!--td { font: 8pt Calibri,Arial; }//--></style>" ;FileWrite(h,s0);

   s0="</head>" ;FileWrite(h,s0);
   
   s0="<body topmargin=1 marginheight=1 style=\"background-color:#EEEEEE;\">" ;FileWrite(h,s0);

   s0="<div align=center><div style=\"font: 12pt Arial\">" ;FileWrite(h,s0);   
   s0="<b>"+WindowExpertName()+".ex4 Generated Report</b>" ;FileWrite(h,s0);
   s0="</div>" ;FileWrite(h,s0);
   
   s0="<div align=center><div style=\"font: 8pt Arial\">" ;FileWrite(h,s0);
   s0="<b>@2011 <a href=\"http://www.mgaforex.com\">MGAforex.com</a></b>" ;FileWrite(h,s0);
   s0="</div>" ;FileWrite(h,s0);
   s0="<br>" ;FileWrite(h,s0);
   
   s0="<div style=\"width:1000px;\">" ;FileWrite(h,s0);
   
   s0="<span style=\"float:left; background-color:#FFFFFF; border:1px solid; border-color:#C0C0C0;\">" ;FileWrite(h,s0);
   s0="<table cellspacing=3 cellpadding=3 border=0>" ;FileWrite(h,s0);
   
   for (int j=0; j<=MAX; j++)
      {
      s0="<tr align=center bgcolor=\"#6699CC\"><font color=\"#FFFFFF\">" ;FileWrite(h,s0); //6666CC
      FileWrite(h,Header());  
      s0="</tr>";FileWrite(h,s0);
         for (i=0; i<symbols; i++)
         {
         if (Trade[i][MODE]!=j) continue;
         fs=StringConcatenate("<tr align=center bgcolor=\""+col+"\">",Line(i),"</tr>");
         FileWrite(h,fs);
         }
      }

   s0="</table>";FileWrite(h,s0);
   s0="</span>"; FileWrite(h,s0);
   s0="</span></div></body></html>"; FileWrite(h,s0);
   FileClose(h); 

   //----
   return(0);
}
  
string Header ()
{  
   string s0;
   s0=StringConcatenate(
   "<td>#</td>",        "<td>Symbol</td>",      "<td>Description</td>",    "<td>Digits</td>",      "<td>Spread</td>",
   "<td>Swap Long</td>","<td>Swap Short</td>",  "<td>Swap Type</td>",      "<td>Stop Level</td>",  "<td>Lot Size</td>",
   "<td>Lot Min</td>",  "<td>Lot Step</td>",    /*"<td>Lot Max</td>",*/    "<td>Tick Value</td>",  "<td>Tick Size</td>",
   /*"<td>Starting</td>",*/   /*"<td>Expiration</td>",*/
   "<td>Trade Allowed</td>",   "<td>Pr. Mode</td>"
   );
  //----
   return(s0);
}

string Line (int i)
{
  string fs1;
  
  fs1=StringConcatenate(
     "<td>"+DoubleToStr(i,0)+"</td>",
     "<td>"+Symbols[i]+"</td>",  
     "<td nowrap>"+Descr[i]+"</td>",
     "<td>"+DoubleToStr(SyDigits[i],0)+"</td>",
     "<td>"+DoubleToStr(Spread[i],0)+"</td>",      
     "<td bgcolor=\""+Highlight(swap[i][LONG])+"\">"+DoubleToStr(swap[i][LONG],4)+"</td>",
     "<td bgcolor=\""+Highlight(swap[i][SHORT])+"\">"+DoubleToStr(swap[i][SHORT],4)+"</td>",
     "<td>"+InfoToStr(swap[i][TYPE], MODE_SWAPTYPE)+"</td>",
     "<td>"+DoubleToStr(Stop[i],0)+"</td>",
     "<td>"+DoubleToStr(Lot[i][SIZE],0)+"</td>",
     "<td>"+DoubleToStr(Lot[i][MIN],3)+"</td>",
     "<td>"+DoubleToStr(Lot[i][LOTSTEP],3)+"</td>",
   //"<td>"+DoubleToStr(Lot[i][MAXLOT],3)+"</td>",
     "<td>"+DoubleToStr(Tick[i][VALUE],6)+"</td>",
     "<td>"+DoubleToStr(Tick[i][SIZE],6)+"</td>",
   //"<td>"+TimeToStr(Timing[i][STARTING])+"</td>",
   //"<td>"+TimeToStr(Timing[i][EXPIRATION])+"</td>",
     "<td>"+InfoToStr (Trade[i][ALLOWED], MODE_TRADEALLOWED)+"</td>",
     "<td>"+InfoToStr (Trade[i][MODE], MODE_TRADES)+"</td>"
     );
    
//----
   return(fs1);
  }

/*string SwitchColor (string actual)       //ruins of an older function, it might still be of some use...
  {
   string res;
   if (actual=="#C0C0C0") res = "#E0E0E0";
   if (actual=="#E0E0E0") res = "#C0C0C0";
//----
   return(res);
  }*/

string Highlight (double sw)
{
   string res;
   if (sw<0) res = "#E0E0E0";  
   if (sw>=0) res = "#C0C0C0";
//----
   return(res);
}
  
string InfoToStr (double info, int mode)
{
  switch (mode)
          {
            case MODE_TRADES:
               if (info==0) return ("Forex");
               if (info==1) return ("CFD");
               if (info==2) return ("Future");
               break;
            case MODE_TRADEALLOWED:
               if (info==1) return ("yes");
               if (info!=1) return ("no");
               break;
            case MODE_SWAPTYPE:
               if (info==0) return ("points");
               if (info==1) return ("dep ccy");
               if (info==2) return ("percent");
               break;
          }
//----
}  
  
  

bool sortSymbolFile(){

/* bubble sort  http://de.wikipedia.org/wiki/Bubblesort
bubbleSort3(Array A)
  n = A.size
  do{
    newn = 1
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
        newn = i+1
      } // ende if
    } // ende for
    n = newn
  } while (n > 1)
*/
  int i,newn,n = ArraySize( Symbols );
  string sTmp;
  bool ret = false;
  while ( n>1 ){
    newn = 1;
    for (i=0; i<n-1; i++){
      if (Symbols[i] > Symbols[i+1]){
                        sTmp = Symbols[i];  // zwei [i]
                        Symbols[i] = Symbols[i+1];
                        Symbols[i+1] = sTmp;
         newn = i+1;
                        ret = true; 
      } // ende if
    } // ende for
    n = newn;
  } 
        return(ret);
}
  
  
  
  
  


But this is a kind of using an undocumented feature - is it save to use it even in future version of mt4?

Maybe s.o. can tell me more.

Thanks in advance,

gooly

whroeder1
14527
whroeder1 2013.11.20 14:55  
gooly: But this is a kind of using an undocumented feature
  1. It's not mathematically ("10" > "9"), it ASCII ordering ("10" < "9") because 1 comes before 9 in the table. Safe until strings go multi byte or you want language depending ordering.
  2. Never use bubble sort. An insertion sort is twice as efficient (your link said that) and simpler to code than yours. https://www.mql5.com/en/forum/138127
Carl Schreiber
6609
Carl Schreiber 2013.11.20 15:42  
WHRoeder:
  1. It's not mathematically ("10" > "9"), it ASCII ordering ("10" < "9") because 1 comes before 9 in the table. Safe until strings go multi byte or you want language depending ordering.
  2. Never use bubble sort. An insertion sort is twice as efficient (your link said that) and simpler to code than yours. https://www.mql5.com/en/forum/138127

ok, Thanks,

the ASCII ordering ("10"<"9") doesn't matter in my case, it's usable for a binary search.

"twice as efficien" If you look here: http://en.wikipedia.org/wiki/Sorting_algorithm the timing should be the same for both, bubble sort and insertion sort (n..n²), both need 1 single temp var.
But in bubble sort I can easily check (=without an extra comparison) whether the array is already sorted (ret stays false, nothing more to do) or s.th. has changed place, whereafter I have to re-write all the other arrays.

Thanks, gooly

whroeder1
14527
whroeder1 2013.11.20 16:26  
gooly: "twice as efficien" If you look here:
No, you look here:
http://en.wikipedia.org/wiki/Bubble_sort
Bubble sort has worst-case and average complexity both О(n2),
http://en.wikipedia.org/wiki/Insertion_sort
worst case input is an array sorted in reverse order. ... (i.e., O(n2)). best case input is an array that is already sorted. ..., Θ(n). insertion sort will usually perform about half as many comparisons as selection sort.(bubble sort) .. insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort;
Half as many = twice as fast. Your bubble sort ALWAYS takes the same amount of time. It is the worst of ALL sorting methods. It should never be taught, never be mentioned.
Alain Verleyen
Moderator
30745
Alain Verleyen 2013.11.20 16:51  
WHRoeder:
No, you look here:
http://en.wikipedia.org/wiki/Bubble_sort
Bubble sort has worst-case and average complexity both О(n2),
http://en.wikipedia.org/wiki/Insertion_sort
worst case input is an array sorted in reverse order. ... (i.e., O(n2)). best case input is an array that is already sorted. ..., Θ(n). insertion sort will usually perform about half as many comparisons as selection sort.(bubble sort) .. insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort;
Half as many = twice as fast. Your bubble sort ALWAYS takes the same amount of time. It is the worst of ALL sorting methods. It should never be taught, never be mentioned.

As most of the time you are too extreme. If bubble sort do the job for gooly, why could he not use it ? I don't think he can get a performance issue by sorting the list of symbols.

It's good for educational purpose also.


whroeder1
14527
whroeder1 2013.11.20 19:51  

I didn't say he couldn't use it. I said he shouldn't use it and why (simpler to code and more efficient.)

Then what does he do, posts a "If you look here" and completely missed what it actually says, and said a complete falsehood "timing should be the same for both"

So I corrected him, so anyone reading this in the future will know the truth. You think that is extreme?

Alain Verleyen
Moderator
30745
Alain Verleyen 2013.11.20 20:30  
WHRoeder:

I didn't say he couldn't use it. I said he shouldn't use it and why (simpler to code and more efficient.)

Then what does he do, posts a "If you look here" and completely missed what it actually says, and said a complete falsehood "timing should be the same for both"

So I corrected him, so anyone reading this in the future will know the truth. You think that is extreme?

My comment is related to your conclusion only : "It should never be taught, never be mentioned.", which is extreme in my opinion. gooly's code do the job using bubble sort algorithm. If someone need better performance he have to use better algorithm. There is nothing wrong with bubble sorting. Future readers can now form an opinion.
Carl Schreiber
6609
Carl Schreiber 2013.11.20 22:20  

WRoeder,

for bubble and insertion sort the timing should be the same - no?

For both I read the same.

bubble sort:

Worst case performance O(n²)
Best case performance O(n)
Average case performance O(n²)
Worst case space complexity O(1) auxiliary


for insertion sort:

Worst case performance О(n2) comparisons, swaps
Best case performance O(n) comparisons, O(1) swaps
Average case performance О(n2) comparisons, swaps
Worst case space complexity О(n) total, O(1) auxiliary


To me this is the same. But more than that the sort-timing is not sooo important for my need.

I want to detect if the array has to be changed (sorted, swapped) because this means I have to re-write all the other arrays and this takes more time.

Bubble sort allows me to place one additional order which is performed only in case of a swap so if the array is already sorted this extra line is never touched.

bubbleSort3(Array A)
  isChanged = false; //my add
  n = ArraySize(A);
  while(n>1) {
    newn = 1;
    for (i=0; i<n-1; i++){
      if (A[i] > A[i+1]){
        A.swap(i, i+1);
        isChanged = true; // my add
        newn = i+1;
      } // ende if
    } // ende for
    n = newn;
  } 

In case of insertion sort where should I place what kind of 'change detector'?

INSERTIONSORT(A)
1 for i = 1 to Length(A)-1 do
2      tempVal = A[i]
3      j = i
4      while j > 1 and A[j-1] > tempVal do
5           A[j] = A[j - 1]
6           j = j − 1
7      A[j] = tempVal

How would you detect whether this array has been changed or not? I think the advantage of insertion sort disappears in this case.

gooly

whroeder1
14527
whroeder1 2013.11.20 22:42  

gooly: for bubble and insertion sort the timing should be the same - no?

How would you detect whether this array has been changed or not? I think the advantage of insertion sort disappears in this case.

  1. No!!!!!!!!! Worst and AVERAGE and BEST case of bubble is n^2 Your newn=i+1 only modifies the best case. For insertion ONLY the worst is n^2 and BEST is O(n).
  2. Stop assuming and measure it.
  3. Detecting whether the array has been changed is irrelevant. That can be done in either method.
    INSERTIONSORT(A)
    1 for i = 1 to Length(A)-1 do
    2      tempVal = A[i]
    3      j = i
    4      while j > 1 and A[j-1] > tempVal do
    5           A[j] = A[j - 1] ; MODIFIED=TRUE;
    6           j = j − 1
    7      A[j] = tempVal
Carl Schreiber
6609
Carl Schreiber 2013.11.21 09:59  

well - if so: "No!!!!!!!!! Worst and AVERAGE and BEST case of bubble is n^2 Your newn=i+1 only modifies the best case. For insertion ONLY the worst is n^2 and BEST is O(n)."

wiki is wrong, but convinced and change the code :)

Thanks,

gooly

To add comments, please log in or register