.NET or VC++
-
i've just started a project and the question of efficiency arose, and i automatically thought c++ out of curiosity though i wrote two test programs one in c++ the other in vb.net using an array of 500,000 strings and 40,000 search words on my system Athlon XP 64 3000+ in vb.net i used the binarysearch function it took around .22 of a second on average to complete in c++ i used the below function since i don't know of any built in functionality it took around .3 of a second on average to complete i also tried using the same algorithm below in vb.net and i can't remember the time, but it was slower than the built in function basically i've found if you can't find the functionallity built into vb.net and have to write it yourself it will slower, i didn't want the hassle of writing things in assembly in c++ either just so i could get more efficiency than vb.net int binarySearchRecursive(string* a, string* value, int left, int right) { int mid; if(right < left) return -1; mid = (int)floor((float)(left + right) / 2); if (_stricmp(value->c_str(), a[mid].c_str())<0) return binarySearchRecursive(a, value, mid + 1, right); else if(_stricmp(value->c_str(), a[mid].c_str())>0) return binarySearchRecursive(a, value, left, mid - 1); else return mid; }
A couple of quick things you can do to speed up this algorithm. No you don't need to resort to assembly either. 1) Why are you converting your mid place holder to a float just to do division? mid=(left+right)/2 is all you need. No need for a conversion routine and a call to floor. 2) Recursion has a lot of overhead associated with it too. Convert it to an iterative loop and you should pick up more speed. In this case you would be trading complexity for speed. Only the developer can really decide which is more important in this case. That is the two simplest things you can do. Other thing you can use is pointers instead of array indexing. If you are looking for simple you can also try the binary_search template that is part of the STL. I don't know how it would compare to the VB benchmark but may be worth exploring.