Function TestRandom

cpp/src/arrow/util/tdigest_test.cc:97–143

}

void TestRandom(size_t size) {
  const std::vector<double> fixed_quantiles = {0, 0.01, 0.1, 0.2, 0.5, 0.8, 0.9, 0.99, 1};

  // append random quantiles to test
  std::vector<double> quantiles;
  random_real(50, 0x11223344, 0.0, 1.0, &quantiles);
  quantiles.insert(quantiles.end(), fixed_quantiles.cbegin(), fixed_quantiles.cend());

  // generate random test values
  const double min = 1e3, max = 1e10;
  std::vector<double> values;
  random_real(size, 0x11223344, min, max, &values);

  TDigest td(200);
  for (double value : values) {
    td.Add(value);
  }
  ASSERT_OK(td.Validate());

  const std::vector<double> expected = ExactQuantile(values, quantiles);
  std::vector<double> approximated;
  for (auto q : quantiles) {
    approximated.push_back(td.Quantile(q));
  }

  // r-square of expected and approximated quantiles should be greater than 0.999
  const double expected_mean =
      std::accumulate(expected.begin(), expected.end(), 0.0) / expected.size();
  double rss = 0, tss = 0;
  for (size_t i = 0; i < quantiles.size(); ++i) {
    rss += (expected[i] - approximated[i]) * (expected[i] - approximated[i]);
    tss += (expected[i] - expected_mean) * (expected[i] - expected_mean);
  }
  const double r2 = 1 - rss / tss;
  EXPECT_GT(r2, 0.999);

  // make sure no quantile drifts too much from the truth
#ifdef _TDIGEST_STRICT_TEST
  const double error_ratio = 0.02;
#else
  const double error_ratio = 0.05;
#endif
  for (size_t i = 0; i < quantiles.size(); ++i) {
    const double tolerance = std::fabs(expected[i]) * error_ratio;
    EXPECT_NEAR(approximated[i], expected[i], tolerance) << quantiles[i];
  }
}

TEST(TDigestTest, RandomValues) { TestRandom(100000); }