unordered_tire/example/order/find_example.cpp

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <chrono>
#include <random>
using namespace std;

#include "tire.h"

const int N = 1e5;
const int M = 5e4;
const int M1 = 3;
const int M2 = 5;

struct Test {
	int a;
	short b;
	int c;
};

vector<long long> umap_times;
vector<long long> tire_times;

vector<string> data_table;
void init_data_table() {
	for (int i = 0; i < N; ++i) {
		string str = to_string(i + 1);
		data_table.push_back(str);
	}
}

vector<string> target_table;
void init_target_table() {
	for (int i = 0; i < M; ++i) {
		char str[32] = "";
		int size = rand() % 30;
		for (int j = 0; j < size; ++j) {
			str[j] = (char)(rand() % 10) + '0';
		}
		str[size] = '\0';
		target_table.push_back(str);
	}
}

void umap_test(unordered_map<string, Test>& umap) {
	auto start = chrono::high_resolution_clock::now();
	for (auto& target : target_table) {
		umap.find(target);
	}
	auto end = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
	umap_times.push_back(duration.count());
}

void tire_test(Tire<Test>& tire) {
	auto start = chrono::high_resolution_clock::now();
	for (auto& target : target_table) {
		tire.find(target);
	}
	auto end = chrono::high_resolution_clock::now();
	auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
	tire_times.push_back(duration.count());
}

void analysis(string name, vector<long long>& nums) {
	const int n = nums.size();
	long long maxn = LLONG_MIN, minn = LLONG_MAX;
	long long sum = 0;
	for (long long& num : nums) {
		maxn = max(maxn, num);
		minn = min(minn, num);
		sum += num;
	}
	cout << name << ": " << "maxn: " << maxn << "ms    " << "minn: " << minn << "ms    " << "avg: " << (1.0 * sum / n) << "ms    " << "sum: " << sum << "ms    " << endl;
}

int main() {
	init_data_table();
	init_target_table();

	Tire<Test> tire;
	unordered_map<string, Test> umap;

	const int n = data_table.size();
	for (int i = 0; i < n; ++i) {
		Test t;
		t.a = i;
		t.c = n + i;
		tire.insert(data_table[i], t);
	}
	for (int i = 0; i < n; ++i) {
		Test t;
		t.a = i;
		t.c = n + i;
		umap.insert({ data_table[i], t });
	}

	// group 1
	for (int i = 0; i < M1; ++i) {
		umap_test(umap);
		tire_test(tire);
	}

	// group 2
	for (int i = 0; i < M1; ++i) {
		tire_test(tire);
		umap_test(umap);
	}

	// group 3
	for (int i = 0; i < M2; ++i) {
		umap_test(umap);
	}
	for (int i = 0; i < M2; ++i) {
		tire_test(tire);
	}

	// group 4
	for (int i = 0; i < M2; ++i) {
		tire_test(tire);
	}
	for (int i = 0; i < M2; ++i) {
		umap_test(umap);
	}

	// 分析
	analysis("umap", umap_times);
	analysis("tire", tire_times);
	return 0;
}