Каков правильный подход при использовании контейнера STL для медианного расчета?

Ответ 1

Любой контейнер с произвольным доступом (например, std::vector) может быть отсортирован со стандартным алгоритмом std::sort, доступным в заголовке <algorithm>.

Для нахождения медианы было бы быстрее использовать std::nth_element; это делает достаточно, чтобы поместить один выбранный элемент в правильное положение, но не полностью сортирует контейнер. Таким образом, вы можете найти медиану следующим образом:

int median(vector<int> &v)
{
    size_t n = v.size() / 2;
    nth_element(v.begin(), v.begin()+n, v.end());
    return v[n];
}

Ответ 2

Медиана более сложна, чем ответ Майка Сеймура. Медиана отличается в зависимости от наличия четного или нечетного числа элементов в выборке. Если существует четное количество элементов, медиана является средним значением для средних двух предметов. Это означает, что медиана списка целых чисел может быть дробной. Наконец, медиана пустого списка undefined. Вот код, который передает мои основные тестовые примеры:

///Represents the exception for taking the median of an empty list
class median_of_empty_list_exception:public std::exception{
  virtual const char* what() const throw() {
    return "Attempt to take the median of an empty list of numbers.  "
      "The median of an empty list is undefined.";
  }
};

///Return the median of a sequence of numbers defined by the random
///access iterators begin and end.  The sequence must not be empty
///(median is undefined for an empty set).
///
///The numbers must be convertible to double.
template<class RandAccessIter>
double median(RandAccessIter begin, RandAccessIter end) 
  throw(median_of_empty_list_exception){
  if(begin == end){ throw median_of_empty_list_exception(); }
  std::size_t size = end - begin;
  std::size_t middleIdx = size/2;
  RandAccessIter target = begin + middleIdx;
  std::nth_element(begin, target, end);

  if(size % 2 != 0){ //Odd number of elements
    return *target;
  }else{            //Even number of elements
    double a = *target;
    RandAccessIter targetNeighbor= target-1;
    std::nth_element(begin, targetNeighbor, end);
    return (a+*targetNeighbor)/2.0;
  }
}

Ответ 3

Вот более полная версия Майка Сеймура:

// Could use pass by copy to avoid changing vector
double median(std::vector<int> &v)
{
  size_t n = v.size() / 2;
  std::nth_element(v.begin(), v.begin()+n, v.end());
  int vn = v[n];
  if(v.size()%2 == 1)
  {
    return vn;
  }else
  {
    std::nth_element(v.begin(), v.begin()+n-1, v.end());
    return 0.5*(vn+v[n-1]);
  }
}

Он обрабатывает ввод нечетной или четной длины.

Ответ 4

Этот алгоритм эффективно обрабатывает как четные, так и нечетные входы с использованием алгоритма STL nth_element (амортизированный O (N)) и алгоритма max_element (O (n)). Обратите внимание, что nth_element имеет еще один гарантированный побочный эффект, а именно, что все элементы до n гарантированно меньше v[n], просто не обязательно сортируются.

//post-condition: After returning, the elements in v may be reordered and the resulting order is implementation defined.
double median(vector<double> &v)
{
  if(v.empty()) {
    return 0.0;
  }
  auto n = v.size() / 2;
  nth_element(v.begin(), v.begin()+n, v.end());
  auto med = v[n];
  if(!(v.size() & 1)) { //If the set size is even
    auto max_it = max_element(v.begin(), v.begin()+n);
    med = (*max_it + med) / 2.0;
  }
  return med;    
}

Ответ 5

Вы можете отсортировать std::vector с помощью библиотечной функции std::sort.

std::vector<int> vec;
// ... fill vector with stuff
std::sort(vec.begin(), vec.end());

Ответ 6

собрав все идеи из этой темы, я закончил с этой рутиной. он работает с любым stl-контейнером или любым классом, предоставляющим итераторы ввода и обрабатывая контейнеры с нечетным и равным размером. Он также выполняет свою работу над копией контейнера, чтобы не изменять исходный контент.

template <typename T = double, typename C>
inline const T median(const C &the_container)
{
    std::vector<T> tmp_array(std::begin(the_container), 
                             std::end(the_container));
    size_t n = tmp_array.size() / 2;
    std::nth_element(tmp_array.begin(), tmp_array.begin() + n, tmp_array.end());

    if(tmp_array.size() % 2){ return tmp_array[n]; }
    else
    {
        // even sized vector -> average the two middle values
        auto max_it = std::max_element(tmp_array.begin(), tmp_array.begin() + n);
        return (*max_it + tmp_array[n]) / 2.0;
    }
}

Ответ 7

Существует алгоритм алгоритм выбора по линейному времени. Нижеприведенный код работает только тогда, когда в контейнере есть итератор с произвольным доступом, но он может быть изменен для работы без — вам просто нужно быть более осторожным, чтобы избежать ярлыков, таких как end - begin и iter + n.

#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <vector>

template<class A, class C = std::less<typename A::value_type> >
class LinearTimeSelect {
public:
    LinearTimeSelect(const A &things) : things(things) {}
    typename A::value_type nth(int n) {
        return nth(n, things.begin(), things.end());
    }
private:
    static typename A::value_type nth(int n,
            typename A::iterator begin, typename A::iterator end) {
        int size = end - begin;
        if (size <= 5) {
            std::sort(begin, end, C());
            return begin[n];
        }
        typename A::iterator walk(begin), skip(begin);
#ifdef RANDOM // randomized algorithm, average linear-time
        typename A::value_type pivot = begin[std::rand() % size];
#else // guaranteed linear-time, but usually slower in practice
        while (end - skip >= 5) {
            std::sort(skip, skip + 5);
            std::iter_swap(walk++, skip + 2);
            skip += 5;
        }
        while (skip != end) std::iter_swap(walk++, skip++);
        typename A::value_type pivot = nth((walk - begin) / 2, begin, walk);
#endif
        for (walk = skip = begin, size = 0; skip != end; ++skip)
            if (C()(*skip, pivot)) std::iter_swap(walk++, skip), ++size;
        if (size <= n) return nth(n - size, walk, end);
        else return nth(n, begin, walk);
    }
    A things;
};

int main(int argc, char **argv) {
    std::vector<int> seq;
    {
        int i = 32;
        std::istringstream(argc > 1 ? argv[1] : "") >> i;
        while (i--) seq.push_back(i);
    }
    std::random_shuffle(seq.begin(), seq.end());
    std::cout << "unordered: ";
    for (std::vector<int>::iterator i = seq.begin(); i != seq.end(); ++i)
        std::cout << *i << " ";
    LinearTimeSelect<std::vector<int> > alg(seq);
    std::cout << std::endl << "linear-time medians: "
        << alg.nth((seq.size()-1) / 2) << ", " << alg.nth(seq.size() / 2);
    std::sort(seq.begin(), seq.end());
    std::cout << std::endl << "medians by sorting: "
        << seq[(seq.size()-1) / 2] << ", " << seq[seq.size() / 2] << std::endl;
    return 0;
}

Ответ 8

Вот ответ, который рассматривает предложение @MatthieuM. т.е. не изменяет входной вектор. Он использует единую частичную сортировку (по вектору индексов) для обоих диапазонов четной и нечетной мощности, тогда как пустые диапазоны обрабатываются исключениями, создаваемыми методом вектора at:

double median(vector<int> const& v)
{
    bool isEven = !(v.size() % 2); 
    size_t n    = v.size() / 2;

    vector<size_t> vi(v.size()); 
    iota(vi.begin(), vi.end(), 0); 

    partial_sort(begin(vi), vi.begin() + n + 1, end(vi), 
        [&](size_t lhs, size_t rhs) { return v[lhs] < v[rhs]; }); 

    return isEven ? 0.5 * (v[vi.at(n-1)] + v[vi.at(n)]) : v[vi.at(n)];
}

Демо