LindaSummer commented on code in PR #3130:
URL: https://github.com/apache/kvrocks/pull/3130#discussion_r2485422691
##########
src/commands/cmd_tdigest.cc:
##########
@@ -180,39 +180,47 @@ class CommandTDigestRevRank : public Commander {
public:
Status Parse(const std::vector<std::string> &args) override {
key_name_ = args[1];
- inputs_.reserve(args.size() - 2);
- for (size_t i = 2; i < args.size(); i++) {
- auto value = ParseFloat(args[i]);
+
+ std::unordered_set<std::string> unique_inputs_set(args.begin() + 2,
args.end());
+ origin_inputs_.assign(args.begin() + 2, args.end());
+
+ unique_inputs_.reserve(unique_inputs_set.size());
+ size_t i = 0;
+ for (const auto &input : unique_inputs_set) {
+ auto value = ParseFloat(input);
if (!value) {
return {Status::RedisParseErr, errValueIsNotFloat};
}
- inputs_.push_back(*value);
+ unique_inputs_.push_back(*value);
+ unique_inputs_order_[input] = i++;
Review Comment:
```suggestion
unique_inputs_order_[input] = i;
++i;
```
Making the increment a newline would make the code better for reading.
##########
src/types/tdigest.h:
##########
@@ -150,3 +152,92 @@ inline StatusOr<double> TDigestQuantile(TD&& td, double q)
{
diff /= (lc.weight / 2 + rc.weight / 2);
return Lerp(lc.mean, rc.mean, diff);
}
+
+inline int DoubleCompare(double a, double b, double rel_eps = 1e-12, double
abs_eps = 1e-9) {
+ double diff = a - b;
+ double adiff = std::abs(diff);
+ if (adiff <= abs_eps) return 0;
+ double maxab = std::max(std::abs(a), std::abs(b));
+ if (adiff <= maxab * rel_eps) return 0;
+ return (diff < 0) ? -1 : 1;
+}
+
+inline bool DoubleEqual(double a, double b, double rel_eps = 1e-12, double
abs_eps = 1e-9) {
+ return DoubleCompare(a, b, rel_eps, abs_eps) == 0;
+}
+
+struct DoubleComparator {
+ bool operator()(const double& a, const double& b) const { return
DoubleCompare(a, b) == -1; }
+};
+
+template <typename TD>
+inline Status TDigestRevRank(TD&& td, const std::vector<double>& inputs,
std::vector<int>& result) {
+ std::map<double, size_t, DoubleComparator> value_to_indices;
+ for (size_t i = 0; i < inputs.size(); ++i) {
+ value_to_indices[inputs[i]] = i;
+ }
+
+ result.clear();
+ result.resize(inputs.size(), -2);
+ auto it = value_to_indices.rbegin();
+
+ // handle inputs larger than maximum
+ while (it != value_to_indices.rend() && it->first > td.Max()) {
+ result[it->second] = -1;
+ ++it;
+ }
+
+ auto iter = td.End();
+ double cumulative_weight = 0;
+ while (iter->Valid() && it != value_to_indices.rend()) {
+ auto centroid = GET_OR_RET(iter->GetCentroid());
+ auto input_value = it->first;
+ if (DoubleEqual(centroid.mean, input_value)) {
+ auto current_mean = centroid.mean;
+ auto current_mean_cumulative_weight = cumulative_weight +
centroid.weight / 2;
+ cumulative_weight += centroid.weight;
+
+ // handle all the prev centroids which has the same mean
+ while (!iter->IsBegin() && iter->Prev()) {
+ auto next_centroid = GET_OR_RET(iter->GetCentroid());
+ if (!DoubleEqual(current_mean, next_centroid.mean)) {
+ // move back to the last equal centroid, because we will process it
in the next loop
+ iter->Next();
+ break;
+ }
+ current_mean_cumulative_weight += next_centroid.weight / 2;
+ cumulative_weight += next_centroid.weight;
+ }
+
+ // handle the prev inputs which has the same value
+ result[it->second] = static_cast<int>(current_mean_cumulative_weight);
+ ++it;
+ if (iter->IsBegin()) {
+ break;
+ }
+ iter->Prev();
+ } else if (DoubleCompare(centroid.mean, input_value) > 0) {
+ cumulative_weight += centroid.weight;
+ if (iter->IsBegin()) {
+ break;
+ }
+ iter->Prev();
+ } else {
+ result[it->second] = static_cast<int>(cumulative_weight);
+ ++it;
+ }
+ }
+
+ // handle inputs less than minimum
+ while (it != value_to_indices.rend()) {
+ result[it->second] = static_cast<int>(td.TotalWeight());
+ ++it;
+ }
+
+ for (auto r : result) {
+ if (r < -2) {
Review Comment:
```suggestion
if (r <= -2) {
```
When the centroids are not empty, no revrank should be `-2`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
