Code snippets‎ > ‎C++‎ > ‎STL‎ > ‎

Unordered

Performance test

#include <iostream>
#include <cstring>
#include <assert.h>
#include <unordered_map>
#include <ctime>
 
struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return strcmp(s1, s2) == 0;
  }
};
 
 
int main()
{
  const size_t N_TESTS = 1000;
  const size_t N_NAMES = 1000000;
  const size_t LENGTH = 10;
 
  std::clock_t start, stop;
 
  {
    typedef std::unordered_map<const char*, size_t, std::hash<const char*>, eqstr> Hash_map;
 
    char **names = (char **)malloc(sizeof(char *) * N_NAMES);
 
    // Generate random names
    for (size_t n=0; n<N_NAMES; ++n) {
      names[n] = (char *)malloc(sizeof(char) * (LENGTH+1));
      for (size_t length=0; length<LENGTH; ++length) {
        names[n][length] = 'a'+(rand()%26);
      }
      names[n][LENGTH] = '\0';
    }
 
    // Enter names in a hash map
    Hash_map my_hash_map;
    for (size_t n=0; n<N_NAMES; ++n) {
      my_hash_map[names[n]] = n;
    }
 
    start = std::clock();
    int success = 0;
    for (size_t test=0; test<N_TESTS; ++test) {
      for (size_t n=0; n<N_NAMES; ++n) {
        if (my_hash_map[names[n]] == n)
          success ++;
      }
    }
    stop = std::clock();
    std::cout
      << "Elapsed time " 
      << (stop-start)/(double)CLOCKS_PER_SEC
      << "s" << std::endl;
  }
 
  {
    typedef std::unordered_map<int, int, std::hash<int>> Hash_map;
 
    int *names = (int *)malloc(sizeof(int *) * N_NAMES);
 
    // Generate random names
    for (size_t n=0; n<N_NAMES; ++n) {
      names[n] = rand();
    }
 
    // Enter names in a hash map
    Hash_map my_hash_map;
    for (size_t n=0; n<N_NAMES; ++n) {
      my_hash_map[n] = names[n];
    }
 
    start = std::clock();
    int success = 0;
    for (size_t test=0; test<N_TESTS; ++test) {
      for (size_t n=0; n<N_NAMES; ++n) {
        if (my_hash_map[n] == names[n])
          success ++;
      }
    }
    stop = std::clock();
    std::cout
      << "Elapsed time " 
      << (stop-start)/(double)CLOCKS_PER_SEC
      << "s" << std::endl;
  }
 
  {
    int *names = (int *)malloc(sizeof(int *) * N_NAMES);
 
    // Generate random names
    for (size_t n=0; n<N_NAMES; ++n) {
      names[n] = (int)n;
    }
 
    start = std::clock();
    int success = 0;
    for (size_t test=0; test<N_TESTS; ++test) {
      for (size_t n=0; n<N_NAMES; ++n) {
        if (names[n] == n)
          success ++;
      }
    }
    stop = std::clock();
    assert(success == N_NAMES*N_TESTS);
    std::cout
      << "Elapsed time " 
      << (stop-start)/(double)CLOCKS_PER_SEC
      << "s" << std::endl;
  }
}

Comments