Какой правильный подход при использовании контейнера STL для вычисления медианы?
Допустим, мне нужно получить медиану из последовательности 1000000 случайных числовых значений.
Если используется что-то кроме STL::list, у меня нет (встроенного) способа сортировки последовательности для вычисления медианы.
При использовании STL:: list я не могу получить произвольный доступ к значениям для получения середины (медианы) отсортированной последовательности.
Лучше реализовать сортировку самостоятельно и перейти, например, с помощью STL:: vector, или же лучше использовать STL:: list и использовать STL:: list:: iterator для обхода цикла до среднего значения? Последний кажется менее надуманным, но и более уродливым.
Или есть еще и лучшие альтернативы для меня?
8 ответов
Любой контейнер с произвольным доступом (например, 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];
}
Медиана более сложна, чем ответ Майка Сеймура. Медиана отличается в зависимости от того, есть ли в выборке четное или нечетное количество элементов. Если есть четное количество предметов, медиана - это среднее от средних двух предметов. Это означает, что медиана списка целых чисел может быть дробной. Наконец, медиана пустого списка не определена. Вот код, который проходит мои основные тестовые случаи:
///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;
}
}
Этот алгоритм эффективно обрабатывает входные данные как четного, так и нечетного размера, используя алгоритм 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;
}
Вот более полная версия ответа Майка Сеймура:
// 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]);
}
}
Он обрабатывает ввод нечетной или четной длины.
Соединив все идеи из этой темы, я получил эту рутину. он работает с любым 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;
}
}
Вы можете отсортировать std::vector используя библиотечную функцию std::sort,
std::vector<int> vec;
// ... fill vector with stuff
std::sort(vec.begin(), vec.end());
Вот ответ, который рассматривает предложение @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)];
}
Существует алгоритм выбора линейного времени. Приведенный ниже код работает только тогда, когда контейнер имеет итератор с произвольным доступом, но его можно изменить, чтобы он работал без него - вам просто нужно быть немного более осторожным, чтобы избежать таких ярлыков, как 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;
}
Armadillo имеет реализацию, которая выглядит так, как в ответ /questions/426621/kakoj-pravilnyij-podhod-pri-ispolzovanii-kontejnera-stl-dlya-vyichisleniya-medianyi/426640#426640 по Matthew Fioravante
Он использует один вызов nth_element и один звонок max_elementи это здесь: https://gitlab.com/conradsnicta/armadillo-code/-/blob/9.900.x/include/armadillo_bits/op_median_meat.hpp
//! find the median value of a std::vector (contents is modified)
template<typename eT>
inline
eT
op_median::direct_median(std::vector<eT>& X)
{
arma_extra_debug_sigprint();
const uword n_elem = uword(X.size());
const uword half = n_elem/2;
typename std::vector<eT>::iterator first = X.begin();
typename std::vector<eT>::iterator nth = first + half;
typename std::vector<eT>::iterator pastlast = X.end();
std::nth_element(first, nth, pastlast);
if((n_elem % 2) == 0) // even number of elements
{
typename std::vector<eT>::iterator start = X.begin();
typename std::vector<eT>::iterator pastend = start + half;
const eT val1 = (*nth);
const eT val2 = (*(std::max_element(start, pastend)));
return op_mean::robust_mean(val1, val2);
}
else // odd number of elements
{
return (*nth);
}
}
you can use this approch. It also takes care of sliding window.
Here days are no of trailing elements for which we want to find median and this makes sure the original container is not changed
#include<bits/stdc++.h>
using namespace std;
int findMedian(vector<int> arr, vector<int> brr, int d, int i)
{
int x,y;
x= i-d;
y=d;
brr.assign(arr.begin()+x, arr.begin()+x+y);
sort(brr.begin(), brr.end());
if(d%2==0)
{
return((brr[d/2]+brr[d/2 -1]));
}
else
{
return (2*brr[d/2]);
}
// for (int i = 0; i < brr.size(); ++i)
// {
// cout<<brr[i]<<" ";
// }
return 0;
}
int main()
{
int n;
int days;
int input;
int median;
int count=0;
cin>>n>>days;
vector<int> arr;
vector<int> brr;
for (int i = 0; i < n; ++i)
{
cin>>input;
arr.push_back(input);
}
for (int i = days; i < n; ++i)
{
median=findMedian(arr,brr, days, i);
}
return 0;
}