<commit_before>#include <iostream>
#include <random>
#include <algorithm>
#include "qdigest.h"

void compare_percentiles(double p,
                         std::vector<int> const &v,
                         qdigest::QDigest const &digest) {
  int ip = (p * 1000 + 9) / 10;
  std::cerr << ip << "th percentile: " << v.at(p * v.size() - 1)
            << " v/s " << digest.percentile(p) << "\n";
}

void test_poisson_distribution(int n, int k, int seed) {
  std::cerr << "<< test_poisson_distribution >>\n";
  std::vector<int> v;
  int number = 1;
  int repeat = 1;
  for (; v.size() != n; ++number) {
    for (int i = 0; i < repeat && v.size() != n; ++i) {
      v.push_back(number);
    }
    // std::cerr << "number: " << number << ", repeat: " << repeat << "\n";
    if (v.size() < n/2) {
      repeat *= 2;
    } else if (v.size() == n/2) {
      // do nothing
    } else {
      repeat /= 2;
    }
    if (!repeat) repeat = 2;
  }

  auto w = v;
  std::sort(v.begin(), v.end());
  std::random_shuffle(w.begin(), w.end());

  qdigest::QDigest digest(k);
  for (size_t i = 0; i < w.size(); ++i) {
    digest.insert(w[i], 1);
  }

  std::cerr << "# nodes: " << digest.size() << "\n"
            << "Compression Ratio: " << digest.compression_ratio() << "\n";

  compare_percentiles(0.01, v, digest);
  compare_percentiles(0.02, v, digest);
  compare_percentiles(0.03, v, digest);
  for (double d = 0.05; d < 1.0; d += 0.05) {
    compare_percentiles(d, v, digest);
  }
}

void test_geometric_distribution(int n, int k, int seed) {
  std::cerr << "<< test_geometric_distribution >>\n";
  std::vector<int> v;
  int number = 1;
  int repeat = 1;
  for (; v.size() != n; number += 1, repeat *= 2) {
    for (int i = 0; i < repeat && v.size() != n; ++i) {
      v.push_back(number);
    }
  }
  auto w = v;
  std::random_shuffle(w.begin(), w.end());

  qdigest::QDigest digest(k);
  for (size_t i = 0; i < w.size(); ++i) {
    digest.insert(w[i], 1);
  }

  std::cerr << "# nodes: " << digest.size() << "\n"
            << "Compression Ratio: " << digest.compression_ratio() << "\n";

  compare_percentiles(0.01, v, digest);
  compare_percentiles(0.02, v, digest);
  compare_percentiles(0.03, v, digest);
  for (double d = 0.05; d < 1.0; d += 0.05) {
    compare_percentiles(d, v, digest);
  }
}

void test_random_distribution(int n, int k, int seed) {
  std::cerr << "<< test_random_distribution >>\n";
  srand(seed);
  qdigest::QDigest digest(k);
  std::vector<int> v;

  for (int i = 0; i < n; ++i) {
    auto number = rand() % n;
    v.push_back(number);
    digest.insert(number, 1);
  }
  std::cerr << "# nodes: " << digest.size() << "\n"
            << "Compression Ratio: " << digest.compression_ratio() << "\n";

  std::sort(v.begin(), v.end());

  for (double d = 0.05; d < 1.0; d += 0.05) {
    compare_percentiles(d, v, digest);
  }
}

