From e7de21daf6c674633ef1159c2fd042523c1ec32e Mon Sep 17 00:00:00 2001
From: KunoiSayami <i@leanhe.dev>
Date: Mon, 12 Jun 2023 00:51:30 +0800
Subject: refector: Rename last year experimental

Signed-off-by: KunoiSayami <i@leanhe.dev>
---
 expt_220802.cpp | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 76 insertions(+)
 create mode 100644 expt_220802.cpp

(limited to 'expt_220802.cpp')

diff --git a/expt_220802.cpp b/expt_220802.cpp
new file mode 100644
index 0000000..094da65
--- /dev/null
+++ b/expt_220802.cpp
@@ -0,0 +1,76 @@
+// Experimental content: Test sort algorithm
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <iostream>
+#include <vector>
+
+std::vector<std::vector<int>> a;
+std::vector<int> result;
+constexpr size_t LENGTH = 1024;
+
+void calculate(int l, int r, int dep) {
+  if (l > r)
+    return;
+  int mid = (l + r) >> 1;
+  a[dep].push_back(mid + 1);
+  calculate(l, mid - 1, dep + 1);
+  calculate(mid + 1, r, dep + 1);
+}
+
+size_t calculate_location(size_t index) {
+  int step = (int)std::log2(++index) + 1;
+  auto location =
+      LENGTH / (1 << step) * ((index & ((1 << (step - 1)) - 1)) * 2 + 1);
+  return location ? location : LENGTH;
+}
+typedef int key_type;
+
+const key_type *cudaBinarySearch(key_type *const start, const key_type *end,
+                                 const key_type val) {
+  int step_limit = (int)std::log2(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 + -((*last_known_point - val) >> 31);
+    last_known_point = next_level_start + son;
+    printf("%d\n", *last_known_point);
+  }
+  return last_known_point;
+}
+
+int main() {
+  int n = LENGTH;
+
+  int c = 0;
+  for (int k = n; k; k >>= 1)
+    c++;
+  a.resize(c);
+  calculate(0, n - 1, 0);
+  for (auto &i : a) {
+    for (int &j : i) {
+      // cout << j << ' ';
+      result.push_back(j);
+    }
+  }
+
+  for (int i = 0; i < 32; i++) {
+    printf("%3d ", i);
+  }
+
+  puts("");
+
+  for (int i = 0; i < 32; i++) {
+    printf("%3d ", result[i]);
+    assert(calculate_location(i) == result[i]);
+  }
+  puts("");
+  cudaBinarySearch(&result[0], &*result.end(), 928);
+  return 0;
+}
-- 
cgit v1.3.1