Main.cpp 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121
  1. #include "../test/Test.hpp"
  2. #include "core/data/HashMap.hpp"
  3. #include "core/data/ProbingHashMap.hpp"
  4. #include "core/utils/Clock.hpp"
  5. #include "core/utils/Random.hpp"
  6. using Millis = Core::Clock::Nanos;
  7. struct Timer {
  8. Core::Clock::Nanos nanos;
  9. Timer() : nanos(0) {
  10. CORE_TEST_ERROR(Core::Clock::getNanos(nanos));
  11. }
  12. Core::Clock::Nanos get() const {
  13. Core::Clock::Nanos nanos2 = 0;
  14. CORE_TEST_ERROR(Core::Clock::getNanos(nanos2));
  15. return nanos2 - nanos;
  16. }
  17. };
  18. template<typename Map>
  19. static Core::Clock::Nanos testSearch(const Map& m) {
  20. Timer t;
  21. volatile int sum = 0;
  22. for(int i = 0; i < 10000; i++) {
  23. for(int k = -5000; k < 5000; k++) {
  24. const int* s = m.search(i + k);
  25. if(s != nullptr) {
  26. sum = sum + *s;
  27. }
  28. }
  29. }
  30. return t.get();
  31. }
  32. template<typename Map>
  33. static Core::Clock::Nanos testEmptySearch(const Map& m) {
  34. Timer t;
  35. volatile int sum = 0;
  36. for(int i = 0; i < 100'000'000; i++) {
  37. const int* s = m.search(-i);
  38. if(s != nullptr) {
  39. sum = sum + *s;
  40. }
  41. }
  42. return t.get();
  43. }
  44. template<typename Map>
  45. static void fillOrder(Map& m) {
  46. for(int i = 0; i < 10000; i++) {
  47. CORE_TEST_ERROR(m.add(i, i * i));
  48. }
  49. }
  50. template<typename Map>
  51. static void fillChaos(Map& m) {
  52. Core::Random random(0);
  53. for(int i = 0; i < 10000; i++) {
  54. int r = random.next(0, 9999);
  55. CORE_TEST_ERROR(m.add(r, r * r));
  56. }
  57. }
  58. template<typename Map>
  59. static Millis average(Map& m, Core::Clock::Nanos (*f)(const Map&), int n) {
  60. Core::Clock::Nanos sum = 0;
  61. for(int i = 0; i < n; i++) {
  62. sum += f(m);
  63. }
  64. return sum / (n * 1'000'000);
  65. }
  66. static void order(int n) {
  67. Core::HashMap<int, int> m;
  68. Core::ProbingHashMap<int, int> m2;
  69. fillOrder(m);
  70. fillOrder(m2);
  71. CORE_LOG_INFO("Order Chaining | Order Probing");
  72. CORE_LOG_INFO("Search | # ms | # ms", average(m, testSearch, n),
  73. average(m2, testSearch, n));
  74. CORE_LOG_INFO("EmptySearch | # ms | # ms", average(m, testEmptySearch, n),
  75. average(m2, testEmptySearch, n));
  76. }
  77. static void chaos(int n) {
  78. Core::HashMap<int, int> m;
  79. Core::ProbingHashMap<int, int> m2;
  80. fillChaos(m);
  81. fillChaos(m2);
  82. CORE_LOG_INFO("Order Chaining | Order Probing");
  83. CORE_LOG_INFO("Search | # ms | # ms", average(m, testSearch, n),
  84. average(m2, testSearch, n));
  85. CORE_LOG_INFO("EmptySearch | # ms | # ms", average(m, testEmptySearch, n),
  86. average(m2, testEmptySearch, n));
  87. }
  88. static void testProbing(int n) {
  89. Core::ProbingHashMap<int, int> m;
  90. Core::ProbingHashMap<int, int> m2;
  91. fillOrder(m);
  92. fillChaos(m2);
  93. CORE_LOG_INFO("Order | Chaos");
  94. CORE_LOG_INFO("Search | # ms | # ms", average(m, testSearch, n),
  95. average(m2, testSearch, n));
  96. CORE_LOG_INFO("EmptySearch | # ms | # ms", average(m, testEmptySearch, n),
  97. average(m2, testEmptySearch, n));
  98. }
  99. int main() {
  100. (void)order;
  101. (void)chaos;
  102. (void)testProbing;
  103. order(3);
  104. chaos(3);
  105. // testProbing(3);
  106. Core::Test::finalize();
  107. return 0;
  108. }