feat: Implement expt_0821

Signed-off-by: KunoiSayami <[email protected]>

1 files changed, 76 insertions, 0 deletions

diff --git a/expt_0821.cpp b/expt_0821.cpp
new file mode 100644
index 0000000..330cf40
--- /dev/null
+++ b/expt_0821.cpp
@@ -0,0 +1,76 @@
+#include "sortlib.h"
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <iostream>
+#include <vector>
+
+typedef unsigned long long key_type;
+std::vector<key_type> population_vector, sample_vector;
+constexpr size_t SAMPLE_LENGTH = 1023, TEST_LENGTH = 1024;
+constexpr int MOVE_OFFSET = sizeof(key_type) * 8 - 1;
+
+auto custom_sort = CustomSort<key_type>(SAMPLE_LENGTH, MOVE_OFFSET);
+
+unsigned long long max_value = 0, min_value = 0xfffffffff;
+inline void store_into_vector(unsigned long long value) {
+  if (max_value < value) {
+    max_value = value;
+  }
+  if (min_value > value) {
+    min_value = value;
+  }
+  population_vector.push_back(value);
+}
+
+void valid_sort(std::vector<key_type> &tmp) {
+  auto iter_end = population_vector.begin() + SAMPLE_LENGTH + 5;
+  for (auto it = population_vector.begin() + SAMPLE_LENGTH; it != iter_end;
+       it++) {
+    // long std_search =
+    //     std::lower_bound(tmp.begin(), tmp.end(), *it) - tmp.begin();
+    long std_search = custom_sort.original_binary_search(
+                          tmp.data(), tmp.data() + tmp.size(), *it) -
+                      tmp.data();
+
+    auto cuda_binary_search =
+        custom_sort.binary_search(sample_vector.data(), *it) -
+        sample_vector.data();
+    cuda_binary_search = custom_sort.calculate_location(cuda_binary_search) - 1;
+    /*printf("%ld:%ld %llu:%llu\n", std_search, cuda_binary_search,
+     *(tmp.begin() + std_search),
+     *(cuda_binary_search + sample_vector.begin()));*/
+    printf("%ld:%ld \n", std_search, cuda_binary_search);
+    // assert(std_search == cuda_binary_search);
+  }
+}
+
+int main() {
+  FILE *file = fopen("normal_distribution.txt", "r");
+  assert(file);
+  for (long long i; fscanf(file, "%lld ", &i) != EOF; store_into_vector(i))
+    ;
+  fclose(file);
+
+  std::vector<key_type> tmp(population_vector.begin(),
+                            population_vector.begin() + SAMPLE_LENGTH - 2);
+  tmp.push_back(max_value);
+  tmp.push_back(min_value);
+
+  std::sort(tmp.begin(), tmp.end());
+
+  sample_vector.resize(SAMPLE_LENGTH);
+  for (size_t i = 0; i < SAMPLE_LENGTH; i++) {
+    sample_vector[custom_sort.calculate_location_inverse(i) - 1] = tmp[i];
+    auto location = custom_sort.calculate_location(i);
+    auto location2 = custom_sort.calculate_location_inverse(location - 1);
+    // printf("%zu %zu\n", location, location2);
+    assert(location2 - 1 == i);
+  }
+  // valid_sort(tmp);
+  /*for (auto element : sample_vector) {
+    printf("%d ", element);
+  }*/
+  valid_sort(tmp);
+  puts("");
+}
\ No newline at end of file