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

Question

Допустим, мне нужно получить медиану из последовательности 1000000 случайных числовых значений.

Если используется что-то , но std::list, у меня нет (встроенного) способа сортировки последовательности для вычисления медианы.

Если используется std::list, я не могу получить произвольный доступ к значениям для получения середины (медианы) отсортированной последовательности.

Лучше ли реализовать сортировку самостоятельно и перейти к примеру? std::vector, или лучше использовать std::list и std::list::iterator для обхода цикла до среднего значения? Последний кажется менее надуманным, но и более уродливым.

Или есть еще и лучшие альтернативы для меня?

Answer 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];
}

Answer 2

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

///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;
  }
}

Answer 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]);
  }
}

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

Answer 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;    
}

Answer 5

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

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

Answer 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;
    }
}

Answer 7

Вот ответ, который рассматривает предложение @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)];
}

Демо

Answer 8

Существует алгоритм линейного выбора времени . Приведенный ниже код работает только тогда, когда контейнер имеет итератор с произвольным доступом, но его можно изменить, чтобы он работал без & mdash; вам просто нужно быть немного более осторожным, чтобы избежать ярлыков типа 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;
}