feat: Add vaild_sort.cpp

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

2 files changed, 194 insertions, 1 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 9d72a91..71f9202 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -4,6 +4,13 @@ set(CMAKE_CUDA_STANDARD 14)
 
 #set(GXX_INCLUDE /usr/lib/gcc/x86_64-pc-linux-gnu/11.3.0/include)
 
+# from: Coelacanthus
+add_compile_options(
+        $<$<COMPILE_LANGUAGE:CXX>:-Wall>
+        $<$<COMPILE_LANGUAGE:CXX>:-pedantic>
+        $<$<COMPILE_LANGUAGE:CXX>:-Wextra>
+)
+
 add_executable(lockfree main.cu)
 #add_definitions(-DNUM_ITEMS=1048576 -DKEYS=1048576 -DFACTOR=1)
 
@@ -117,5 +124,8 @@ set_target_properties(expt_0809 PROPERTIES CUDA_ARCHITECTURES "75")
 set_target_properties(expt_0809 PROPERTIES LINKER_LANGUAGE CUDA)
 
 
-add_executable(valid_sort valid_sort_new.cpp)
+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
diff --git a/valid_sort.cpp b/valid_sort.cpp
new file mode 100644
index 0000000..f4d5ef4
--- /dev/null
+++ b/valid_sort.cpp
@@ -0,0 +1,183 @@
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <iostream>
+#include <vector>
+
+typedef unsigned long long key_type;
+std::vector<unsigned long long> population_vector, sample_vector;
+std::vector<bool> result_storage;
+constexpr size_t SAMPLE_LENGTH = 1024, TEST_LENGTH = 1024;
+
+constexpr int MOVE_OFFSET = sizeof(key_type) * 8 - 1;
+
+size_t fast_log(size_t a) {
+  float t = a;
+  return (((*(int *)&t) >> 23) + 1) & 127;
+}
+
+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;
+}
+
+size_t calculate_location_inverse(size_t index) {
+  ++index;
+  size_t low_bit = index & (-index);
+  return (low_bit == SAMPLE_LENGTH) ? SAMPLE_LENGTH
+                                    : ((SAMPLE_LENGTH + index) / low_bit) >> 1;
+}
+
+/*size_t calculate_location(size_t index) {
+  int step = (int)std::log2(++index) + 1;
+  auto location =
+      SAMPLE_LENGTH / (1 << step) * ((index & ((1 << (step - 1)) - 1)) * 2 + 1);
+  return location ? location : SAMPLE_LENGTH;
+}*/
+
+const key_type *cudaBinarySearch(key_type *const start, const key_type val) {
+  int step_limit = (int)fast_log(SAMPLE_LENGTH) - 1;
+  key_type *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));
+    son = son * 2 + (int)((*last_known_point - val) >> MOVE_OFFSET);
+    // 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;
+    assert(last_known_point < &*sample_vector.end());
+    // printf("%d\n", *last_known_point);
+  }
+  return last_known_point;
+}
+
+long double sample_cdf(long double x) {
+  auto it = std::lower_bound(sample_vector.begin(), sample_vector.end(), x);
+  if (it == sample_vector.end()) {
+    return 1;
+  }
+  if (it == sample_vector.begin()) {
+    return 0;
+  }
+  auto it_prev = it - 1;
+
+  return ((long double)(it_prev - sample_vector.begin()) +
+          (long double)(x - *it_prev) / (*it - *it_prev)) /
+         (long double)(sample_vector.size() - 1);
+}
+
+long double sample_cdf_custom_version(long double x) {
+  auto it = cudaBinarySearch(sample_vector.data(), x);
+  assert(it < &*sample_vector.end());
+  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 test = ((long double)(it_prev - (&*sample_vector.begin())) +
+               (long double)(x - *it_prev) / (*it - *it_prev)) /
+              (long double)(sample_vector.size() - 1);
+  return test;
+}
+
+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);
+}
+
+inline long double safe_ceil(long double value) {
+  auto c = std::ceil(value);
+  return c == 0 ? 1 : c;
+}
+
+typedef long double (*cdf_function_type)(long double);
+typedef void (*init_function_type)(const std::vector<key_type> &);
+
+void process_function(const std::vector<key_type> &tmp,
+                      cdf_function_type cdf_function, init_function_type init) {
+  sample_vector.clear();
+  sample_vector.resize(SAMPLE_LENGTH);
+
+  init(tmp);
+
+  for (int scale = 2; scale < 9; scale++) {
+    const long split_size = TEST_LENGTH * scale;
+    result_storage.clear();
+    result_storage.resize(scale * SAMPLE_LENGTH, false);
+    auto slice_size = 1.0 / (double)(split_size);
+
+    // printf("\nscale: %d\n", scale);
+    for (size_t i = 0; i < TEST_LENGTH; i++) {
+
+      auto index =
+          (int)safe_ceil(cdf_function(population_vector[i + SAMPLE_LENGTH]) /
+                         slice_size) -
+          1;
+      // printf("index: %d\n", index);
+      while (result_storage[index]) {
+        index++;
+      }
+      result_storage[index] = true;
+    }
+    for (auto &&element : result_storage) {
+      printf("%d", element ? 1 : 0);
+    }
+    puts("");
+  }
+}
+
+void process_function(const std::vector<key_type> &tmp,
+                      cdf_function_type cdf_function) {
+  process_function(tmp, cdf_function, [](const std::vector<key_type> &tmp) {
+    sample_vector.assign(tmp.begin(), tmp.end());
+  });
+}
+
+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());
+
+  process_function(tmp, sample_cdf);
+  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];
+          auto location = calculate_location(i);
+          auto location2 = calculate_location_inverse(location - 1);
+          assert(location2 - 1 == i);
+          // printf("%zu %zu\n", location, location2);
+        }
+      });
+}
\ No newline at end of file