binary_data_histogram.cc 2.8 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/zucchini/binary_data_histogram.h"
  5. #include <algorithm>
  6. #include <cmath>
  7. #include <limits>
  8. #include "base/check_op.h"
  9. #include "base/format_macros.h"
  10. #include "base/strings/stringprintf.h"
  11. namespace zucchini {
  12. /******** OutlierDetector ********/
  13. OutlierDetector::OutlierDetector() = default;
  14. OutlierDetector::~OutlierDetector() = default;
  15. // For BinaryDataHistogram, |sample| is typically in interval [0, 1].
  16. void OutlierDetector::Add(double sample) {
  17. ++n_;
  18. sum_ += sample;
  19. sum_of_squares_ += sample * sample;
  20. }
  21. void OutlierDetector::Prepare() {
  22. if (n_ > 0) {
  23. mean_ = sum_ / n_;
  24. standard_deviation_ = ::sqrt((sum_of_squares_ - sum_ * mean_) /
  25. std::max(static_cast<size_t>(1), n_ - 1));
  26. }
  27. }
  28. std::string OutlierDetector::RenderStats() {
  29. return base::StringPrintf("Mean = %.5f, StdDev = %.5f over %" PRIuS
  30. " samples",
  31. mean_, standard_deviation_, n_);
  32. }
  33. // Constants are chosen for BinaryDataHistogram, where |sample| is typically in
  34. // [0, 1].
  35. int OutlierDetector::DecideOutlier(double sample) {
  36. // Lower bound to avoid divide-by-zero and penalizing tight clusters.
  37. constexpr double kMinTolerance = 0.1;
  38. // Number of standard deviations away from mean for value to become outlier.
  39. constexpr double kSigmaBound = 1.9;
  40. if (n_ <= 1)
  41. return 0;
  42. double tolerance = std::max(kMinTolerance, standard_deviation_);
  43. double num_sigma = (sample - mean_) / tolerance;
  44. return num_sigma > kSigmaBound ? 1 : num_sigma < -kSigmaBound ? -1 : 0;
  45. }
  46. /******** BinaryDataHistogram ********/
  47. BinaryDataHistogram::BinaryDataHistogram() = default;
  48. BinaryDataHistogram::~BinaryDataHistogram() = default;
  49. bool BinaryDataHistogram::Compute(ConstBufferView region) {
  50. DCHECK(!histogram_);
  51. // Binary data with size < 2 are invalid.
  52. if (region.size() < sizeof(uint16_t))
  53. return false;
  54. DCHECK_LE(region.size(),
  55. static_cast<size_t>(std::numeric_limits<int32_t>::max()));
  56. histogram_ = std::make_unique<int32_t[]>(kNumBins);
  57. size_ = region.size();
  58. // Number of 2-byte intervals fully contained in |region|.
  59. size_t bound = size_ - sizeof(uint16_t) + 1;
  60. for (size_t i = 0; i < bound; ++i)
  61. ++histogram_[region.read<uint16_t>(i)];
  62. return true;
  63. }
  64. double BinaryDataHistogram::Distance(const BinaryDataHistogram& other) const {
  65. DCHECK(IsValid() && other.IsValid());
  66. // Compute Manhattan (L1) distance between respective histograms.
  67. double total_diff = 0;
  68. for (int i = 0; i < kNumBins; ++i)
  69. total_diff += std::abs(histogram_[i] - other.histogram_[i]);
  70. // Normalize by total size, so result lies in [0, 1].
  71. return total_diff / (size_ + other.size_);
  72. }
  73. } // namespace zucchini