feat: Implement expt_0821

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

1 files changed, 14 insertions, 13 deletions

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