another question for those who knows: b600+ and hash-arrays - page 2

New comment
 

hmm, not generic objects, but what about this.

I am using this to read all symbols and and their specification:

To get the correct index of a specific symbol I (insertion-) sort the symbol-array (and if changed I re-write the other values to the various arrays) and now I can get by the index of a symbol to get all its specific values even those one I have meanwhile entered by a binary search on the string array:

int getStrIndex(string str, string arr[]){
        //if ( arr[0] == str ) return(0);
        int m,l=0,r=ArraySize(arr)-1; //int c=0;Print("Start Bin-Search for ",sym);
        while ( l<=r ) { // binary search
                m = l + 0.5*(r - l);  //c++;Print(c,"  compare[",m,"] ",Symbols[m]," => ",( Symbols[m] == sym ),"  m: ",m,"  l: ",l,"  r: ",r);
                if ( arr[m] == str ) return(m);
                if ( arr[m]  > str ) r = m-1;
                else l = m+1;
        } //Print("FAILED[",m,"] ",arr[m]," => ",( arr[m] == str ),"  m: ",m,"  l: ",l,"  r: ",r);
        return(-1);     // not found
}

Instead of iterating more than 100 symbols it needs only 7 checks :).

This version is (too) easy because of two reasons: no additional symbol will appear and no symbol will disappear.

So this does not need to handle collisions and missing elements - only all required arrays are a bit too big because not all the symbols are used.

Gooly

 
Ovo:

Well, blindly, I meant in a sequence they were stored. For example for 3 elements there are 3 string comparisons, while computing a hash and managing hash slots have constant overhead. So there is a number of key elements, at which the sequential comparison is beaten by the hash search speed.


Hmm no idea. You are welcome to test :)
 
gooly:

hmm, not generic objects, but what about this.

I am using this to read all symbols and and their specification:

To get the correct index of a specific symbol I (insertion-) sort the symbol-array (and if changed I re-write the other values to the various arrays) and now I can get by the index of a symbol to get all its specific values even those one I have meanwhile entered by a binary search on the string array:

Instead of iterating more than 100 symbols it needs only 7 checks :).

This version is (too) easy because of two reasons: no additional symbol will appear and no symbol will disappear.

So this does not need to handle collisions and missing elements - only all required arrays are a bit too big because not all the symbols are used.

Gooly


Hi yup a binary chop works well on searching sorted data, but inserts can be expensive. Unless you make a Binary tree

hash.mqh is a Hash Table implementation for inserting and deleting using strings as indexes.

Plenty of comparisons on the net. Maybe this one is best advice.

 

IF anyone's interested I've updated my HashTable implementation to use Prime Number sizing and also to auto resize when it is more than 75% full (like default Java class)

Offsite link here (always latest) Library should get updated soon.

 
ydrol:

IF anyone's interested I've updated my HashTable implementation to use Prime Number sizing and also to auto resize when it is more than 75% full (like default Java class)

Offsite link here (always latest) Library should get updated soon.


Thanks, I am interested for sure. So far I did not meet any large sets in my code, but the need will come.
12
New comment