Skip to content

Instantly share code, notes, and snippets.

@parthvshah
Created May 5, 2021 06:22
Show Gist options
  • Save parthvshah/4fbb5f89d3898531f42420a7050f8fbe to your computer and use it in GitHub Desktop.
Save parthvshah/4fbb5f89d3898531f42420a7050f8fbe to your computer and use it in GitHub Desktop.
(C++ STL) Benchmarking Find for Vector and Unordered Set
#include <vector>
#include <set>
#include <unordered_set>
#include <cassert>
#include <iostream>
#include <ctime>
#include <unistd.h>
#include <chrono>
#include <algorithm>
#include <vector>
#define LEN 23
using namespace std;
using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::duration;
using std::chrono::milliseconds;
int random_number(int min, int max)
{
static bool first = true;
if (first)
{
srand( time(NULL) );
first = false;
}
return min + rand() % (( max + 1 ) - min);
}
string random_string(const int len)
{
string tmp_s;
static const char alphanum[] =
"0123456789"
"ABCDEFGHIJKLMNOPQRSTUVWXYZ"
"abcdefghijklmnopqrstuvwxyz";
srand( (unsigned) time(NULL) * getpid());
tmp_s.reserve(len);
for (int i = 0; i < len; ++i)
tmp_s += alphanum[rand() % (sizeof(alphanum) - 1)];
return tmp_s;
}
void test_vec(long long int size)
{
// cout << "Testing vec..." << endl;
vector<string> vec;
int index = random_number(0, size-1);
string find;
for(int i = 0; i<size; ++i)
{
string temp = random_string(LEN);
vec.push_back(temp);
if(i==index)
find = temp;
}
auto t1 = high_resolution_clock::now();
if(std::find(vec.begin(), vec.end(), find) == vec.end())
cout << "Failed!" << endl;
auto t2 = high_resolution_clock::now();
duration<double, std::milli> ms_double = t2 - t1;
cout << ms_double.count() << endl;
}
void test_set(long long int size)
{
// cout << "Testing set..." << endl;
unordered_set<string> set;
int index = random_number(0, size-1);
string find;
for(int i = 0; i<size; ++i)
{
string temp = random_string(LEN);
set.insert(temp);
if(i==index)
find = temp;
}
auto t1 = high_resolution_clock::now();
if(set.find(find) == set.end())
cout << "Failed!" << endl;
auto t2 = high_resolution_clock::now();
duration<double, std::milli> ms_double = t2 - t1;
cout << ms_double.count() << endl;
}
int main()
{
for(long long int size = 100; size<=100000000; size*=10)
{
cout << size << endl;
test_vec(size);
test_set(size);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment