From 0b2735596e8969c08797f18977c626f423b3ab6d Mon Sep 17 00:00:00 2001
From: KunoiSayami <i@leanhe.dev>
Date: Thu, 30 Jun 2022 02:20:09 +0800
Subject: refactor(script): Optimize cdf calculator

Signed-off-by: KunoiSayami <i@leanhe.dev>
---
 main.cu | 33 ++++++++++++++++++++++++++++++---
 1 file changed, 30 insertions(+), 3 deletions(-)

(limited to 'main.cu')

diff --git a/main.cu b/main.cu
index 1d0cc4e..898df07 100644
--- a/main.cu
+++ b/main.cu
@@ -69,6 +69,7 @@ Conference on Parallel and Distributed Systems, December 2012.
 #include <cstdio>
 #include <cstdlib>
 #include <random>
+#include <set>
 
 #if __WORDSIZE == 64
 typedef unsigned long long LL;
@@ -601,9 +602,6 @@ LL RandomLevel(std::mt19937 &randomEngine, double p) {
 }
 
 std::vector<LL> storage;
-#ifdef MEASURE_TIME
-std::vector<int> SpendTimeVec;
-#endif
 
 unsigned trailing_zeroes(size_t index) {
   unsigned bits = 0;
@@ -648,6 +646,35 @@ __global__ void copy_function(int *spend_time) {
   memcpy(spend_time, l->spend_time, sizeof(int) * NUM_ITEMS);
 }
 
+std::vector<double> population;
+std::vector<double> sample;
+
+void initialize(const std::vector<double> &input_population,
+                const std::vector<double> &input_sample) {
+  population = input_population;
+  std::sort(population.begin(), population.end());
+  sample = input_sample;
+  std::sort(sample.begin(), sample.end());
+}
+
+double sample_cdf(double x) {
+  auto it = lower_bound(sample.begin(), sample.end(), x);
+  if (it == sample.end()) {
+    return 1;
+  }
+  if (it == sample.begin()) {
+    return 0;
+  }
+  auto it_prev = it - 1;
+  return (double(it_prev - sample.begin()) +
+          double(x - *it_prev) / (*it - *it_prev)) /
+         double(sample.size() - 1);
+}
+
+int infer_offset(double x) {
+  return int(sample_cdf(x) * double(population.size()));
+}
+
 int main(int argc, char **argv) {
   if (argc != 3) {
     printf("Need two arguments: percent add ops and percent delete ops (e.g., "
-- 
cgit v1.3.1