From 813049a3ff85b18bc1ca6f640c7677c8bbf39414 Mon Sep 17 00:00:00 2001
From: KunoiSayami <i@leanhe.dev>
Date: Sun, 18 Jun 2023 21:26:01 +0800
Subject: feat(exp): Add more test for level

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

(limited to 'expt_0618_3.cu')

diff --git a/expt_0618_3.cu b/expt_0618_3.cu
new file mode 100644
index 0000000..4558f54
--- /dev/null
+++ b/expt_0618_3.cu
@@ -0,0 +1,117 @@
+// Experimental content: Print level by cdf
+
+#include "sortlib.cuh"
+#define READ_NO_OUTPUT
+#include "read_helper_p.h"
+#include <random>
+
+long pow_for_sample(long n) {
+  auto x = 2;
+  for (int i = 1; i < n; i++) {
+    x *= 2;
+  }
+  return x - 1;
+}
+constexpr size_t MAX_LEVEL = 32;
+constexpr auto RESULT_LENGTH = MAX_LEVEL + 3;
+
+static unsigned trailing_zeroes(size_t index) {
+  constexpr auto block_size = 2;
+  unsigned bits = 0;
+  auto x = index / block_size;
+
+  if (x) {
+    while (x % block_size == 0) {
+      ++bits;
+      x /= block_size;
+    }
+  }
+  return bits;
+}
+
+inline double calcSliceSize(size_t insertion_size) {
+  return 1.0 / (double)insertion_size;
+}
+
+void generateRandomLevel(std::vector<unsigned int> &v, long run_times) {
+  // auto levels = new int[size];
+  std::random_device randomDevice;
+  std::mt19937 randomEngine(randomDevice());
+  std::geometric_distribution<> distribution(0.5);
+  for (int i = 0; i < run_times; i++) {
+    v[(int)std::min(MAX_LEVEL, (size_t)distribution(randomEngine))]++;
+  }
+}
+
+void multiple_generate(std::vector<unsigned int> &v, long run_times,
+                       const int outer_times = 10) {
+  std::vector<std::vector<unsigned int>> results(outer_times);
+  std::random_device randomDevice;
+  std::mt19937 randomEngine(randomDevice());
+  std::geometric_distribution<> distribution(0.5);
+  for (int x = 0; x < outer_times; x++) {
+    results[x].resize(RESULT_LENGTH, 0);
+    for (int i = 0; i < run_times; i++) {
+      results[x]
+             [(int)std::min(MAX_LEVEL, (size_t)distribution(randomEngine))]++;
+    }
+  }
+  for (int level = 0; level < MAX_LEVEL; level++) {
+    auto sum = 0L;
+    for (int i = 0; i < outer_times; i++) {
+      sum += results[i][level];
+    }
+    v[level] = sum / outer_times;
+  }
+}
+
+int main(int argc, char const *argv[]) {
+
+  auto multiple_times = 0L;
+  if (argc < 3) {
+    printf("Usage %s [sample(pow)] [population]\n", argv[0]);
+    return 1;
+  }
+
+  if (argc == 4) {
+    multiple_times = strtol(argv[3], nullptr, 10);
+    printf("multiple_times defined: %ld\n", multiple_times);
+  }
+
+  auto sample_length = pow_for_sample(strtol(argv[1], nullptr, 10));
+  auto population_length = strtol(argv[2], nullptr, 10);
+
+  printf("sample length: %ld, population length: %ld\n", sample_length,
+         population_length);
+
+  ReadHelper<key_type> readHelper("normal_distribution.txt", sample_length, 0);
+  readHelper.readFile();
+
+  std::vector<key_type> sample, population;
+  std::vector<unsigned int> result(RESULT_LENGTH), result2(RESULT_LENGTH);
+  readHelper.split_into(sample, population);
+  rebuildSort(sample);
+
+  auto scale_size = calcSliceSize(population_length);
+
+  auto sort = CustomSort(sample_length, sizeof(key_type) * 8);
+
+  for (auto element : readHelper.population_vector) {
+    auto ret = sort.sample_cdf_custom_version(sample.data(), element);
+    auto cdf_index = ret / scale_size;
+    auto index = trailing_zeroes((size_t)cdf_index);
+    result[index]++;
+  }
+
+  if (!multiple_times)
+    generateRandomLevel(result2, population_length);
+  else
+    multiple_generate(result2, population_length);
+
+  for (int i = 0; i < 32; i++) {
+    if (!result[i] && !result2[i]) {
+      continue;
+    }
+    printf("%d: %d %d\n", i, result[i], result2[i]);
+  }
+}
-- 
cgit v1.3.1