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_220726.cpp | 126 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 126 insertions(+)
 create mode 100644 expt_220726.cpp

(limited to 'expt_220726.cpp')

diff --git a/expt_220726.cpp b/expt_220726.cpp
new file mode 100644
index 0000000..397bc90
--- /dev/null
+++ b/expt_220726.cpp
@@ -0,0 +1,126 @@
+#include <algorithm>
+#include <cassert>
+#include <chrono>
+#include <cmath>
+#include <cstdio>
+#include <iostream>
+#include <vector>
+
+constexpr size_t length = 2097152;
+std::vector<unsigned long long> population_vector, sample_vector,
+    original_vector;
+// std::vector<std::vector<unsigned long long>> result_storage;
+std::vector<bool> result_storage;
+
+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);
+}
+
+inline long double safe_ceil(long double value) {
+  auto c = std::ceil(value);
+  return c == 0 ? 1 : c;
+}
+
+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);
+}
+
+constexpr long sample_length = 1024;
+constexpr long test_size = 1000000;
+
+void mian(long scale_size) {
+  const long split_size = test_size * scale_size;
+  result_storage.clear();
+  result_storage.resize(split_size, false);
+
+  const auto slice_size = 1.0 / (double)(split_size);
+
+  for (long i = 0; i < test_size; i++) {
+    auto index = (int)safe_ceil(sample_cdf(original_vector[i + sample_length]) /
+                                slice_size) -
+                 1;
+    // printf("%Lf\n", index);
+    if (result_storage[index]) {
+      while (result_storage[++index]) {
+        assert(index < split_size);
+      }
+    }
+    result_storage[index] = true;
+  }
+}
+
+int main(int _argc, char const *_argv[]) {
+  assert((length & 1) == 0);
+  assert(length > 1024);
+
+  FILE *file = fopen("normal_distribution.txt", "r");
+  assert(file);
+  for (long long i; fscanf(file, "%lld ", &i) != EOF; store_into_vector(i))
+    ;
+  fclose(file);
+
+  assert(population_vector.size() == length);
+
+  original_vector = population_vector;
+
+  sample_vector = std::vector<unsigned long long>(
+      original_vector.begin(), original_vector.begin() + sample_length);
+  sample_vector.push_back(min_value);
+  sample_vector.push_back(max_value);
+
+  std::sort(sample_vector.begin(), sample_vector.end());
+
+  for (int i = 2; i <= 16; i++) {
+
+    auto start = std::chrono::high_resolution_clock::now();
+    mian(i);
+    auto end = std::chrono::high_resolution_clock::now();
+
+    auto element_size_max = 0;
+    for (auto element : result_storage) {
+      if (element_size_max < element) {
+        element_size_max = element;
+      }
+    }
+    assert(element_size_max == 1);
+    printf("scale: %d, time spend: %ldms\n", i,
+           std::chrono::duration_cast<std::chrono::microseconds>(end - start)
+               .count());
+  }
+}
+/*
+ * Sample output:
+scale: 2, time spend: 6749258ms
+scale: 3, time spend: 1721671ms
+scale: 4, time spend: 611112ms
+scale: 5, time spend: 353036ms
+scale: 6, time spend: 266654ms
+scale: 7, time spend: 267346ms
+scale: 8, time spend: 267377ms
+scale: 9, time spend: 260396ms
+scale: 10, time spend: 267724ms
+scale: 11, time spend: 263023ms
+scale: 12, time spend: 270249ms
+scale: 13, time spend: 265440ms
+scale: 14, time spend: 266876ms
+scale: 15, time spend: 270683ms
+scale: 16, time spend: 273216ms
+ */
\ No newline at end of file
-- 
cgit v1.3.1