int main() {
  const int K = 100;
  int seed = 377;
  int N = 20000;

  test_random_distribution(N, K, seed);
  std::cerr << std::endl;
  test_geometric_distribution(N, K, seed);
  std::cerr << std::endl;
  N = 65535;
  test_poisson_distribution(N, K, seed);<commit_msg>Update poisson distribution, and use N=65535 inserts for every test.<commit_after>#include <iostream>
#include <random>
#include <algorithm>
#include "qdigest.h"

void compare_percentiles(double p,
                         std::vector<int> const &v,
                         qdigest::QDigest const &digest) {
  int ip = (p * 1000 + 9) / 10;
  std::cerr << ip << "th percentile: " << v.at(p * v.size() - 1)
            << " v/s " << digest.percentile(p) << "\n";
}

void test_poisson_distribution(int n, int k, int seed) {
  std::cerr << "<< test_poisson_distribution >>\n";
  std::vector<int> v;
  int number = 1;
  int repeat = 1;
  bool flipped = false;
  for (; v.size() != n; ++number) {
    for (int i = 0; i < repeat && v.size() != n; ++i) {
      v.push_back(number);
    }
    // std::cerr << "number: " << number << ", repeat: " << repeat << "\n";
    // std::cerr << v.size() << "\n";
    if (v.size() <= n/2) {
      if (!flipped) repeat += 3;
    } else {
      if (!flipped) repeat += 3;
      flipped = true;
      repeat -= 3;
    }
    if (repeat < 1) repeat = 2;
  }

  auto w = v;
  std::sort(v.begin(), v.end());
  std::random_shuffle(w.begin(), w.end());

  qdigest::QDigest digest(k);
  for (size_t i = 0; i < w.size(); ++i) {
    digest.insert(w[i], 1);
  }

  std::cerr << "# nodes: " << digest.size() << "\n"
            << "Compression Ratio: " << digest.compression_ratio() << "\n";

  compare_percentiles(0.01, v, digest);
  compare_percentiles(0.02, v, digest);
  compare_percentiles(0.03, v, digest);
  for (double d = 0.05; d < 1.0; d += 0.05) {
    compare_percentiles(d, v, digest);
  }
}

void test_geometric_distribution(int n, int k, int seed) {
  std::cerr << "<< test_geometric_distribution >>\n";
  std::vector<int> v;
  int number = 1;
  int repeat = 1;
  for (; v.size() != n; number += 1, repeat *= 2) {
    for (int i = 0; i < repeat && v.size() != n; ++i) {
      v.push_back(number);
    }
  }
  auto w = v;
  std::random_shuffle(w.begin(), w.end());

  qdigest::QDigest digest(k);
  for (size_t i = 0; i < w.size(); ++i) {
    digest.insert(w[i], 1);
  }

  std::cerr << "# nodes: " << digest.size() << "\n"
            << "Compression Ratio: " << digest.compression_ratio() << "\n";

  compare_percentiles(0.01, v, digest);
  compare_percentiles(0.02, v, digest);
  compare_percentiles(0.03, v, digest);
  for (double d = 0.05; d < 1.0; d += 0.05) {
    compare_percentiles(d, v, digest);
  }
}

void test_random_distribution(int n, int k, int seed) {
  std::cerr << "<< test_random_distribution >>\n";
  srand(seed);
  qdigest::QDigest digest(k);
  std::vector<int> v;

  for (int i = 0; i < n; ++i) {
    auto number = rand() % n;
    v.push_back(number);
    digest.insert(number, 1);
  }
  std::cerr << "# nodes: " << digest.size() << "\n"
            << "Compression Ratio: " << digest.compression_ratio() << "\n";

  std::sort(v.begin(), v.end());

  for (double d = 0.05; d < 1.0; d += 0.05) {
    compare_percentiles(d, v, digest);
  }
}

int main() {
  const int K = 100;
  int seed = 377;
  int N = 65535;

  test_random_distribution(N, K, seed);
  std::cerr << std::endl;
  test_geometric_distribution(N, K, seed);
  std::cerr << std::endl;
  test_poisson_distribution(N, K, seed);
{'fraction_non_alphanumeric': 0.20588698252793955, 'fraction_numerical': 0.026916417440579255, 'mean_word_length': 2.782142857142857, 'pattern_counts': {'":': 0, '<': 188, '<?xml version=': 0, '>': 29, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2153828', 'n_tokens_mistral': 2619, 'n_tokens_neox': 2424, 'n_words': 597}