CODEWITHSUNDEEP
c++performancestringfull-text-search
Dom
Dom

Reputation: 29

C++ Search Performance

What I have is two text files. One contains a list of roughly 70,000 names (~1.5MB). The other contains text which will be obtained from miscellaneous sources. That is, this file's contents will change each time the program is executed (~0.5MB). Essentially, I want to be able to paste some text into a text file and see which names from my list are found. Kind of like the find function (CTR + F) but with 70,000 keywords.

In any case, what I have thus far is:

int main()
{
     ifstream namesfile("names.txt");   //names list
     ifstream miscfile("misc.txt");     //misc text
     vector<string> vecnames;           //vector to hold names
     vector<string> vecmisc;            //vector to hold misc text
     size_t found;

     string s;
     string t;

     while (getline(namesfile,s))       
         veccomp.push_back(s);  

     while (getline(miscfile,t))        
         vectenk.push_back(t);

     //outer loop iterates through names list
     for (vector<string>::size_type i = 0; i != vecnames.size(); ++i) {
         //inner loop iterates through the lines of the mist text file
         for (vector<string>::size_type j = 0;j != vecmisc.size(); ++j) {
             found=vecmisc[j].find(vecnames[i]);
             if (found!=string::npos) {
                 cout << vecnames[i] << endl;
                 break;
             }
         }
     }

     cout << "SEARCH COMPLETE";

     //to keep console application from exiting
     getchar();

     return 0;
 }

Now this works great as far as extracting the data I need, however, it is terribly slow and obviously inefficient since each name requires that I potentially search the entire file again which gives (75000 x # of lines in misc text file) iterations. If anyone could help, I would certainly appreciate it. Some sample code is most welcomed. Additionally, I'm using Dev C++ if that makes any difference. Thanks.

Upvotes: 1

Views: 1205

Answers (3)

Ian Thompson
Ian Thompson

Reputation: 654

While a map of any kind is the simplest solution, Scott Myers makes a good case for sorted vector and binary_search from algorithm (in Effective STL).

Using a sorted vector, your code would look something like

#include <algorithm>

...

int vecsize = vecnames.size();
sort(vecnames.begin(), vecnames.begin() + vecsize );
for (vector<string>::size_type j = 0;j != vecmisc.size(); ++j)
{
  bool found= binary_search(vecnames.begin(), vecnames.begin()+vecsize,vecmisc[j]);
  if (found) std::cout << vecmisc[j] << std::endl;
}

The advantages of using a sorted vector and binary_search are

1) There is no tree to traverse, the binary_search begins at (end-start)/2, and keeps dividing by 2. It will take at most log(n) to search the range.

2) There is no key,value pair. You get the simplicity of a vector without the overhead of a map.

3) The vector's elements are in a contiguous range (which is why you should use reserve before populating the vector, inserts are faster), and so searching through the vector's elements rarely crosses page boundaries (slightly faster).

4) It's cool.

Upvotes: 0

Jason
Jason

Reputation: 32520

Using a vector, the best-case search time you're going to get is O(log N) complexity using a binary search algorithm, and that's only going to work for a sorted list. If you include the time it will take to make sorted insertions into a list, the final amortized complexity for a sorted linear container (arrays, lists), as well as non-linear containers such as binary-search trees, O(N log N). So that basically means that if you add more elements to the list, the time it will take to both add those elements to the list, as well as find them later on, will increase at a rate a little faster than the linear growth rate of the list (i.e., if you double the size of the list, it will take a little over double the time to sort the list, and then any searches on the list will be pretty quick ... in order to double the search time, the list would have to grow by the square of the existing amount of elements).

A good hash-table implementation on the other-hand (such as std::unordered_map) along with a good hash-algorithm that avoids too many collisions, has an amortized complexity of O(1) ... that means overall there's a constant look-up time for any given element, no matter how many elements there are, making searches very fast. The main penalty over a linear list or binary-search tree for the hash-table is the actual memory footprint of the hash table. A good hash-table, in order to avoid too many collisions, will want to have a size equal to some large prime number that is at least greater than 2*N, where N is the total number of elements you plan on storing in the array. But the "wasted space" is the trade-off for efficient and extremely fast look-ups.

Upvotes: 1

nornagon
nornagon

Reputation: 15821

Use a std::hash_set. Insert all your keywords into the set, then traverse the large document and each time you come to a word, test whether the set includes that word.

Upvotes: 4

Related Questions