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
86 lines
3.1 KiB
C++
86 lines
3.1 KiB
C++
// Unit test for cataclysm-0003: surroundings_menu item/terfurn dedup
|
|
// Verifies that unordered_set dedup matches vector+std::find dedup
|
|
// for add_item_recursive and add_terfurn patterns.
|
|
|
|
#include <algorithm>
|
|
#include <cassert>
|
|
#include <chrono>
|
|
#include <cstdio>
|
|
#include <string>
|
|
#include <unordered_set>
|
|
#include <vector>
|
|
|
|
int main() {
|
|
// Simulate nearby items: radius 12 means ~(25)^2 = 625 tiles
|
|
// Each tile may have 0-5 items. With item stacking, many names repeat.
|
|
const int num_items = 2000;
|
|
const int unique_names = 300;
|
|
|
|
std::vector<std::string> item_names;
|
|
for( int i = 0; i < num_items; i++ ) {
|
|
item_names.push_back( "item_type_" + std::to_string( i % unique_names ) );
|
|
}
|
|
|
|
// BEFORE: vector + std::find for dedup
|
|
auto t0 = std::chrono::high_resolution_clock::now();
|
|
for( int run = 0; run < 500; run++ ) {
|
|
std::vector<std::string> item_order;
|
|
for( const auto &name : item_names ) {
|
|
if( std::find( item_order.begin(), item_order.end(), name ) == item_order.end() ) {
|
|
item_order.push_back( name );
|
|
}
|
|
}
|
|
}
|
|
auto t1 = std::chrono::high_resolution_clock::now();
|
|
double ms_before = std::chrono::duration<double, std::milli>( t1 - t0 ).count();
|
|
|
|
// Capture result for correctness check
|
|
std::vector<std::string> result_before;
|
|
for( const auto &name : item_names ) {
|
|
if( std::find( result_before.begin(), result_before.end(), name ) == result_before.end() ) {
|
|
result_before.push_back( name );
|
|
}
|
|
}
|
|
|
|
// AFTER: unordered_set + vector for dedup
|
|
auto t2 = std::chrono::high_resolution_clock::now();
|
|
for( int run = 0; run < 500; run++ ) {
|
|
std::vector<std::string> item_order;
|
|
std::unordered_set<std::string> item_order_set;
|
|
for( const auto &name : item_names ) {
|
|
if( item_order_set.find( name ) == item_order_set.end() ) {
|
|
item_order.push_back( name );
|
|
item_order_set.insert( name );
|
|
}
|
|
}
|
|
}
|
|
auto t3 = std::chrono::high_resolution_clock::now();
|
|
double ms_after = std::chrono::duration<double, std::milli>( t3 - t2 ).count();
|
|
|
|
// Capture result for correctness check
|
|
std::vector<std::string> result_after;
|
|
std::unordered_set<std::string> result_set;
|
|
for( const auto &name : item_names ) {
|
|
if( result_set.find( name ) == result_set.end() ) {
|
|
result_after.push_back( name );
|
|
result_set.insert( name );
|
|
}
|
|
}
|
|
|
|
printf( "BEFORE (vector+find): %.3f ms\n", ms_before );
|
|
printf( "AFTER (unordered_set): %.3f ms\n", ms_after );
|
|
|
|
// Verify correctness: same elements in same order
|
|
assert( result_before.size() == result_after.size() );
|
|
for( size_t i = 0; i < result_before.size(); i++ ) {
|
|
assert( result_before[i] == result_after[i] );
|
|
}
|
|
assert( result_before.size() == static_cast<size_t>( unique_names ) );
|
|
|
|
double ratio = ms_before / ms_after;
|
|
printf( "Speedup ratio: %.1fx\n", ratio );
|
|
assert( ratio > 2.0 ); // Must show clear improvement
|
|
|
|
printf( "PASS: cataclysm-0003 surroundings_menu dedup\n" );
|
|
return 0;
|
|
}
|