90 lines
2.2 KiB
C++
90 lines
2.2 KiB
C++
#include <algorithm>
|
|
#include <chrono>
|
|
#include <iostream>
|
|
#include <random>
|
|
#include <string>
|
|
#include <unordered_map>
|
|
#include <vector>
|
|
|
|
using namespace std;
|
|
using namespace std::chrono;
|
|
|
|
int N = 1000000; // 1,000,000 tries
|
|
int L = 20; // string length
|
|
|
|
string random_string(size_t length) {
|
|
static const string chars =
|
|
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
|
|
|
|
static random_device rd;
|
|
static mt19937 gen(rd());
|
|
|
|
uniform_int_distribution<> dist(0, chars.size() - 1);
|
|
|
|
string s;
|
|
|
|
for (size_t i = 0; i < length; i++) {
|
|
s += chars[dist(gen)];
|
|
}
|
|
|
|
return s;
|
|
}
|
|
|
|
void test_array(int length) {
|
|
std::unordered_map<std::string, int> hash_map;
|
|
hash_map.reserve(length * 2); // Reserve more to avoid rehashing
|
|
std::vector<std::pair<std::string, int>> array;
|
|
array.reserve(length);
|
|
|
|
vector<string> keys;
|
|
|
|
for (int i = 0; i < length; ++i) {
|
|
string key = random_string(L);
|
|
|
|
keys.push_back(key);
|
|
|
|
hash_map[key] = i;
|
|
array.emplace_back(key, i);
|
|
}
|
|
|
|
auto start = std::chrono::high_resolution_clock::now();
|
|
for (int i = 0; i < N; ++i) {
|
|
string &key = keys[i % length];
|
|
|
|
auto it = hash_map.find(key);
|
|
|
|
volatile int value = it->second;
|
|
(void)value;
|
|
}
|
|
auto end = std::chrono::high_resolution_clock::now();
|
|
auto hash_duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
|
|
|
|
start = std::chrono::high_resolution_clock::now();
|
|
for (int i = 0; i < N; ++i) {
|
|
string &key = keys[i % length];
|
|
|
|
auto it = std::find_if(array.begin(), array.end(), [&key](const auto &pair) {
|
|
return pair.first == key;
|
|
});
|
|
|
|
volatile int value = it->second;
|
|
(void)value;
|
|
}
|
|
end = std::chrono::high_resolution_clock::now();
|
|
auto array_duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count();
|
|
|
|
std::cout << length << "," << hash_duration << "," << array_duration << "\n";
|
|
}
|
|
|
|
int main() {
|
|
std::cout << "elements,hash,array\n";
|
|
|
|
for (int length = 1; length <= 10; length++)
|
|
test_array(length);
|
|
for (int length = 10; length <= 100; length += 10)
|
|
test_array(length);
|
|
for (int length = 100; length <= 1000; length += 100)
|
|
test_array(length);
|
|
|
|
return 0;
|
|
} |