<commit_before>// Copyright 2016 <NAME>. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Source project : https://github.com/ismaelJimenez/cpp.leastsq
// Adapted to be used with google benchmark

#include "benchmark/benchmark.h"

#include <algorithm>
#include <cmath>
#include "check.h"
#include "complexity.h"

namespace benchmark {

// Internal function to calculate the different scalability forms
BigOFunc* FittingCurve(BigO complexity) {
  static const double kLog2E = 1.44269504088896340736;
  switch (complexity) {
    case oN:
      return [](int64_t n) -> double { return static_cast<double>(n); };
    case oNSquared:
      return [](int64_t n) -> double { return std::pow(n, 2); };
    case oNCubed:
      return [](int64_t n) -> double { return std::pow(n, 3); };
    case oLogN:
      /* Note: can't use log2 because Android's GNU STL lacks it */
      return [](int64_t n) { return kLog2E * log(static_cast<double>(n)); };
    case oNLogN:
      /* Note: can't use log2 because Android's GNU STL lacks it */
      return [](int64_t n) { return kLog2E * n * log(static_cast<double>(n)); };
    case o1:
    default:
      return [](int64_t) { return 1.0; };
  }
}

// Function to return an string for the calculated complexity
std::string GetBigOString(BigO complexity) {
  switch (complexity) {
    case oN:
      return "N";
    case oNSquared:
      return "N^2";
    case oNCubed:
      return "N^3";
    case oLogN:
      return "lgN";
    case oNLogN:
      return "NlgN";
    case o1:
      return "(1)";
    default:
      return "f(N)";
  }
}

// Find the coefficient for the high-order term in the running time, by
// minimizing the sum of squares of relative error, for the fitting curve
// given by the lambda expression.
//   - n             : Vector containing the size of the benchmark tests.
//   - time          : Vector containing the times for the benchmark tests.
//   - fitting_curve : lambda expression (e.g. [](int64_t n) {return n; };).

// For a deeper explanation on the algorithm logic, look the README file at
// http://github.com/ismaelJimenez/Minimal-Cpp-Least-Squared-Fit

LeastSq MinimalLeastSq(const std::vector<int64_t>& n,
                       const std::vector<double>& time,
                       BigOFunc* fitting_curve) {
  double sigma_gn = 0.0;
  double sigma_gn_squared = 0.0;
  double sigma_time = 0.0;<commit_msg>Update reference to complexity calculation (#723)<commit_after>// Copyright 2016 <NAME>. All rights reserved.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

// Source project : https://github.com/ismaelJimenez/cpp.leastsq
// Adapted to be used with google benchmark

#include "benchmark/benchmark.h"

#include <algorithm>
#include <cmath>
#include "check.h"
#include "complexity.h"

namespace benchmark {

// Internal function to calculate the different scalability forms
BigOFunc* FittingCurve(BigO complexity) {
  static const double kLog2E = 1.44269504088896340736;
  switch (complexity) {
    case oN:
      return [](int64_t n) -> double { return static_cast<double>(n); };
    case oNSquared:
      return [](int64_t n) -> double { return std::pow(n, 2); };
    case oNCubed:
      return [](int64_t n) -> double { return std::pow(n, 3); };
    case oLogN:
      /* Note: can't use log2 because Android's GNU STL lacks it */
      return [](int64_t n) { return kLog2E * log(static_cast<double>(n)); };
    case oNLogN:
      /* Note: can't use log2 because Android's GNU STL lacks it */
      return [](int64_t n) { return kLog2E * n * log(static_cast<double>(n)); };
    case o1:
    default:
      return [](int64_t) { return 1.0; };
  }
}

// Function to return an string for the calculated complexity
std::string GetBigOString(BigO complexity) {
  switch (complexity) {
    case oN:
      return "N";
    case oNSquared:
      return "N^2";
    case oNCubed:
      return "N^3";
    case oLogN:
      return "lgN";
    case oNLogN:
      return "NlgN";
    case o1:
      return "(1)";
    default:
      return "f(N)";
  }
}

// Find the coefficient for the high-order term in the running time, by
// minimizing the sum of squares of relative error, for the fitting curve
// given by the lambda expression.
//   - n             : Vector containing the size of the benchmark tests.
//   - time          : Vector containing the times for the benchmark tests.
//   - fitting_curve : lambda expression (e.g. [](int64_t n) {return n; };).

// For a deeper explanation on the algorithm logic, please refer to
// https://en.wikipedia.org/wiki/Least_squares#Least_squares,_regression_analysis_and_statistics

LeastSq MinimalLeastSq(const std::vector<int64_t>& n,
                       const std::vector<double>& time,
                       BigOFunc* fitting_curve) {
  double sigma_gn = 0.0;
  double sigma_gn_squared = 0.0;
  double sigma_time = 0.0;
{'fraction_non_alphanumeric': 0.11300204220558203, 'fraction_numerical': 0.022634445200816884, 'mean_word_length': 2.9522528581035643, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 25, 'https://': 3, 'lorem ipsum': 0, 'www.': 2, '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': '6672873', 'n_tokens_mistral': 1914, 'n_tokens_neox': 1796, 'n_words': 648}