From 3c745606e9494917763313e821e3722d010e2e97 Mon Sep 17 00:00:00 2001
From: KunoiSayami <i@leanhe.dev>
Date: Fri, 22 Jul 2022 16:40:36 +0800
Subject: refactor: Rename files

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

(limited to 'expt_3.cpp')

diff --git a/expt_3.cpp b/expt_3.cpp
new file mode 100644
index 0000000..f8ed1e7
--- /dev/null
+++ b/expt_3.cpp
@@ -0,0 +1,142 @@
+#include <algorithm>
+#include <cassert>
+#include <cmath>
+#include <cstdio>
+#include <set>
+#include <vector>
+
+constexpr size_t length = 1048576;
+constexpr size_t sample_length = 1000;
+
+#define CALC_HEIGHT
+//#define CALC_CDF_DIFF
+//#define INSERT_LIMIT_VALUE
+
+#ifdef CALC_HEIGHT
+constexpr int block_size = 2;
+unsigned trailing_zeroes(size_t index) {
+  unsigned bits = 0;
+  unsigned x = index;
+
+  if (x) {
+    while (x % block_size == 0) {
+      ++bits;
+      x /= block_size;
+    }
+  }
+  return bits;
+}
+
+unsigned int getHeight(long loc) {
+  // if (loc % block_size == 0) {
+  auto level = trailing_zeroes(loc) + 1;
+  return level;
+  //}
+
+  // return 1;
+}
+#else
+unsigned int getHeight(long loc) { return loc; }
+#endif
+
+std::vector<long long> population_vector, sample_vector;
+
+void initialize(const std::vector<long long> &input_population,
+                const std::vector<long long> &input_sample) {
+  population_vector = input_population;
+  std::sort(population_vector.begin(), population_vector.end());
+  sample_vector = input_sample;
+  std::sort(sample_vector.begin(), sample_vector.end());
+#ifdef INSERT_LIMIT_VALUE
+  sample_vector.insert(sample_vector.cbegin(), *population_vector.begin());
+  sample_vector.push_back(*(population_vector.end() - 1));
+#endif
+}
+
+long double sample_cdf(long double x) {
+  auto it = 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);
+}
+
+int infer_offset(long double x) {
+  return (int)std::round(sample_cdf(x) * double(population_vector.size()));
+}
+#ifdef CALC_CDF_DIFF
+int infer_offset_from_cdf(long double cdf) {
+  return int(cdf * double(population_vector.size()));
+}
+
+// const double M_SQRT1_2 = sqrt(0.5);
+constexpr long long s_avg = 2147483648;
+constexpr long long s_stddev = 2147483648;
+
+long double goal_cdf(long double x) { return std::erfc(-x * M_SQRT1_2) * 0.5; }
+long double stat_cdf(long double x) { return goal_cdf((x - s_avg) / s_stddev); }
+
+long double finite_population_cdf(long double x) {
+  auto it = upper_bound(population_vector.begin(), population_vector.end(), x);
+  return (long double)(it - population_vector.begin()) /
+         population_vector.size();
+}
+#endif
+
+int main() {
+
+  std::vector<long long> original_vector;
+
+  std::set<long long> set2;
+
+  FILE *file = fopen("normal_distribution.txt", "r");
+  assert(file);
+  for (long long i; fscanf(file, "%lld ", &i) != EOF;
+       original_vector.push_back(i))
+    ;
+  fclose(file);
+
+  assert(original_vector.size() >= length);
+
+  auto it = original_vector.begin();
+  for (int i = 1; i <= sample_length; i++) {
+    auto element = *it;
+    auto ret = set2.insert(element);
+    if (ret.second) {
+      sample_vector.push_back(element);
+      // printf("%lld\n", element);
+    }
+    it++;
+  }
+
+  assert(sample_vector.size() == sample_length);
+
+  initialize(original_vector, sample_vector);
+
+  for (auto iter = population_vector.begin(); iter != population_vector.end();
+       iter++) {
+#ifdef CALC_CDF_DIFF
+    auto cdf = sample_cdf(*iter);
+    printf("%d,%d,%.6Lf ", getHeight(infer_offset_from_cdf(cdf)),
+           getHeight(iter - population_vector.begin()),
+           std::abs(cdf - stat_cdf(*iter)));
+#else
+    auto index = infer_offset(*iter);
+    printf("%d,%d,%d,%ld\n", getHeight(index), index,
+           getHeight(iter - population_vector.begin() + 1),
+           iter - population_vector.begin() + 1);
+#endif
+    // fflush(stdout);
+  }
+  // puts("");
+  //  printf("%lld, %lld\n", sample_vector[1], *(sample_vector.end() - 2));
+  //  printf("%lld, %lld\n", population_vector[0], *(population_vector.end() -
+  //  1));
+  return 0;
+}
\ No newline at end of file
-- 
cgit v1.3.1