Function Median

tensorflow/core/grappler/costs/robust_stats.cc:37–57

Given a vector of values (sorted or not), calculate the median.

// Given a vector of values (sorted or not), calculate the median.
static double Median(std::vector<double> &&values) {
  const size_t n = values.size();
  if (n == 0) return 0;
  const auto middle = values.begin() + (n / 2);
  // Put the middle value in its place.
  std::nth_element(values.begin(), middle, values.end());
  if (n & 1) {
    return *middle;
  }
  // Return the average of the two elements, the max_element lower than
  // *middle is found between begin and middle as a post-cond of
  // nth_element.
  const auto lower_middle = std::max_element(values.begin(), middle);
  // Preventing overflow. We know that '*lower_middle <= *middle'.
  // If both are on opposite sides of zero, the sum won't overflow, otherwise
  // the difference won't overflow.
  if (*lower_middle <= 0 && *middle >= 0) {
    return (*lower_middle + *middle) / 2;
  }
  return *lower_middle + (*middle - *lower_middle) / 2;
}

// Given a set of values, calculates the scaled Median Absolute Deviation (a
// robust approximation to the standard deviation).  This is calculated as the