feat(exp): Use sample to calculate cdf

Signed-off-by: KunoiSayami <[email protected]>

1 files changed, 45 insertions, 10 deletions

diff --git a/exp_0702.cpp b/exp_0702.cpp
index 1c74d0a..c767afd 100644
--- a/exp_0702.cpp
+++ b/exp_0702.cpp
@@ -5,30 +5,65 @@
 #include <vector>
 
 constexpr size_t length = 1048576;
-std::vector<unsigned long long> original_vector;
+constexpr size_t sample_length = 1024;
+constexpr long double slice_size = 1.0 / sample_length;
+std::vector<unsigned long long> population_vector, sample_vector;
+std::vector<std::vector<unsigned long long>> result_storage;
 
-long double finite_population_cdf(long double x) {
-  auto it = upper_bound(original_vector.begin(), original_vector.end(), x);
-  return (long double)(it - original_vector.begin()) / original_vector.size();
+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 main() {
+inline long double safe_ceil(long double value) {
+  auto c = std::ceil(value);
+  return c == 0 ? 1 : c;
+}
 
+int main() {
   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;
-       original_vector.push_back(i))
+       population_vector.push_back(i))
     ;
   fclose(file);
 
-  assert(original_vector.size() == length);
+  assert(population_vector.size() == length);
 
-  std::sort(original_vector.begin(), original_vector.end());
+  std::vector<unsigned long long> original_vector(population_vector);
 
-  for (int i = length / 1024 - 1; i < length; i += (length / 1024)) {
-    printf("%Lf\n", finite_population_cdf(original_vector[i]));
+  sample_vector = std::vector<unsigned long long>(
+      population_vector.begin(), population_vector.begin() + sample_length);
+
+  result_storage.resize(sample_length, std::vector<unsigned long long>());
+
+  std::sort(population_vector.begin(), population_vector.end());
+  sample_vector.push_back(population_vector[0]);
+  sample_vector.push_back(*(population_vector.cend() - 1));
+  std::sort(sample_vector.begin(), sample_vector.end());
+
+  for (auto &element : original_vector) {
+    result_storage[(int)safe_ceil(sample_cdf(element) / slice_size) - 1]
+        .push_back(element);
+    /*auto tmp = sample_cdf(element) / slice_size;
+    if (tmp < 1) {
+      printf("%lld %Lf ", element, tmp);
+    }*/
+  }
+  for (const auto &element : result_storage) {
+    printf("%ld ", element.size());
   }
+  puts("");
 }
\ No newline at end of file