Main.cpp 3.3 KB

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