feat: Implement expt_0821

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

4 files changed, 175 insertions, 14 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 71f9202..e05ef87 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -128,4 +128,7 @@ add_executable(valid_sort_new valid_sort_new.cpp)
 target_link_libraries(valid_sort_new m stdc++)
 
 add_executable(valid_sort valid_sort.cpp)
-target_link_libraries(valid_sort m stdc++)
\ No newline at end of file
+target_link_libraries(valid_sort m stdc++)
+
+add_executable(expt_0821 expt_0821.cpp sortlib.h)
+target_link_libraries(expt_0821 m stdc++)
\ No newline at end of file
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
diff --git a/sortlib.h b/sortlib.h
new file mode 100644
index 0000000..c00c07f
--- /dev/null
+++ b/sortlib.h
@@ -0,0 +1,81 @@
+#pragma once
+#include <cassert>
+#include <cstddef>
+#include <cstdio>
+
+template <typename C> class CustomSort {
+public:
+  CustomSort(size_t length, int move_offset)
+      : LENGTH(length), MOVE_OFFSET(move_offset) {}
+  const size_t LENGTH;
+  const int MOVE_OFFSET;
+
+  static size_t fast_log(size_t a) {
+    float t = a;
+    return (((*(int *)&t) >> 23) + 1) & 127;
+  }
+  size_t calculate_location(size_t index) const {
+    size_t bit_low = (LENGTH + 1) >> fast_log(++index) >> 1;
+    return (((index << 1) | 1) * bit_low - LENGTH - 1);
+  }
+
+  size_t calculate_location_inverse(size_t index) const {
+    index++;
+    size_t low_bit = index & (-index);
+    return ((LENGTH + index) / low_bit) >> 1;
+  }
+
+  __attribute__((unused)) void testCalculation() const {
+    for (size_t i = 0; i < LENGTH; i++) {
+      auto l = calculate_location(i);
+      auto l2 = calculate_location_inverse(l - 1);
+      assert(l == l2);
+    }
+  }
+  template <typename T> const T *binary_search(T *const start, const T val) {
+
+    int step_limit = (int)fast_log(LENGTH);
+    T *last_known_point = start;
+    auto son = 0;
+
+    for (int i = 0; i < step_limit; i++) {
+      const auto next_level_start = start + (1 << (i + 1)) - 1;
+      if (*last_known_point == val) {
+        return last_known_point;
+      }
+
+      // son = get_son_from_step(son, (*last_known_point > val));
+      auto tmp = (int)((*last_known_point - val) >> MOVE_OFFSET);
+      printf("%llu %llu ", val, *last_known_point);
+      son = son * 2 + tmp;
+      puts(tmp == 0 ? "1:left" : "1:right");
+      // if (son < 0) son = 0;
+      /*printf("%d %d %d\n", (1 << (i + 1)), son,
+             -(int)((*last_known_point - val) >> MOVE_OFFSET));*/
+      last_known_point = next_level_start + son;
+    }
+    return last_known_point;
+  }
+  template <typename T> T *original_binary_search(T *start, T *end, T &val) {
+    auto begin = start;
+    T *last_known_point = nullptr;
+    while (begin < end) {
+      auto mid = (end - begin) / 2;
+      auto mid_val = *(begin + mid);
+      if (val == mid_val) {
+        return begin + mid;
+      }
+      printf("%llu %llu ", val, mid_val);
+      puts(val > mid_val ? "right" : "left");
+      /*begin += (int)((mid_val - val) >> MOVE_OFFSET) & (mid + 1);
+      end -= (int)(~((mid_val - val) >> MOVE_OFFSET)) & (mid + 1);*/
+      if (val > mid_val) {
+        begin = begin + mid + 1;
+      } else {
+        end = end - mid - 1;
+      }
+      last_known_point = begin;
+    }
+    return last_known_point;
+  }
+};
diff --git a/valid_sort.cpp b/valid_sort.cpp
index f4d5ef4..399ac08 100644
--- a/valid_sort.cpp
+++ b/valid_sort.cpp
@@ -10,18 +10,20 @@ std::vector<bool> result_storage;
 constexpr size_t SAMPLE_LENGTH = 1024, TEST_LENGTH = 1024;
 
 constexpr int MOVE_OFFSET = sizeof(key_type) * 8 - 1;
+constexpr size_t MAX_SCALE = 3;
 
 size_t fast_log(size_t a) {
   float t = a;
   return (((*(int *)&t) >> 23) + 1) & 127;
 }
-
+// calculate location by number
 size_t calculate_location(size_t index) {
   size_t bit_low = SAMPLE_LENGTH >> fast_log(++index) >> 1;
   return (!bit_low) ? SAMPLE_LENGTH
                     : ((index << 1) | 1) * bit_low - SAMPLE_LENGTH;
 }
 
+// calculate number by location
 size_t calculate_location_inverse(size_t index) {
   ++index;
   size_t low_bit = index & (-index);
@@ -53,8 +55,6 @@ const key_type *cudaBinarySearch(key_type *const start, const key_type val) {
     /*printf("%d %d %d\n", (1 << (i + 1)), son,
            -(int)((*last_known_point - val) >> MOVE_OFFSET));*/
     last_known_point = next_level_start + son;
-    assert(last_known_point < &*sample_vector.end());
-    // printf("%d\n", *last_known_point);
   }
   return last_known_point;
 }
@@ -77,23 +77,23 @@ long double sample_cdf(long double x) {
 long double sample_cdf_custom_version(long double x) {
   auto it = cudaBinarySearch(sample_vector.data(), x);
   assert(it < &*sample_vector.end());
+  assert(it >= sample_vector.data());
   if (it == (&*sample_vector.end() - 1)) {
     return 1;
   }
   if (it == sample_vector.data()) {
     return 0;
   }
-  auto it_prev = sample_vector.data() +
-                 calculate_location_inverse(
-                     calculate_location(it - sample_vector.data()) - 2) -
-                 1;
 
-  // printf("------------ %ld %ld\n", it - &*sample_vector.begin(), it_prev -
-  // it);
+  auto prev_real_location =
+      calculate_location_inverse(it - sample_vector.data()) - 2;
+
+  auto it_prev =
+      sample_vector.data() + calculate_location(prev_real_location) - 1;
 
-  auto test = ((long double)(it_prev - (&*sample_vector.begin())) +
+  auto test = ((long double)prev_real_location +
                (long double)(x - *it_prev) / (*it - *it_prev)) /
-              (long double)(sample_vector.size() - 1);
+              (long double)(SAMPLE_LENGTH - 1);
   return test;
 }
 
@@ -123,7 +123,7 @@ void process_function(const std::vector<key_type> &tmp,
 
   init(tmp);
 
-  for (int scale = 2; scale < 9; scale++) {
+  for (size_t scale = 2; scale < MAX_SCALE; scale++) {
     const long split_size = TEST_LENGTH * scale;
     result_storage.clear();
     result_storage.resize(scale * SAMPLE_LENGTH, false);
@@ -173,11 +173,12 @@ int main() {
   process_function(
       tmp, sample_cdf_custom_version, [](const std::vector<key_type> &tmp_) {
         for (size_t i = 0; i < SAMPLE_LENGTH; i++) {
-          sample_vector[calculate_location(i) - 1] = tmp_[i];
+          sample_vector[calculate_location_inverse(i) - 1] = tmp_[i];
           auto location = calculate_location(i);
           auto location2 = calculate_location_inverse(location - 1);
           assert(location2 - 1 == i);
           // printf("%zu %zu\n", location, location2);
         }
       });
+  valid_sort(tmp);
 }
\ No newline at end of file