Created
May 5, 2021 06:22
-
-
Save parthvshah/4fbb5f89d3898531f42420a7050f8fbe to your computer and use it in GitHub Desktop.
(C++ STL) Benchmarking Find for Vector and Unordered Set
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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