1 // Copyright 2023 gRPC authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include <string>
16 #include <utility>
17 #include <vector>
18
19 #include "fuzztest/fuzztest.h"
20 #include "gtest/gtest.h"
21 #include "src/core/util/tdigest.h"
22
23 using fuzztest::InRange;
24 using fuzztest::VectorOf;
25
26 namespace grpc_core {
27
GetTrueQuantile(const std::vector<double> & samples,double quantile)28 double GetTrueQuantile(const std::vector<double>& samples, double quantile) {
29 std::vector<double> s = samples;
30 double true_idx = static_cast<double>(s.size()) * quantile - 1;
31 double idx_left = std::floor(true_idx);
32 if (idx_left < 0.0) return 0.0;
33 double idx_right = std::ceil(true_idx);
34
35 std::sort(s.begin(), s.end());
36 if (idx_left == idx_right) {
37 return s[idx_left];
38 }
39 return s[idx_left] * (idx_right - true_idx) +
40 s[idx_right] * (true_idx - idx_left);
41 }
42
QuantilesMatch(std::vector<double> values,double compression,double quantile)43 void QuantilesMatch(std::vector<double> values, double compression,
44 double quantile) {
45 TDigest digest(compression);
46 for (auto value : values) {
47 digest.Add(value);
48 }
49 EXPECT_NEAR(digest.Quantile(quantile), GetTrueQuantile(values, quantile),
50 1.0);
51 }
52 FUZZ_TEST(MyTestSuite, QuantilesMatch)
53 .WithDomains(VectorOf(InRange(0.0, 10.0)).WithMinSize(100),
54 InRange(20, 2000), InRange(0, 1));
55
56 } // namespace grpc_core
57