diff options
author | Gard Spreemann <gspr@nonempty.org> | 2022-04-29 13:54:09 +0200 |
---|---|---|
committer | Gard Spreemann <gspr@nonempty.org> | 2022-04-29 13:54:09 +0200 |
commit | fb4866e1d827389db17d74e5986d848617c8ef72 (patch) | |
tree | 46093502435ec117b137991a51acbe7f67b41dbc | |
parent | 66702d9cf122703964dbe22319ae8d97424d496f (diff) | |
parent | 8fbae1d789b3c9d7e9b079284c85489d8dcd7e65 (diff) |
Merge tag 'v1.0.0' into dfsg/latestdfsg/latest
Version 1.0.0
22 files changed, 126 insertions, 1103 deletions
diff --git a/matching/example/module_example.cpp b/matching/example/module_example.cpp index aec38c2..6fa2e5a 100644 --- a/matching/example/module_example.cpp +++ b/matching/example/module_example.cpp @@ -5,61 +5,83 @@ using namespace md; int main(int /*argc*/, char** /*argv*/) { - // create generators. - // A generator is a point in plane, - // generators are stored in a vector of points: - PointVec<double> gens_a; - - // module A will have one generator that appears at point (0, 0) - gens_a.emplace_back(0, 0); - - // relations are stored in a vector of relations using RelationVec = ModulePresentation<double>::RelVec; + using Relation = ModulePresentation<double>::Relation; + + // Module A (three rectangles) + PointVec<double> gens_a; RelationVec rels_a; - // A relation is a struct with position and column - using Relation = ModulePresentation<double>::Relation; - // at this point the relation rel_a_1 will appear: - Point<double> rel_a_1_position { 1, 1 }; + // First rectangle + gens_a.emplace_back(-3, -1); - // vector IndexVec contains non-zero indices of the corresponding relation - // (we work over Z/2). Since we have one generator only, the relation - // contains only one entry, 0 + Point<double> rel_a_1_position { -3, 3 }; IndexVec rel_a_1_components { 0 }; - - // construct a relation from position and column: Relation rel_a_1 { rel_a_1_position, rel_a_1_components }; - - // and add it to a vector of relations rels_a.push_back(rel_a_1); - // after populating vectors of generators and relations - // construct a module: - ModulePresentation<double> module_a { gens_a, rels_a }; + Point<double> rel_a_2_position { 1, -1 }; + IndexVec rel_a_2_components { 0 }; + Relation rel_a_2 { rel_a_2_position, rel_a_2_components }; + rels_a.push_back(rel_a_2); + // Second rectangle + gens_a.emplace_back(-1, -1); - // same for module_b. It will also have just one - // generator and one relation, but at different positions. + Point<double> rel_a_3_position { -1, 1 }; + IndexVec rel_a_3_components { 1 }; + Relation rel_a_3 { rel_a_3_position, rel_a_3_components }; + rels_a.push_back(rel_a_3); - PointVec<double> gens_b; - gens_b.emplace_back(1, 1); + Point<double> rel_a_4_position { 1, -1 }; + IndexVec rel_a_4_components { 1 }; + Relation rel_a_4 { rel_a_4_position, rel_a_4_components }; + rels_a.push_back(rel_a_4); + // Third rectangle + gens_a.emplace_back(-1, -3); + + Point<double> rel_a_5_position { -1, 1 }; + IndexVec rel_a_5_components { 2 }; + Relation rel_a_5 { rel_a_5_position, rel_a_5_components }; + rels_a.push_back(rel_a_5); + + Point<double> rel_a_6_position { 3, -3 }; + IndexVec rel_a_6_components { 2 }; + Relation rel_a_6 { rel_a_6_position, rel_a_6_components }; + rels_a.push_back(rel_a_6); + + + ModulePresentation<double> module_a { gens_a, rels_a }; + + + // Module B (one rectangle) + PointVec<double> gens_b; RelationVec rels_b; - Point<double> rel_b_1_position { 2, 2 }; + // Rectangle + gens_b.emplace_back(-2, -2); + + Point<double> rel_b_1_position { -2, 2 }; IndexVec rel_b_1_components { 0 }; + Relation rel_b_1 { rel_b_1_position, rel_b_1_components }; + rels_b.push_back(rel_b_1); + + Point<double> rel_b_2_position { 2, -2 }; + IndexVec rel_b_2_components { 0 }; + Relation rel_b_2 { rel_b_2_position, rel_b_2_components }; + rels_b.push_back(rel_b_2); - rels_b.emplace_back(rel_b_1_position, rel_b_1_components); ModulePresentation<double> module_b { gens_b, rels_b }; - // create CalculationParams + + // Computations CalculationParams<double> params; - // set relative error to 10 % : params.delta = 0.1; - // go at most 8 levels deep in quadtree: - params.max_depth = 8; + params.max_depth = 5; + params.initialization_depth = 0; double dist = matching_distance(module_a, module_b, params); std::cout << "dist = " << dist << std::endl; diff --git a/wasserstein/CMakeLists.txt b/wasserstein/CMakeLists.txt index dea4550..0a0fa4e 100644 --- a/wasserstein/CMakeLists.txt +++ b/wasserstein/CMakeLists.txt @@ -1,62 +1,25 @@ -project (wasserstein) -cmake_minimum_required (VERSION 3.5.1) +project(wasserstein) +cmake_minimum_required(VERSION 3.5.1) -set(CMAKE_EXPORT_COMPILE_COMMANDS ON) +set(CMAKE_CXX_STANDARD 14) +set(CMAKE_CXX_STANDARD_REQUIRED TRUE) -include (GenerateExportHeader) - -include(TestBigEndian) -test_big_endian(BIG_ENDIAN) -if(BIG_ENDIAN) - add_definitions(-DBIGENDIAN) -endif() - -# Default to Release - -if (NOT CMAKE_BUILD_TYPE) - set (CMAKE_BUILD_TYPE "Release" CACHE STRING "Choose the type of build, options are: Debug Release RelWithDebInfo MinSizeRel." FORCE) +if(NOT CMAKE_BUILD_TYPE) + set(CMAKE_BUILD_TYPE "Release" CACHE STRING "Choose the type of build, options are: Debug Release RelWithDebInfo MinSizeRel." FORCE) set_property(CACHE CMAKE_BUILD_TYPE PROPERTY STRINGS "Debug" "Release" "MinSizeRel" "RelWithDebInfo") -endif (NOT CMAKE_BUILD_TYPE) +endif(NOT CMAKE_BUILD_TYPE) # Boost -find_package (Boost) -include_directories (${CMAKE_CURRENT_SOURCE_DIR}/include - SYSTEM ${Boost_INCLUDE_DIR}) - -if(NOT WIN32) - add_definitions(-std=c++14) - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -Wall") - set(CMAKE_CXX_FLAGS_DEBUG "${CMAKE_CXX_FLAGS_DEBUG} -ggdb -D_GLIBCXX_DEBUG") - set(CMAKE_CXX_FLAGS_RELEASE "${CMAKE_CXX_FLAGS_RELEASE} -O3 ") - set(CMAKE_CXX_FLAGS_RELWITHDEBINFO "${CMAKE_CXX_FLAGS_RELEASE} -O2 -g -ggdb") -endif(NOT WIN32) +find_package(Boost) -file(GLOB WS_HEADERS ${CMAKE_CURRENT_SOURCE_DIR}/include/*.h ${CMAKE_CURRENT_SOURCE_DIR}/include/*.hpp) - -#add_library(wasserstein ${WS_SOURCES}) - -#if (WIN32) - #GENERATE_EXPORT_HEADER(wasserstein - #BASE_NAME wasserstein - #EXPORT_MACRO_NAME wasserstein_EXPORT - #EXPORT_FILE_NAME wasserstein_export.h - #STATIC_DEFINE wasserstein_BUILT_AS_STATIC) -#endif(WIN32) +include_directories(${CMAKE_CURRENT_SOURCE_DIR}/include SYSTEM ${Boost_INCLUDE_DIR}) find_package (Threads) set (libraries ${libraries} ${CMAKE_THREAD_LIBS_INIT}) -add_executable(wasserstein_dist ${CMAKE_CURRENT_SOURCE_DIR}/example/wasserstein_dist.cpp ${WS_HEADERS} include/hera_infinity.h) -target_link_libraries(wasserstein_dist PUBLIC ${libraries}) - -add_executable(wasserstein_dist_dipha ${CMAKE_CURRENT_SOURCE_DIR}/example/wasserstein_dist_dipha.cpp ${WS_HEADERS} include/hera_infinity.h) -target_link_libraries(wasserstein_dist_dipha PUBLIC ${libraries}) - -# pure geometric version, arbitrary dimension -add_executable(wasserstein_dist_point_cloud ${CMAKE_CURRENT_SOURCE_DIR}/example/wasserstein_dist_point_cloud.cpp ${WS_HEADERS} include/hera_infinity.h) -target_link_libraries(wasserstein_dist_point_cloud PUBLIC ${libraries}) +add_subdirectory(example) +#add_subdirectory(tests) # Tests add_executable(wasserstein_test ${CMAKE_CURRENT_SOURCE_DIR}/tests/tests_main.cpp ${CMAKE_CURRENT_SOURCE_DIR}/tests/test_hera_wasserstein.cpp ${CMAKE_CURRENT_SOURCE_DIR}/tests/test_hera_wasserstein_pure_geom.cpp include/hera_infinity.h tests/tests_reader.h) -#add_executable(wasserstein_test EXCLUDE_FROM_ALL ${CMAKE_CURRENT_SOURCE_DIR}/tests/test_hera_wasserstein.cpp) target_link_libraries(wasserstein_test PUBLIC ${libraries}) diff --git a/wasserstein/example/CMakeLists.txt b/wasserstein/example/CMakeLists.txt new file mode 100644 index 0000000..2e2f1f2 --- /dev/null +++ b/wasserstein/example/CMakeLists.txt @@ -0,0 +1,21 @@ +add_executable(wasserstein_dist wasserstein_dist.cpp) +target_link_libraries(wasserstein_dist PUBLIC ${libraries}) + +add_executable(wasserstein_dist_dipha wasserstein_dist_dipha.cpp) +target_link_libraries(wasserstein_dist_dipha PUBLIC ${libraries}) + +# pure geometric version, arbitrary dimension +add_executable(wasserstein_dist_point_cloud wasserstein_dist_point_cloud.cpp) +target_link_libraries(wasserstein_dist_point_cloud PUBLIC ${libraries}) + +if(MSVC) + target_compile_options(wasserstein_dist PRIVATE /W4 /WX) + target_compile_options(wasserstein_dist_dipha PRIVATE /W4 /WX) + target_compile_options(wasserstein_dist_point_cloud PRIVATE /W4 /WX) +else() + target_compile_options(wasserstein_dist PRIVATE -Wall -Wextra -Wpedantic) + target_compile_options(wasserstein_dist_dipha PRIVATE -Wall -Wextra -Wpedantic) + target_compile_options(wasserstein_dist_point_cloud PRIVATE -Wall -Wextra -Wpedantic) +endif() + + diff --git a/wasserstein/example/wasserstein_dist.cpp b/wasserstein/example/wasserstein_dist.cpp index cbe83e2..46f06fc 100644 --- a/wasserstein/example/wasserstein_dist.cpp +++ b/wasserstein/example/wasserstein_dist.cpp @@ -33,8 +33,6 @@ derivative works thereof, in binary and source code form. #include "opts/opts.h" -//#define LOG_AUCTION - //#include "auction_runner_fr.h" //#include "auction_runner_fr.hpp" @@ -138,14 +136,7 @@ int main(int argc, char* argv[]) params.max_bids_per_round = std::numeric_limits<decltype(params.max_bids_per_round)>::max(); - std::string log_filename_prefix = ( 11 <= argc ) ? argv[10] : ""; - - -#ifdef LOG_AUCTION - spdlog::set_level(spdlog::level::info); -#endif - - Real res = hera::wasserstein_dist(diagramA, diagramB, params, log_filename_prefix); + Real res = hera::wasserstein_dist(diagramA, diagramB, params); std::cout << std::setprecision(15) << res << std::endl; if (print_relative_error) diff --git a/wasserstein/example/wasserstein_dist_dipha.cpp b/wasserstein/example/wasserstein_dist_dipha.cpp index 2ed9c2c..1bfc41b 100644 --- a/wasserstein/example/wasserstein_dist_dipha.cpp +++ b/wasserstein/example/wasserstein_dist_dipha.cpp @@ -32,8 +32,6 @@ derivative works thereof, in binary and source code form. #include <iomanip> #include <vector> -//#define LOG_AUCTION - //#include "auction_runner_fr.h" //#include "auction_runner_fr.hpp" @@ -50,7 +48,7 @@ int main(int argc, char* argv[]) hera::AuctionParams<double> params; if (argc < 4 ) { - std::cerr << "Usage: " << argv[0] << " file1 file2 ph_dim [wasserstein_degree] [relative_error] [internal norm] [initial epsilon] [epsilon_factor] [max_bids_per_round] [gamma_threshold][log_filename_prefix]. By default power is 1.0, relative error is 0.01, internal norm is l_infinity, initall epsilon is chosen automatically, epsilon factor is 5.0, Jacobi variant is used (max bids per round is maximal), gamma_threshold = 0.0." << std::endl; + std::cerr << "Usage: " << argv[0] << " file1 file2 ph_dim [wasserstein_degree] [relative_error] [internal norm] [initial epsilon] [epsilon_factor] [max_bids_per_round] [gamma_threshold]. By default power is 1.0, relative error is 0.01, internal norm is l_infinity, initall epsilon is chosen automatically, epsilon factor is 5.0, Jacobi variant is used (max bids per round is maximal), gamma_threshold = 0.0." << std::endl; return 1; } @@ -116,15 +114,9 @@ int main(int argc, char* argv[]) params.gamma_threshold = (11 <= argc) ? atof(argv[10]) : 0.0; - std::string log_filename_prefix = ( 12 <= argc ) ? argv[11] : ""; - params.max_num_phases = 800; -#ifdef LOG_AUCTION - spdlog::set_level(spdlog::level::info); -#endif - - double res = hera::wasserstein_dist(diagramA, diagramB, params, log_filename_prefix); + double res = hera::wasserstein_dist(diagramA, diagramB, params); std::cout << std::setprecision(15) << res << std::endl; diff --git a/wasserstein/example/wasserstein_dist_point_cloud.cpp b/wasserstein/example/wasserstein_dist_point_cloud.cpp index ab7ff4f..754d0e3 100644 --- a/wasserstein/example/wasserstein_dist_point_cloud.cpp +++ b/wasserstein/example/wasserstein_dist_point_cloud.cpp @@ -86,7 +86,7 @@ int main(int argc, char* argv[]) hera::AuctionParams<Real> params; if (argc < 3 ) { - std::cerr << "Usage: " << argv[0] << " file1 file2 [wasserstein_degree] [relative_error] [internal norm] [initial epsilon] [epsilon_factor] [max_bids_per_round] [gamma_threshold][log_filename_prefix]. By default power is 1.0, relative error is 0.01, internal norm is l_infinity, initall epsilon is chosen automatically, epsilon factor is 5.0, Jacobi variant is used (max bids per round is maximal), gamma_threshold = 0.0." << std::endl; + std::cerr << "Usage: " << argv[0] << " file1 file2 [wasserstein_degree] [relative_error] [internal norm] [initial epsilon] [epsilon_factor] [max_bids_per_round] [gamma_threshold]. By default power is 1.0, relative error is 0.01, internal norm is l_infinity, initall epsilon is chosen automatically, epsilon factor is 5.0, Jacobi variant is used (max bids per round is maximal), gamma_threshold = 0.0." << std::endl; return 1; } @@ -159,14 +159,8 @@ int main(int argc, char* argv[]) params.gamma_threshold = (10 <= argc) ? atof(argv[9]) : 0.0; - std::string log_filename_prefix = ( 11 <= argc ) ? argv[10] : ""; - params.max_num_phases = 800; -#ifdef LOG_AUCTION - spdlog::set_level(spdlog::level::critical); -#endif - Real res = hera::ws::wasserstein_dist(set_A, set_B, params); std::cout << std::setprecision(15) << res << std::endl; diff --git a/wasserstein/include/auction_oracle_kdtree_restricted.hpp b/wasserstein/include/auction_oracle_kdtree_restricted.hpp index f0e7ac6..e86a5d5 100644 --- a/wasserstein/include/auction_oracle_kdtree_restricted.hpp +++ b/wasserstein/include/auction_oracle_kdtree_restricted.hpp @@ -270,7 +270,6 @@ IdxValPair<Real_> AuctionOracleKDTreeRestricted<Real_, PointContainer_>::get_opt // and vice versa. size_t best_item_idx { k_invalid_index }; - size_t second_best_item_idx { k_invalid_index }; size_t best_diagonal_item_idx { k_invalid_index }; Real best_item_value; Real second_best_item_value; @@ -297,17 +296,14 @@ IdxValPair<Real_> AuctionOracleKDTreeRestricted<Real_, PointContainer_>::get_opt best_item_idx = proj_item_idx; best_item_value = proj_item_value; second_best_item_value = best_diagonal_item_value_; - second_best_item_idx = best_diagonal_item_idx; } else if (proj_item_value < second_best_diagonal_item_value_) { best_item_idx = best_diagonal_item_idx; best_item_value = best_diagonal_item_value_; second_best_item_value = proj_item_value; - second_best_item_idx = proj_item_idx; } else { best_item_idx = best_diagonal_item_idx; best_item_value = best_diagonal_item_value_; second_best_item_value = second_best_diagonal_item_value_; - second_best_item_idx = second_best_diagonal_item_idx_; } } else { // for normal bidder get 2 best items among non-diagonal points from diff --git a/wasserstein/include/auction_runner_fr.h b/wasserstein/include/auction_runner_fr.h index 0c67b65..3ee659c 100644 --- a/wasserstein/include/auction_runner_fr.h +++ b/wasserstein/include/auction_runner_fr.h @@ -64,8 +64,7 @@ public: const Real _eps_factor = 5.0, const int _max_num_phases = std::numeric_limits<int>::max(), const Real _gamma_threshold = 0.0, - const size_t _max_bids_per_round = std::numeric_limits<size_t>::max(), - const std::string& _log_filename_prefix = ""); + const size_t _max_bids_per_round = std::numeric_limits<size_t>::max()); void set_epsilon(Real new_val); Real get_epsilon() const { return epsilon; } @@ -188,7 +187,6 @@ private: void print_debug(); void print_matching(); - std::string log_filename_prefix; const Real k_max_relative_error = 2.0; // if relative error cannot be estimated or is too large, use this value void reset_round_stat(); // empty, if logging is disable void reset_phase_stat(); @@ -196,69 +194,6 @@ private: std::unordered_set<size_t> never_assigned_bidders; std::unordered_set<size_t> never_assigned_items; -#ifdef LOG_AUCTION - std::unordered_set<size_t> unassigned_normal_bidders; - std::unordered_set<size_t> unassigned_diag_bidders; - - std::unordered_set<size_t> unassigned_normal_items; - std::unordered_set<size_t> unassigned_diag_items; - - - size_t all_assigned_round { 0 }; - size_t all_assigned_round_found { false }; - - int num_forward_rounds_non_cumulative { 0 }; - int num_forward_rounds { 0 }; - - int num_reverse_rounds_non_cumulative { 0 }; - int num_reverse_rounds { 0 }; - - // all per-round vars are non-cumulative - - // forward rounds - int num_normal_forward_bids_submitted { 0 }; - int num_diag_forward_bids_submitted { 0 }; - - int num_forward_diag_to_diag_assignments { 0 }; - int num_forward_diag_to_normal_assignments { 0 }; - int num_forward_normal_to_diag_assignments { 0 }; - int num_forward_normal_to_normal_assignments { 0 }; - - int num_forward_diag_from_diag_thefts { 0 }; - int num_forward_diag_from_normal_thefts { 0 }; - int num_forward_normal_from_diag_thefts { 0 }; - int num_forward_normal_from_normal_thefts { 0 }; - - // reverse rounds - int num_normal_reverse_bids_submitted { 0 }; - int num_diag_reverse_bids_submitted { 0 }; - - int num_reverse_diag_to_diag_assignments { 0 }; - int num_reverse_diag_to_normal_assignments { 0 }; - int num_reverse_normal_to_diag_assignments { 0 }; - int num_reverse_normal_to_normal_assignments { 0 }; - - int num_reverse_diag_from_diag_thefts { 0 }; - int num_reverse_diag_from_normal_thefts { 0 }; - int num_reverse_normal_from_diag_thefts { 0 }; - int num_reverse_normal_from_normal_thefts { 0 }; - - // price change statistics - std::vector<std::vector<size_t>> forward_price_change_cnt_vec; - std::vector<std::vector<size_t>> reverse_price_change_cnt_vec; - - size_t parallel_threshold = 5000; - int num_parallelizable_rounds { 0 }; - int num_parallelizable_forward_rounds { 0 }; - int num_parallelizable_reverse_rounds { 0 }; - - int num_parallel_bids { 0 }; - int num_total_bids { 0 }; - - int num_parallel_assignments { 0 }; - int num_total_assignments { 0 }; -#endif - }; diff --git a/wasserstein/include/auction_runner_fr.hpp b/wasserstein/include/auction_runner_fr.hpp index b0b65d0..ba36006 100644 --- a/wasserstein/include/auction_runner_fr.hpp +++ b/wasserstein/include/auction_runner_fr.hpp @@ -61,9 +61,7 @@ AuctionRunnerFR<R, AO>::AuctionRunnerFR(const std::vector<DgmPoint>& A, const Real _eps_factor, const int _max_num_phases, const Real _gamma_threshold, - const size_t _max_bids_per_round, - const std::string& _log_filename_prefix - ) : + const size_t _max_bids_per_round) : bidders(A), items(B), num_bidders(A.size()), @@ -96,8 +94,7 @@ AuctionRunnerFR<R, AO>::AuctionRunnerFR(const std::vector<DgmPoint>& A, partial_cost(0.0), unassigned_bidders_persistence(total_bidders_persistence), unassigned_items_persistence(total_items_persistence), - gamma_threshold(_gamma_threshold), - log_filename_prefix(_log_filename_prefix) + gamma_threshold(_gamma_threshold) { assert(A.size() == B.size()); for(const auto& p : bidders) { @@ -157,13 +154,6 @@ template<class R, class AO> void AuctionRunnerFR<R, AO>::reset_phase_stat() { num_rounds_non_cumulative = 0; -#ifdef LOG_AUCTION - num_parallelizable_rounds = 0; - num_parallelizable_forward_rounds = 0; - num_parallelizable_reverse_rounds = 0; - num_forward_rounds_non_cumulative = 0; - num_reverse_rounds_non_cumulative = 0; -#endif } @@ -172,34 +162,6 @@ void AuctionRunnerFR<R, AO>::reset_round_stat() { num_forward_bids_submitted = 0; num_reverse_bids_submitted = 0; -#ifdef LOG_AUCTION - num_normal_forward_bids_submitted = 0; - num_diag_forward_bids_submitted = 0; - - num_forward_diag_to_diag_assignments = 0; - num_forward_diag_to_normal_assignments = 0; - num_forward_normal_to_diag_assignments = 0; - num_forward_normal_to_normal_assignments = 0; - - num_forward_diag_from_diag_thefts = 0; - num_forward_diag_from_normal_thefts = 0; - num_forward_normal_from_diag_thefts = 0; - num_forward_normal_from_normal_thefts = 0; - - // reverse rounds - num_normal_reverse_bids_submitted = 0; - num_diag_reverse_bids_submitted = 0; - - num_reverse_diag_to_diag_assignments = 0; - num_reverse_diag_to_normal_assignments = 0; - num_reverse_normal_to_diag_assignments = 0; - num_reverse_normal_to_normal_assignments = 0; - - num_reverse_diag_from_diag_thefts = 0; - num_reverse_diag_from_normal_thefts = 0; - num_reverse_normal_from_diag_thefts = 0; - num_reverse_normal_from_normal_thefts = 0; -#endif } @@ -233,63 +195,6 @@ void AuctionRunnerFR<R, AO>::assign_forward(IdxType item_idx, IdxType bidder_idx // new edge was added to matching, increase partial cost partial_cost += get_item_bidder_cost(item_idx, bidder_idx); -#ifdef LOG_AUCTION - - if (unassigned_bidders.size() > parallel_threshold) { - num_parallel_assignments++; - } - num_total_assignments++; - - - int it_d = is_item_diagonal(item_idx); - int b_d = is_bidder_diagonal(bidder_idx); - // 2 - None - int old_d = ( k_invalid_index == old_item_owner ) ? 2 : is_bidder_diagonal(old_item_owner); - int key = 100 * old_d + 10 * b_d + it_d; - switch(key) { - case 211 : num_forward_diag_to_diag_assignments++; - break; - case 210 : num_forward_diag_to_normal_assignments++; - break; - case 201 : num_forward_normal_to_diag_assignments++; - break; - case 200 : num_forward_normal_to_normal_assignments++; - break; - - case 111 : num_forward_diag_to_diag_assignments++; - num_forward_diag_from_diag_thefts++; - break; - case 110 : num_forward_diag_to_normal_assignments++; - num_forward_diag_from_diag_thefts++; - break; - break; - case 101 : num_forward_normal_to_diag_assignments++; - num_forward_normal_from_diag_thefts++; - break; - break; - case 100 : num_forward_normal_to_normal_assignments++; - num_forward_normal_from_diag_thefts++; - break; - - case 11 : num_forward_diag_to_diag_assignments++; - num_forward_diag_from_normal_thefts++; - break; - case 10 : num_forward_diag_to_normal_assignments++; - num_forward_diag_from_normal_thefts++; - break; - break; - case 1 : num_forward_normal_to_diag_assignments++; - num_forward_normal_from_normal_thefts++; - break; - break; - case 0 : num_forward_normal_to_normal_assignments++; - num_forward_normal_from_normal_thefts++; - break; - default : std::cerr << "key = " << key << std::endl; - throw std::runtime_error("Bug in logging, wrong key"); - break; - } -#endif sanity_check(); } @@ -323,63 +228,6 @@ void AuctionRunnerFR<R, AO>::assign_reverse(IdxType item_idx, IdxType bidder_idx // new edge was added to matching, increase partial cost partial_cost += get_item_bidder_cost(item_idx, bidder_idx); - -#ifdef LOG_AUCTION - if (unassigned_items.size() > parallel_threshold) { - num_parallel_assignments++; - } - num_total_assignments++; - - int it_d = is_item_diagonal(item_idx); - int b_d = is_bidder_diagonal(bidder_idx); - // 2 - None - int old_d = (k_invalid_index == old_bidder_owner) ? 2 : is_item_diagonal(old_bidder_owner); - int key = 100 * old_d + 10 * it_d + b_d; - switch(key) { - case 211 : num_reverse_diag_to_diag_assignments++; - break; - case 210 : num_reverse_diag_to_normal_assignments++; - break; - case 201 : num_reverse_normal_to_diag_assignments++; - break; - case 200 : num_reverse_normal_to_normal_assignments++; - break; - - case 111 : num_reverse_diag_to_diag_assignments++; - num_reverse_diag_from_diag_thefts++; - break; - case 110 : num_reverse_diag_to_normal_assignments++; - num_reverse_diag_from_diag_thefts++; - break; - break; - case 101 : num_reverse_normal_to_diag_assignments++; - num_reverse_normal_from_diag_thefts++; - break; - break; - case 100 : num_reverse_normal_to_normal_assignments++; - num_reverse_normal_from_diag_thefts++; - break; - - case 11 : num_reverse_diag_to_diag_assignments++; - num_reverse_diag_from_normal_thefts++; - break; - case 10 : num_reverse_diag_to_normal_assignments++; - num_reverse_diag_from_normal_thefts++; - break; - break; - case 1 : num_reverse_normal_to_diag_assignments++; - num_reverse_normal_from_normal_thefts++; - break; - break; - case 0 : num_reverse_normal_to_normal_assignments++; - num_reverse_normal_from_normal_thefts++; - break; - default : std::cerr << "key = " << key << std::endl; - throw std::runtime_error("Bug in logging, wrong key"); - break; - } - -#endif } template<class R, class AO> @@ -409,10 +257,6 @@ void AuctionRunnerFR<R, AO>::assign_to_best_bidder(IdxType item_idx) auto new_bidder_price = -get_item_bidder_cost(item_idx, best_bidder_idx) - best_bid_value; reverse_oracle.set_price(best_bidder_idx, new_bidder_price, false); check_epsilon_css(); -#ifdef LOG_AUCTION - forward_price_change_cnt_vec.back()[item_idx]++; - reverse_price_change_cnt_vec.back()[best_bidder_idx]++; -#endif } template<class R, class AO> @@ -430,10 +274,6 @@ void AuctionRunnerFR<R, AO>::assign_to_best_item(IdxType bidder_idx) reverse_oracle.sanity_check(); auto new_item_price = -get_item_bidder_cost(best_item_idx, bidder_idx) - best_bid_value; forward_oracle.set_price(best_item_idx, new_item_price, false); -#ifdef LOG_AUCTION - forward_price_change_cnt_vec.back()[best_item_idx]++; - reverse_price_change_cnt_vec.back()[bidder_idx]++; -#endif check_epsilon_css(); } @@ -487,20 +327,6 @@ void AuctionRunnerFR<R, AO>::submit_forward_bid(IdxType bidder_idx, const IdxVal items_with_bids.insert(best_item_idx); -#ifdef LOG_AUCTION - - if (unassigned_bidders.size() > parallel_threshold) { - num_parallel_bids++; - } - num_total_bids++; - - - if (is_bidder_diagonal(bidder_idx)) { - num_diag_forward_bids_submitted++; - } else { - num_normal_forward_bids_submitted++; - } -#endif } template<class R, class AO> @@ -525,19 +351,6 @@ void AuctionRunnerFR<R, AO>::submit_reverse_bid(IdxType item_idx, const IdxValPa } bidders_with_bids.insert(best_bidder_idx); -#ifdef LOG_AUCTION - - if (unassigned_items.size() > parallel_threshold) { - num_parallel_bids++; - } - num_total_bids++; - - if (is_item_diagonal(item_idx)) { - num_diag_reverse_bids_submitted++; - } else { - num_normal_reverse_bids_submitted++; - } -#endif } @@ -628,35 +441,6 @@ void AuctionRunnerFR<R, AO>::flush_assignment() unassigned_items_by_persistence.insert(std::make_pair(items[item_idx].persistence_lp(1.0), item_idx)); } #endif - -#ifdef LOG_AUCTION - - reset_phase_stat(); - - forward_price_change_cnt_vec.push_back(std::vector<size_t>(num_items, 0)); - reverse_price_change_cnt_vec.push_back(std::vector<size_t>(num_bidders, 0)); - - // all bidders and items become unassigned - for(size_t bidder_idx = 0; bidder_idx < num_bidders; ++bidder_idx) { - if (is_bidder_normal(bidder_idx)) { - unassigned_normal_bidders.insert(bidder_idx); - } else { - unassigned_diag_bidders.insert(bidder_idx); - } - } - - never_assigned_bidders = unassigned_bidders; - - for(size_t item_idx = 0; item_idx < items.size(); ++item_idx) { - if (is_item_normal(item_idx)) { - unassigned_normal_items.insert(item_idx); - } else { - unassigned_diag_items.insert(item_idx); - } - } - - never_assigned_items = unassigned_items; -#endif check_epsilon_css(); } @@ -803,13 +587,6 @@ void AuctionRunnerFR<R, AO>::add_unassigned_bidder(const size_t bidder_idx) unassigned_bidders_by_persistence.insert(std::make_pair(bidder.persistence_lp(1.0), bidder_idx)); #endif -#ifdef LOG_AUCTION - if (is_bidder_diagonal(bidder_idx)) { - unassigned_diag_bidders.insert(bidder_idx); - } else { - unassigned_normal_bidders.insert(bidder_idx); - } -#endif } template<class R, class AO> @@ -823,13 +600,6 @@ void AuctionRunnerFR<R, AO>::add_unassigned_item(const size_t item_idx) unassigned_items_by_persistence.insert(std::make_pair(item.persistence_lp(1.0), item_idx)); #endif -#ifdef LOG_AUCTION - if (is_item_diagonal(item_idx)) { - unassigned_diag_items.insert(item_idx); - } else { - unassigned_normal_items.insert(item_idx); - } -#endif } @@ -845,17 +615,6 @@ void AuctionRunnerFR<R, AO>::remove_unassigned_bidder(const size_t bidder_idx) unassigned_bidders_by_persistence.erase(std::make_pair(bidders[bidder_idx].persistence_lp(1.0), bidder_idx)); #endif -#ifdef LOG_AUCTION - if (is_bidder_diagonal(bidder_idx)) { - unassigned_diag_bidders.erase(bidder_idx); - } else { - unassigned_normal_bidders.erase(bidder_idx); - } - if (never_assigned_bidders.empty() and not all_assigned_round_found) { - all_assigned_round = num_rounds_non_cumulative; - all_assigned_round_found = true; - } -#endif } template<class R, class AO> @@ -870,17 +629,6 @@ void AuctionRunnerFR<R, AO>::remove_unassigned_item(const size_t item_idx) unassigned_items_by_persistence.erase(std::make_pair(items[item_idx].persistence_lp(1.0), item_idx)); #endif -#ifdef LOG_AUCTION - if (is_item_normal(item_idx)) { - unassigned_normal_items.erase(item_idx); - } else { - unassigned_diag_items.erase(item_idx); - } - if (never_assigned_items.empty() and not all_assigned_round_found) { - all_assigned_round = num_rounds_non_cumulative; - all_assigned_round_found = true; - } -#endif } template<class R, class AO> @@ -906,14 +654,6 @@ void AuctionRunnerFR<R, AO>::run_reverse_auction_phase() num_rounds_non_cumulative++; check_epsilon_css(); -#ifdef LOG_AUCTION - if (unassigned_items.size() >= parallel_threshold) { - ++num_parallelizable_reverse_rounds; - ++num_parallelizable_rounds; - } - num_reverse_rounds++; - num_reverse_rounds_non_cumulative++; -#endif reset_round_stat(); // bidding @@ -986,14 +726,6 @@ void AuctionRunnerFR<R, AO>::run_forward_auction_phase() while (continue_forward(original_unassigned_bidders, min_forward_matching_increment)) { check_epsilon_css(); num_rounds++; -#ifdef LOG_AUCTION - if (unassigned_bidders.size() >= parallel_threshold) { - ++num_parallelizable_forward_rounds; - ++num_parallelizable_rounds; - } - num_forward_rounds++; - num_forward_rounds_non_cumulative++; -#endif reset_round_stat(); // bidding step @@ -1024,33 +756,6 @@ void AuctionRunnerFR<R, AO>::run_forward_auction_phase() check_epsilon_css(); -#ifdef LOG_AUCTION - forward_plot_logger->info("{0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14} {15} {16} {17} {18} {19} {20} {21} {22}", - num_phase, - num_rounds, - num_forward_rounds, - unassigned_bidders.size(), - get_gamma(), - partial_cost, - forward_oracle.get_epsilon(), - num_normal_forward_bids_submitted, - num_diag_forward_bids_submitted, - num_forward_diag_to_diag_assignments, - num_forward_diag_to_normal_assignments, - num_forward_normal_to_diag_assignments, - num_forward_normal_to_normal_assignments, - num_forward_diag_from_diag_thefts, - num_forward_diag_from_normal_thefts, - num_forward_normal_from_diag_thefts, - num_forward_normal_from_normal_thefts, - unassigned_normal_bidders.size(), - unassigned_diag_bidders.size(), - unassigned_normal_items.size(), - unassigned_diag_items.size(), - forward_oracle.get_heap_top_size(), - get_relative_error(false) - ); -#endif } ; } diff --git a/wasserstein/include/auction_runner_gs.h b/wasserstein/include/auction_runner_gs.h index 8ad95c2..3616a98 100644 --- a/wasserstein/include/auction_runner_gs.h +++ b/wasserstein/include/auction_runner_gs.h @@ -49,8 +49,7 @@ public: AuctionRunnerGS(const PointContainer& A, const PointContainer& B, - const AuctionParams<Real>& params, - const std::string& _log_filename_prefix = ""); + const AuctionParams<Real>& params); void set_epsilon(Real new_val) { assert(epsilon > 0.0); epsilon = new_val; }; Real get_epsilon() const { return oracle.get_epsilon(); } @@ -98,19 +97,6 @@ public: int num_phase { 0 }; int num_rounds { 0 }; bool is_distance_computed {false}; -#ifdef LOG_AUCTION - bool log_auction { false }; - std::shared_ptr<spdlog::logger> console_logger; - std::shared_ptr<spdlog::logger> plot_logger; - std::unordered_set<size_t> unassigned_items; - size_t max_unassigned_to_log { 0 }; - const char* logger_name = "auction_detailed_logger"; // the name in spdlog registry; filename is provided as parameter in enable_logging - const Real total_items_persistence; - const Real total_bidders_persistence; - Real partial_cost; - Real unassigned_bidders_persistence; - Real unassigned_items_persistence; -#endif }; } // ws diff --git a/wasserstein/include/auction_runner_gs.hpp b/wasserstein/include/auction_runner_gs.hpp index 4ef94db..dcc8960 100644 --- a/wasserstein/include/auction_runner_gs.hpp +++ b/wasserstein/include/auction_runner_gs.hpp @@ -54,8 +54,7 @@ namespace ws { template<class R, class AO, class PC> AuctionRunnerGS<R, AO, PC>::AuctionRunnerGS(const PC& A, const PC& B, - const AuctionParams<Real>& params, - const std::string& _log_filename_prefix) : + const AuctionParams<Real>& params) : bidders(A), items(B), num_bidders(A.size()), @@ -71,63 +70,14 @@ AuctionRunnerGS<R, AO, PC>::AuctionRunnerGS(const PC& A, tolerate_max_iter_exceeded(params.tolerate_max_iter_exceeded), dimension(params.dim), oracle(bidders, items, params) -#ifdef LOG_AUCTION - , total_items_persistence(std::accumulate(items.begin(), - items.end(), - R(0.0), - [params](const Real& ps, const DgmPoint& item) - { return ps + std::pow(item.persistence_lp(params.internal_p), params.wasserstein_power); } - )) - - , total_bidders_persistence(std::accumulate(bidders.begin(), - bidders.end(), - R(0.0), - [params](const Real& ps, const DgmPoint& bidder) - { return ps + std::pow(bidder.persistence_lp(params.internal_p), params.wasserstein_power); } - )) - , partial_cost(0.0) - , unassigned_bidders_persistence(0.0) - , unassigned_items_persistence(0.0) -#endif { assert(initial_epsilon >= 0.0 ); assert(epsilon_common_ratio >= 0.0 ); assert(A.size() == B.size()); -#ifdef LOG_AUCTION - - unassigned_items_persistence = total_items_persistence; - unassigned_bidders_persistence = total_bidders_persistence; - - console_logger = spdlog::get("console"); - if (not console_logger) { - console_logger = spdlog::stdout_logger_st("console"); - } - console_logger->set_pattern("[%H:%M:%S.%e] %v"); - console_logger->debug("Gauss-Seidel, num_bidders = {0}", num_bidders); - - plot_logger = spdlog::get("plot_logger"); - if (not plot_logger) { - plot_logger = spdlog::basic_logger_st("plot_logger", "plot_logger.txt"); - plot_logger->info("New plot starts here"); - plot_logger->set_pattern("%v"); - } -#endif } -#ifdef LOG_AUCTION -template<class R, class AO, class PC> -void AuctionRunnerGS<R, AO, PC>::enable_logging(const char* log_filename, const size_t _max_unassigned_to_log) -{ - log_auction = true; - max_unassigned_to_log = _max_unassigned_to_log; - - auto log = spdlog::basic_logger_st(logger_name, log_filename); - log->set_pattern("%v"); -} -#endif - template<class R, class AO, class PC> void AuctionRunnerGS<R, AO, PC>::assign_item_to_bidder(IdxType item_idx, IdxType bidder_idx) { @@ -148,58 +98,6 @@ void AuctionRunnerGS<R, AO, PC>::assign_item_to_bidder(IdxType item_idx, IdxType bidders_to_items[old_item_owner] = k_invalid_index; unassigned_bidders.insert(old_item_owner); } - - -#ifdef LOG_AUCTION - - partial_cost += get_item_bidder_cost(item_idx, bidder_idx, true); - partial_cost -= get_item_bidder_cost(item_idx, old_item_owner, true); - - unassigned_items.erase(item_idx); - - unassigned_bidders_persistence -= std::pow(bidders[bidder_idx].persistence_lp(internal_p), wasserstein_power); - - if (old_item_owner != k_invalid_index) { - // item has been assigned to some other bidder, - // and he became unassigned - unassigned_bidders_persistence += std::pow(bidders[old_item_owner].persistence_lp(internal_p), wasserstein_power); - } else { - // item was unassigned before - unassigned_items_persistence -= std::pow(items[item_idx].persistence_lp(internal_p), wasserstein_power); - } - - if (log_auction) - plot_logger->info("{0} {1} {2} {3} {4} {5} {6} {7} {8} {9}", - num_phase, - num_rounds, - unassigned_bidders.size(), - unassigned_items_persistence, - unassigned_bidders_persistence, - unassigned_items_persistence + unassigned_bidders_persistence, - partial_cost, - total_bidders_persistence, - total_items_persistence, - oracle.get_epsilon() - ); - - - if (log_auction and unassigned_bidders.size() <= max_unassigned_to_log) { - auto logger = spdlog::get(logger_name); - if (logger) { - auto item = items[item_idx]; - auto bidder = bidders[bidder_idx]; - logger->info("{0} # ({1}, {2}) # ({3}, {4}) # {5} # {6} # {7}", - num_rounds, - item.getRealX(), - item.getRealY(), - bidder.getRealX(), - bidder.getRealY(), - format_point_set_to_log(unassigned_bidders, bidders), - format_point_set_to_log(unassigned_items, items), - oracle.get_epsilon()); - } - } -#endif } @@ -220,16 +118,6 @@ void AuctionRunnerGS<R, AO, PC>::flush_assignment() } assert(unassigned_bidders.size() == bidders.size()); -#ifdef LOG_AUCTION - partial_cost = 0.0; - unassigned_bidders_persistence = total_bidders_persistence; - unassigned_items_persistence = total_items_persistence; - - for(size_t item_idx = 0; item_idx < items.size(); ++item_idx) { - unassigned_items.insert(item_idx); - } -#endif - oracle.adjust_prices(); } @@ -253,24 +141,13 @@ void AuctionRunnerGS<R, AO, PC>::run_auction_phases(const int max_num_phases, co // assert(fabs(current_result - current_result_1) < 0.001); Real denominator = current_result - num_bidders * oracle.get_epsilon(); current_result = pow(current_result, 1.0 / wasserstein_power); -#ifdef LOG_AUCTION - console_logger->info("Phase {0} done, num_rounds (cumulative) = {1}, current_result = {2}, epsilon = {3}", - phase_num, format_int(num_rounds), current_result, - oracle.get_epsilon()); -#endif + if ( denominator <= 0 ) { -#ifdef LOG_AUCTION - console_logger->info("Epsilon is too large"); -#endif + ; } else { denominator = pow(denominator, 1.0 / wasserstein_power); Real numerator = current_result - denominator; relative_error = numerator / denominator; - // spdlog::get("console")->info("relative error = {} / {} = {}, result = {}", numerator, denominator, relative_error, current_result); -#ifdef LOG_AUCTION - console_logger->info("error = {0} / {1} = {2}", - numerator, denominator, relative_error); -#endif if (relative_error <= delta) { break; } diff --git a/wasserstein/include/auction_runner_gs_single_diag.h b/wasserstein/include/auction_runner_gs_single_diag.h index f32fbbc..9746255 100644 --- a/wasserstein/include/auction_runner_gs_single_diag.h +++ b/wasserstein/include/auction_runner_gs_single_diag.h @@ -127,17 +127,6 @@ public: Real getDistanceToQthPowerInternal(); int num_phase { 0 }; int num_rounds { 0 }; -#ifdef LOG_AUCTION - bool log_auction { false }; - std::unordered_set<size_t> unassigned_items; - size_t max_unassigned_to_log { 0 }; - const char* logger_name = "auction_detailed_logger"; // the name in spdlog registry; filename is provided as parameter in enable_logging - const Real total_items_persistence; - const Real total_bidders_persistence; - Real partial_cost; - Real unassigned_bidders_persistence; - Real unassigned_items_persistence; -#endif }; } // ws diff --git a/wasserstein/include/auction_runner_gs_single_diag.hpp b/wasserstein/include/auction_runner_gs_single_diag.hpp index a3c401e..b56fbfb 100644 --- a/wasserstein/include/auction_runner_gs_single_diag.hpp +++ b/wasserstein/include/auction_runner_gs_single_diag.hpp @@ -96,24 +96,6 @@ AuctionRunnerGaussSeidelSingleDiag<R, AO>::AuctionRunnerGaussSeidelSingleDiag(co initial_epsilon(_initial_epsilon), epsilon_common_ratio(_eps_factor == 0.0 ? 5.0 : _eps_factor), max_iter_num(_max_iter_num) -#ifdef LOG_AUCTION - , total_items_persistence(std::accumulate(items.begin(), - items.end(), - R(0.0), - [_internal_p, q](const Real& ps, const DgmPoint& item) - { return ps + std::pow(item.persistence_lp(_internal_p), q); } - )) - - , total_bidders_persistence(std::accumulate(bidders.begin(), - bidders.end(), - R(0.0), - [_internal_p, q](const Real& ps, const DgmPoint& bidder) - { return ps + std::pow(bidder.persistence_lp(_internal_p), q); } - )) - , partial_cost(0.0) - , unassigned_bidders_persistence(0.0) - , unassigned_items_persistence(0.0) -#endif { assert(initial_epsilon >= 0.0 ); @@ -133,33 +115,8 @@ AuctionRunnerGaussSeidelSingleDiag<R, AO>::AuctionRunnerGaussSeidelSingleDiag(co for(size_t i = num_normal_bidders; i < num_bidders; ++i) { assert(bidders[i].is_diagonal()); } - -#ifdef LOG_AUCTION - - unassigned_items_persistence = total_items_persistence; - unassigned_bidders_persistence = total_bidders_persistence; - - if (not spdlog::get("plot_logger")) { - auto log = spdlog::basic_logger_st("plot_logger", "plot_logger.txt"); - log->info("New plot starts here"); - log->set_pattern("%v"); - } -#endif - } -#ifdef LOG_AUCTION -template<class R, class AO> -void AuctionRunnerGaussSeidelSingleDiag<R, AO>::enable_logging(const char* log_filename, const size_t _max_unassigned_to_log) -{ - log_auction = true; - max_unassigned_to_log = _max_unassigned_to_log; - - auto log = spdlog::basic_logger_st(logger_name, log_filename); - log->set_pattern("%v"); -} -#endif - template<class R, class AO> void AuctionRunnerGaussSeidelSingleDiag<R, AO>::process_diagonal_bid(const DiagonalBidR& bid) { @@ -337,61 +294,6 @@ void AuctionRunnerGaussSeidelSingleDiag<R, AO>::assign_item_to_bidder(const IdxT if (call_set_price) { oracle->set_price(item_idx, new_price, item_is_diagonal, bidder_is_diagonal, old_owner_type); } - - //std::cout << "Exit assign_item_to_bidder, state\n" << *this << std::endl; - -#ifdef LOG_AUCTION - - partial_cost += get_item_bidder_cost(item_idx, bidder_idx, true); - partial_cost -= get_item_bidder_cost(item_idx, old_owner_idx, true); - - unassigned_items.erase(item_idx); - - unassigned_bidders_persistence -= std::pow(bidders[bidder_idx].persistence_lp(internal_p), wasserstein_power); - - if (old_owner_type != OwnerType::k_none) { - // item has been assigned to some other bidder, - // and he became unassigned - unassigned_bidders_persistence += std::pow(bidders[old_owner_idx].persistence_lp(internal_p), wasserstein_power); - } else { - // item was unassigned before - unassigned_items_persistence -= std::pow(items[item_idx].persistence_lp(internal_p), wasserstein_power); - } - - auto plot_logger = spdlog::get("plot_logger"); - plot_logger->info("{0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10}", - num_phase, - num_rounds, - unassigned_normal_bidders.size(), - unassigned_diag_bidders.size(), - unassigned_items_persistence, - unassigned_bidders_persistence, - unassigned_items_persistence + unassigned_bidders_persistence, - partial_cost, - total_bidders_persistence, - total_items_persistence, - oracle->get_epsilon() - ); - - - if (log_auction and unassigned_normal_bidders.size() + unassigned_diag_bidders.size() <= max_unassigned_to_log) { - auto logger = spdlog::get(logger_name); - if (logger) { - auto item = items[item_idx]; - auto bidder = bidders[bidder_idx]; - logger->info("{0} # ({1}, {2}) # ({3}, {4}) # {5} # {6} # {7} # {8}", - num_rounds, - item.getRealX(), - item.getRealY(), - bidder.getRealX(), - bidder.getRealY(), - format_point_set_to_log(unassigned_diag_bidders, bidders), - format_point_set_to_log(unassigned_normal_bidders, bidders), - format_point_set_to_log(unassigned_items, items), - oracle->get_epsilon()); - } - } -#endif } @@ -421,17 +323,6 @@ void AuctionRunnerGaussSeidelSingleDiag<R, AO>::flush_assignment() oracle->flush_assignment(); oracle->adjust_prices(); - -#ifdef LOG_AUCTION - partial_cost = 0.0; - unassigned_bidders_persistence = total_bidders_persistence; - unassigned_items_persistence = total_items_persistence; - - for(size_t item_idx = 0; item_idx < items.size(); ++item_idx) { - unassigned_items.insert(item_idx); - } -#endif - } diff --git a/wasserstein/include/auction_runner_jac.h b/wasserstein/include/auction_runner_jac.h index 252ca32..11b8f8e 100644 --- a/wasserstein/include/auction_runner_jac.h +++ b/wasserstein/include/auction_runner_jac.h @@ -30,7 +30,6 @@ derivative works thereof, in binary and source code form. #define HERA_AUCTION_RUNNER_JAC_H #ifdef WASSERSTEIN_PURE_GEOM -#undef LOG_AUCTION #undef ORDERED_BY_PERSISTENCE #endif @@ -62,8 +61,7 @@ public: AuctionRunnerJac(const PointContainer& A, const PointContainer& B, - const AuctionParams<Real>& params, - const std::string& _log_filename_prefix = ""); + const AuctionParams<Real>& params); void set_epsilon(Real new_val); Real get_epsilon() const { return epsilon; } @@ -74,7 +72,7 @@ public: void decrease_epsilon(); Real get_wasserstein_distance(); Real get_wasserstein_cost(); - Real get_relative_error(const bool debug_output = false) const; + Real get_relative_error() const; //private: // private data PointContainer bidders; @@ -169,54 +167,7 @@ public: void print_debug(); void print_matching(); - std::string log_filename_prefix; const Real k_max_relative_error = 2.0; // if relative error cannot be estimated or is too large, use this value - -#ifdef LOG_AUCTION - - size_t parallel_threshold { 5000 }; - bool is_step_parallel {false}; - std::unordered_set<size_t> unassigned_items; - std::unordered_set<size_t> unassigned_normal_items; - std::unordered_set<size_t> unassigned_diag_items; - std::unordered_set<size_t> never_assigned_bidders; - size_t all_assigned_round { 0 }; - size_t all_assigned_round_found { false }; - - int num_rounds_non_cumulative { 0 }; // set to 0 in the beginning of each phase - int num_diag_assignments { 0 }; - int num_diag_assignments_non_cumulative { 0 }; - int num_diag_bids_submitted { 0 }; - int num_diag_stole_from_diag { 0 }; - int num_normal_assignments { 0 }; - int num_normal_assignments_non_cumulative { 0 }; - int num_normal_bids_submitted { 0 }; - - std::vector<std::vector<size_t>> price_change_cnt_vec; - - - const char* plot_logger_name = "plot_logger"; - const char* price_state_logger_name = "price_stat_logger"; - std::string plot_logger_file_name; - std::string price_stat_logger_file_name; - std::shared_ptr<spdlog::logger> plot_logger; - std::shared_ptr<spdlog::logger> price_stat_logger; - std::shared_ptr<spdlog::logger> console_logger; - - - int num_parallel_bids { 0 }; - int num_total_bids { 0 }; - - int num_parallel_diag_bids { 0 }; - int num_total_diag_bids { 0 }; - - int num_parallel_normal_bids { 0 }; - int num_total_normal_bids { 0 }; - - int num_parallel_assignments { 0 }; - int num_total_assignments { 0 }; -#endif - }; // AuctionRunnerJac diff --git a/wasserstein/include/auction_runner_jac.hpp b/wasserstein/include/auction_runner_jac.hpp index e623f4a..4dcb235 100644 --- a/wasserstein/include/auction_runner_jac.hpp +++ b/wasserstein/include/auction_runner_jac.hpp @@ -53,9 +53,7 @@ namespace ws { template<class R, class AO, class PC> AuctionRunnerJac<R, AO, PC>::AuctionRunnerJac(const PointContainer& A, const PointContainer& B, - const AuctionParams<Real>& params, - const std::string &_log_filename_prefix - ) : + const AuctionParams<Real>& params) : bidders(A), items(B), num_bidders(A.size()), @@ -71,9 +69,9 @@ namespace ws { bid_table(A.size(), std::make_pair(k_invalid_index, k_lowest_bid_value)), oracle(bidders, items, params), max_bids_per_round(params.max_bids_per_round), - dimension(params.dim), + dimension(params.dim) #ifndef WASSERSTEIN_PURE_GEOM - total_items_persistence(std::accumulate(items.begin(), + , total_items_persistence(std::accumulate(items.begin(), items.end(), R(0.0), [params](const Real &ps, const DgmPoint &item) { @@ -89,9 +87,8 @@ namespace ws { )), unassigned_bidders_persistence(total_bidders_persistence), unassigned_items_persistence(total_items_persistence), - gamma_threshold(params.gamma_threshold), + gamma_threshold(params.gamma_threshold) #endif - log_filename_prefix(_log_filename_prefix) { assert(A.size() == B.size()); @@ -119,74 +116,6 @@ namespace ws { } #endif -#ifdef LOG_AUCTION - parallel_threshold = 16; - console_logger = spdlog::get("console"); - if (not console_logger) { - console_logger = spdlog::stdout_logger_st("console"); - } - console_logger->set_pattern("[%H:%M:%S.%e] %v"); -#ifdef ORDERED_BY_PERSISTENCE - if (max_bids_per_round == 1) { - console_logger->info("Gauss-Seidel imitated by Jacobi runner, q = {0}, max_bids_per_round = {1}, batch_size = {4}, gamma_threshold = {2}, diag_first = {3} ORDERED_BY_PERSISTENCE", - wasserstein_power, - max_bids_per_round, - gamma_threshold, - diag_first, - batch_size); - } else { - console_logger->info("Jacobi runner, q = {0}, max_bids_per_round = {1}, batch_size = {4}, gamma_threshold = {2}, diag_first = {3} ORDERED_BY_PERSISTENCE", - wasserstein_power, - max_bids_per_round, - gamma_threshold, - diag_first, - batch_size); - } - -#else - if (max_bids_per_round == 1) { - console_logger->info( - "Gauss-Seidel imitated by Jacobi runner, q = {0}, max_bids_per_round = {1}, batch_size = {4}, gamma_threshold = {2}, diag_first = {3}", - wasserstein_power, - max_bids_per_round, - gamma_threshold, - diag_first, - batch_size); - } else { - console_logger->info( - "Jacobi runner, q = {0}, max_bids_per_round = {1}, batch_size = {4}, gamma_threshold = {2}, diag_first = {3}", - wasserstein_power, - max_bids_per_round, - gamma_threshold, - diag_first, - batch_size); - } -#endif - - plot_logger_file_name = log_filename_prefix + "_plot.txt"; - plot_logger = spdlog::get(plot_logger_name); - if (not plot_logger) { - plot_logger = spdlog::basic_logger_st(plot_logger_name, plot_logger_file_name); - } - plot_logger->info("New plot starts here, diagram size = {0}, gamma_threshold = {1}, epsilon_common_ratio = {2}", - bidders.size(), - gamma_threshold, - epsilon_common_ratio); - plot_logger->set_pattern("%v"); - - price_stat_logger_file_name = log_filename_prefix + "_price_change_stat"; - price_stat_logger = spdlog::get(price_state_logger_name); - if (not price_stat_logger) { - price_stat_logger = spdlog::basic_logger_st(price_state_logger_name, - price_stat_logger_file_name); - } - price_stat_logger->info( - "New price statistics starts here, diagram size = {0}, gamma_threshold = {1}, epsilon_common_ratio = {2}", - bidders.size(), - gamma_threshold, - epsilon_common_ratio); - price_stat_logger->set_pattern("%v"); -#endif } #ifndef WASSERSTEIN_PURE_GEOM @@ -233,24 +162,6 @@ namespace ws { // new edge was added to matching, increase partial cost partial_cost += get_item_bidder_cost(item_idx, bidder_idx); - -#ifdef LOG_AUCTION - if (is_item_diagonal(item_idx)) { - num_diag_assignments++; - num_diag_assignments_non_cumulative++; - } else { - num_normal_assignments++; - num_normal_assignments_non_cumulative++; - } - - if (k_invalid_index != old_item_owner) { - if (is_bidder_diagonal(bidder_idx) and is_bidder_diagonal(old_item_owner)) { - num_diag_stole_from_diag++; - } - } -#endif - - //sanity_check(); } template<class R, class AO, class PC> @@ -268,15 +179,6 @@ namespace ws { IdxValPairR best_bid{bid_table[item_idx]}; assign_item_to_bidder(item_idx, best_bid.first); oracle.set_price(item_idx, best_bid.second); -#ifdef LOG_AUCTION - - if (is_step_parallel) { - num_parallel_assignments++; - } - num_total_assignments++; - - price_change_cnt_vec.back()[item_idx]++; -#endif } template<class R, class AO, class PC> @@ -300,18 +202,6 @@ namespace ws { bid_table[item_idx].second = bid_value; } items_with_bids.insert(item_idx); - -#ifdef LOG_AUCTION - - num_total_bids++; - - - if (is_bidder_diagonal(bidder_idx)) { - num_diag_bids_submitted++; - } else { - num_normal_bids_submitted++; - } -#endif } template<class R, class AO, class PC> @@ -347,7 +237,7 @@ namespace ws { template<class R, class AO, class PC> typename AuctionRunnerJac<R, AO, PC>::Real - AuctionRunnerJac<R, AO, PC>::get_relative_error(const bool debug_output) const + AuctionRunnerJac<R, AO, PC>::get_relative_error() const { if (partial_cost == 0.0 and unassigned_bidders.empty()) return 0.0; @@ -360,21 +250,10 @@ namespace ws { // cost minus n epsilon Real reduced_cost = partial_cost - num_bidders * get_epsilon(); if (reduced_cost < 0) { -#ifdef LOG_AUCTION - if (debug_output) { - console_logger->info("Epsilon too large, reduced_cost = {0}, gamma = {1}", reduced_cost, gamma); - } -#endif result = k_max_relative_error; } else { Real denominator = std::pow(reduced_cost, 1.0 / wasserstein_power) - gamma; if (denominator <= 0) { -#ifdef LOG_AUCTION - if (debug_output) { - console_logger->info("Epsilon too large, reduced_cost = {0}, denominator = {1}, gamma = {2}", - reduced_cost, denominator, gamma); - } -#endif result = k_max_relative_error; } else { Real numerator = 2 * gamma + @@ -382,17 +261,6 @@ namespace ws { std::pow(reduced_cost, 1.0 / wasserstein_power); result = numerator / denominator; -#ifdef LOG_AUCTION - if (debug_output) { - console_logger->info( - "Reduced_cost = {0}, denominator = {1}, numerator {2}, error = {3}, gamma = {4}", - reduced_cost, - denominator, - numerator, - result, - gamma); - } -#endif } } return result; @@ -437,30 +305,6 @@ namespace ws { unassigned_bidders_persistence = total_bidders_persistence; unassigned_items_persistence = total_items_persistence; -#ifdef LOG_AUCTION - - price_change_cnt_vec.push_back(std::vector<size_t>(num_items, 0)); - - never_assigned_bidders = unassigned_bidders; - - for (size_t item_idx = 0; item_idx < items.size(); ++item_idx) { - unassigned_items.insert(item_idx); - if (is_item_normal(item_idx)) { - unassigned_normal_items.insert(item_idx); - } else { - unassigned_diag_items.insert(item_idx); - } - } - - num_diag_bids_submitted = 0; - num_normal_bids_submitted = 0; - num_diag_assignments = 0; - num_normal_assignments = 0; - - all_assigned_round = 0; - all_assigned_round_found = false; - num_rounds_non_cumulative = 0; -#endif #endif } // flush_assignment @@ -481,65 +325,6 @@ namespace ws { flush_assignment(); run_auction_phase(); -#ifdef LOG_AUCTION - console_logger->info( - "Phase {0} done, current_result = {1}, eps = {2}, error = {7}, num_rounds = {3}, num_assignments = {4}, num_bids_submitted = {5}, # unassigned = {6}", - num_phase, - partial_cost, - get_epsilon(), - format_int<>(num_rounds), - format_int<>(num_normal_assignments + num_diag_assignments), - format_int<>(num_normal_bids_submitted + num_diag_bids_submitted), - unassigned_bidders.size(), - get_relative_error(num_phase == 1) - ); - -// console_logger->info("num_rounds (non-cumulative)= {0}, num_diag_assignments = {1}, num_normal_assignments = {2}, num_diag_bids_submitted = {3}, num_normal_bids_submitted = {4}", -// format_int<>(num_rounds_non_cumulative), -// format_int<>(num_diag_assignments), -// format_int<>(num_normal_assignments), -// format_int<>(num_diag_bids_submitted), -// format_int<>(num_normal_bids_submitted) -// ); - - console_logger->info( - "num_parallel_bids / num_total_bids = {0} / {1} = {2}, num_parallel_assignments / num_total_aassignments = {3} / {4} = {5}", - format_int<>(num_parallel_bids), - format_int<>(num_total_bids), - static_cast<double>(num_parallel_bids) / static_cast<double>(num_total_bids), - format_int<>(num_parallel_assignments), - format_int<>(num_total_assignments), - static_cast<double>(num_parallel_assignments) / static_cast<double>(num_total_assignments) - ); - - console_logger->info( - "num_parallel_diag_bids / num_total_diag_bids = {0} / {1} = {2}, num_parallel_normal_bids / num_total_normal_bids = {3} / {4} = {5}", - format_int<>(num_parallel_diag_bids), - format_int<>(num_total_diag_bids), - static_cast<double>(num_parallel_diag_bids) / static_cast<double>(num_total_diag_bids), - format_int<>(num_parallel_normal_bids), - format_int<>(num_total_normal_bids), - static_cast<double>(num_parallel_normal_bids) / static_cast<double>(num_total_normal_bids) - ); - -// console_logger->info("num_rounds before all biders assigned = {0}, num_rounds (non-cumulative)= {1}, fraction = {2}", -// format_int<>(all_assigned_round), -// format_int<>(num_rounds_non_cumulative), -// static_cast<double>(all_assigned_round) / static_cast<double>(num_rounds_non_cumulative) -// ); - - for (size_t item_idx = 0; item_idx < num_items; ++item_idx) { - price_stat_logger->info("{0} {1} {2} {3} {4}", - phase_num, - item_idx, - items[item_idx][0], - items[item_idx][1], - price_change_cnt_vec.back()[item_idx] - ); - } -#endif - - if (is_done()) break; else @@ -618,31 +403,15 @@ namespace ws { unassigned_normal_bidders.erase(bidder_idx); } - -#ifdef LOG_AUCTION - never_assigned_bidders.erase(bidder_idx); - if (never_assigned_bidders.empty() and not all_assigned_round_found) { - all_assigned_round = num_rounds_non_cumulative; - all_assigned_round_found = true; - } -#endif #endif } template<class R, class AO, class PC> void AuctionRunnerJac<R, AO, PC>::remove_unassigned_item(const size_t item_idx) { + // to suppress unused parameter warning + (void)item_idx; #ifndef WASSERSTEIN_PURE_GEOM unassigned_items_persistence -= get_cost_to_diagonal(items[item_idx]); - -#ifdef LOG_AUCTION - unassigned_items.erase(item_idx); - - if (is_item_normal(item_idx)) { - unassigned_normal_items.erase(item_idx); - } else { - unassigned_diag_items.erase(item_idx); - } -#endif #endif } @@ -650,12 +419,6 @@ namespace ws { template<class Range> void AuctionRunnerJac<R, AO, PC>::run_bidding_step(const Range &active_bidders) { -#ifdef LOG_AUCTION - is_step_parallel = false; - size_t diag_bids_submitted = 0; - size_t normal_bids_submitted = 0; -#endif - clear_bid_table(); size_t bids_submitted = 0; for (const auto bidder_idx : active_bidders) { @@ -663,37 +426,8 @@ namespace ws { ++bids_submitted; submit_bid(bidder_idx, oracle.get_optimal_bid(bidder_idx)); - -#ifdef LOG_AUCTION - if (is_bidder_diagonal(bidder_idx)) { - diag_bids_submitted++; - } else { - normal_bids_submitted++; - } - - if (bids_submitted >= parallel_threshold) { - is_step_parallel = true; - } - - if (bids_submitted >= max_bids_per_round) { - break; - } - if (diag_first and not unassigned_diag_bidders.empty() and - diag_bids_submitted >= oracle.get_heap_top_size()) { - continue; - } -#endif } -#ifdef LOG_AUCTION - num_total_diag_bids += diag_bids_submitted; - num_total_normal_bids += normal_bids_submitted; - if (is_step_parallel) { - num_parallel_bids += bids_submitted; - num_parallel_diag_bids += diag_bids_submitted; - num_parallel_normal_bids += normal_bids_submitted; - } -#endif } template<class R, class AO, class PC> @@ -720,12 +454,6 @@ namespace ws { do { num_rounds++; -#ifdef LOG_AUCTION - num_diag_stole_from_diag = 0; - num_normal_assignments_non_cumulative = 0; - num_diag_assignments_non_cumulative = 0; - num_rounds_non_cumulative++; -#endif // bidding #ifdef ORDERED_BY_PERSISTENCE @@ -756,26 +484,6 @@ namespace ws { for (auto item_idx : items_with_bids) { assign_to_best_bidder(item_idx); } -#ifdef LOG_AUCTION - plot_logger->info("{0} {1} {2} {3} {4} {5} {6} {7} {8} {9} {10} {11} {12} {13} {14}", - num_phase, - num_rounds, - unassigned_bidders.size(), - get_gamma(), - partial_cost, - oracle.get_epsilon(), - unassigned_normal_bidders.size(), - unassigned_diag_bidders.size(), - unassigned_normal_items.size(), - unassigned_diag_items.size(), - num_normal_assignments_non_cumulative, - num_diag_assignments_non_cumulative, - oracle.get_heap_top_size(), - get_relative_error(false), - num_diag_stole_from_diag - ); -#endif - //sanity_check(); } while (continue_auction_phase()); } diff --git a/wasserstein/include/basic_defs_ws.h b/wasserstein/include/basic_defs_ws.h index bdcfd75..73c761c 100644 --- a/wasserstein/include/basic_defs_ws.h +++ b/wasserstein/include/basic_defs_ws.h @@ -236,7 +236,7 @@ namespace ws template<class Real> struct DistImpl<Real, DiagramPoint<Real>> { - Real operator()(const DiagramPoint<Real>& a, const DiagramPoint<Real>& b, const Real p, const int dim) + Real operator()(const DiagramPoint<Real>& a, const DiagramPoint<Real>& b, const Real p, const int /*dim */) { Real result = 0.0; if ( a.is_diagonal() and b.is_diagonal()) { diff --git a/wasserstein/include/dnn/parallel/tbb.h b/wasserstein/include/dnn/parallel/tbb.h index 712f812..20e886e 100644 --- a/wasserstein/include/dnn/parallel/tbb.h +++ b/wasserstein/include/dnn/parallel/tbb.h @@ -4,7 +4,7 @@ #include <vector> #include <boost/range.hpp> -#include <boost/bind.hpp> +#include <boost/bind/bind.hpp> #include <boost/foreach.hpp> #ifdef TBB @@ -17,6 +17,8 @@ #include <boost/serialization/collections_load_imp.hpp> #include <boost/serialization/collections_save_imp.hpp> +using namespace boost::placeholders; + namespace hera { namespace ws diff --git a/wasserstein/include/wasserstein.h b/wasserstein/include/wasserstein.h index 142fcbb..1530b79 100644 --- a/wasserstein/include/wasserstein.h +++ b/wasserstein/include/wasserstein.h @@ -208,8 +208,7 @@ namespace ws template<class RealType> inline RealType wasserstein_cost_vec(const std::vector<DiagramPoint<RealType>>& A, const std::vector<DiagramPoint<RealType>>& B, - AuctionParams<RealType>& params, - const std::string& _log_filename_prefix) + AuctionParams<RealType>& params) { if (params.wasserstein_power < 1.0) { throw std::runtime_error("Bad q in Wasserstein " + std::to_string(params.wasserstein_power)); @@ -230,7 +229,7 @@ namespace ws RealType result; // just use Gauss-Seidel - AuctionRunnerGS<RealType> auction(A, B, params, _log_filename_prefix); + AuctionRunnerGS<RealType> auction(A, B, params); auction.run_auction(); result = auction.get_wasserstein_cost(); params.final_relative_error = auction.get_relative_error(); @@ -245,8 +244,7 @@ template<class PairContainer> inline typename DiagramTraits<PairContainer>::RealType wasserstein_cost(const PairContainer& A, const PairContainer& B, - AuctionParams< typename DiagramTraits<PairContainer>::RealType >& params, - const std::string& _log_filename_prefix = "") + AuctionParams< typename DiagramTraits<PairContainer>::RealType >& params) { using Traits = DiagramTraits<PairContainer>; @@ -355,7 +353,7 @@ wasserstein_cost(const PairContainer& A, if (infinity_cost == plus_inf) { return infinity_cost; } else { - return infinity_cost + wasserstein_cost_vec(dgm_A, dgm_B, params, _log_filename_prefix); + return infinity_cost + wasserstein_cost_vec(dgm_A, dgm_B, params); } } @@ -364,11 +362,10 @@ template<class PairContainer> inline typename DiagramTraits<PairContainer>::RealType wasserstein_dist(const PairContainer& A, const PairContainer& B, - AuctionParams<typename DiagramTraits<PairContainer>::RealType>& params, - const std::string& _log_filename_prefix = "") + AuctionParams<typename DiagramTraits<PairContainer>::RealType>& params) { using Real = typename DiagramTraits<PairContainer>::RealType; - return std::pow(hera::wasserstein_cost(A, B, params, _log_filename_prefix), Real(1.)/params.wasserstein_power); + return std::pow(hera::wasserstein_cost(A, B, params), Real(1.)/params.wasserstein_power); } } // end of namespace hera diff --git a/wasserstein/tests/CMakeLists.txt b/wasserstein/tests/CMakeLists.txt new file mode 100644 index 0000000..b379da2 --- /dev/null +++ b/wasserstein/tests/CMakeLists.txt @@ -0,0 +1,9 @@ +add_executable(wasserstein_test tests_main.cpp test_hera_wasserstein.cpp test_hera_wasserstein_pure_geom.cpp) +target_link_libraries(wasserstein_test PRIVATE ${libraries}) + +target_include_directories(tests PRIVATE ${CMAKE_CURRENT_SOURCE_DIR}/../include + ${CMAKE_CURRENT_SOURCE_DIR}../extern/Catch2/src) + +target_link_libraries(tests PRIVATE Catch2::Catch2WithMain) + +add_test(NAME all COMMAND wasserstein_test) diff --git a/wasserstein/tests/test_hera_wasserstein.cpp b/wasserstein/tests/test_hera_wasserstein.cpp index 6f5de3b..6a0404a 100644 --- a/wasserstein/tests/test_hera_wasserstein.cpp +++ b/wasserstein/tests/test_hera_wasserstein.cpp @@ -1,12 +1,9 @@ -#define LOG_AUCTION #include "catch/catch.hpp" #include <sstream> #include <iostream> -#undef LOG_AUCTION - #include "wasserstein.h" #include "tests_reader.h" diff --git a/wasserstein/tests/test_hera_wasserstein_pure_geom.cpp b/wasserstein/tests/test_hera_wasserstein_pure_geom.cpp index 9603ceb..e7aa417 100644 --- a/wasserstein/tests/test_hera_wasserstein_pure_geom.cpp +++ b/wasserstein/tests/test_hera_wasserstein_pure_geom.cpp @@ -4,8 +4,6 @@ #include <iostream> -#undef LOG_AUCTION - #include "wasserstein_pure_geom.hpp" #include "tests_reader.h" diff --git a/wasserstein/tests/tests_main.cpp b/wasserstein/tests/tests_main.cpp index d24407e..1c77b13 100644 --- a/wasserstein/tests/tests_main.cpp +++ b/wasserstein/tests/tests_main.cpp @@ -1,3 +1,2 @@ -#define LOG_AUCTION #define CATCH_CONFIG_MAIN #include "catch/catch.hpp" |