C / C++ / MFC

Greg Utas wrote:

and then some

#include <iostream>
#include <map>
using namespace std;

constexpr int Indices = 4096;
constexpr int Size = 512;


extern  const int idx[Indices];
extern  const string tag [Size];



int linear_search(const string & s )
{ 
  for (int n = 0; n<Size; ++n)
    if ( s == tag[n]) return n;
  
  return -1;
}


constexpr int Iterations = 1000000;

int main()
{
  std::map<string, int> mtag;
  for (int n=0; n<Size; ++n)
  {
    mtag.insert(make_pair(tag[n], n));
  }

  int sum = 0;

  for (int n=0; n<Iterations; ++n)
  {
    int i = idx[n % Indices];
    const string & s  = tag[i];
    int k;
#ifdef LINEAR_SEARCH
    k = linear_search( s );
#else
    auto it = mtag.find(s);
    k = it->second;
#endif
    sum+=k;
  }

  cout << "sum " << sum << endl;
}

• tag is an array of 512 randomly generated strings (having length betwween 4 and 12)
• idx is an array of 4096 randomly generated indices (for quickly gatering a candidate)

g++ -D LINEAR_SEARCH -Wall lookup.cpp -o lookup_linear_search
g++  -Wall lookup.cpp -o lookup_map

time ./lookup_linear_search 
sum 252632422

real    0m1,821s
user    0m1,811s
sys     0m0,008s

time ./lookup_map
sum 252632422

real    0m0,297s
user    0m0,297s
sys     0m0,000s

Quote:

What compiler are you using?

g++ -D LINEAR_SEARCH -Wall lookup.cpp -o lookup_linear_search