russell@unturf.com
8ea8ad434f
cataclysm-0001: overmap_ui search dedup vector O(P*M), 79x cataclysm-0002: dependency_tree dedup vector O(N^2), 2x cataclysm-0003: surroundings_menu item/terfurn dedup O(N^2), 9x
80 lines
2.8 KiB
C++
80 lines
2.8 KiB
C++
// Unit test for cataclysm-0001: overmap_ui search dedup
|
|
// Verifies that unordered_set dedup matches vector+std::find dedup
|
|
// and measures O(1) vs O(N) lookup performance.
|
|
|
|
#include <algorithm>
|
|
#include <cassert>
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
// Simulate point_abs_om as a simple pair
|
|
struct point_abs_om {
|
|
int x, y;
|
|
bool operator==( const point_abs_om &o ) const { return x == o.x && y == o.y; }
|
|
};
|
|
|
|
struct point_abs_om_hash {
|
|
size_t operator()( const point_abs_om &p ) const {
|
|
return std::hash<int>()( p.x ) ^ ( std::hash<int>()( p.y ) << 16 );
|
|
}
|
|
};
|
|
|
|
int main() {
|
|
// Generate overmap coordinates as if scanning radius 900
|
|
// In practice, distinct overmaps = (2*900/180+1)^2 ~ 100
|
|
const int num_overmaps = 100;
|
|
const int num_lookups = 50000; // simulating many points mapping to same overmaps
|
|
|
|
std::vector<point_abs_om> points;
|
|
for( int i = 0; i < num_lookups; i++ ) {
|
|
points.push_back( { i % num_overmaps, i / num_overmaps } );
|
|
}
|
|
|
|
// BEFORE: vector + std::find
|
|
{
|
|
std::vector<point_abs_om> checked;
|
|
int found_count = 0;
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
for( const auto &p : points ) {
|
|
if( std::find( checked.begin(), checked.end(), p ) == checked.end() ) {
|
|
checked.push_back( p );
|
|
} else {
|
|
found_count++;
|
|
}
|
|
}
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
double ms_before = std::chrono::duration<double, std::milli>( t1 - t0 ).count();
|
|
printf( "BEFORE (vector+find): %.3f ms, %d unique, %d dupes\n",
|
|
ms_before, (int)checked.size(), found_count );
|
|
|
|
// AFTER: unordered_set
|
|
std::unordered_set<point_abs_om, point_abs_om_hash> checked_set;
|
|
int found_count2 = 0;
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
for( const auto &p : points ) {
|
|
if( checked_set.find( p ) == checked_set.end() ) {
|
|
checked_set.insert( p );
|
|
} else {
|
|
found_count2++;
|
|
}
|
|
}
|
|
auto t3 = std::chrono::high_resolution_clock::now();
|
|
double ms_after = std::chrono::duration<double, std::milli>( t3 - t2 ).count();
|
|
printf( "AFTER (unordered_set): %.3f ms, %zu unique, %d dupes\n",
|
|
ms_after, checked_set.size(), found_count2 );
|
|
|
|
// Verify correctness
|
|
assert( checked.size() == checked_set.size() );
|
|
assert( found_count == found_count2 );
|
|
|
|
double ratio = ms_before / ms_after;
|
|
printf( "Speedup ratio: %.1fx\n", ratio );
|
|
assert( ratio > 1.5 ); // Must be measurably faster
|
|
|
|
printf( "PASS: cataclysm-0001 overmap search dedup\n" );
|
|
}
|
|
|
|
return 0;
|
|
}
|