1000000 個のランダムな数値のシーケンスから中央値を取得する必要があるとしましょう。
以外のものを使用する場合、中央値計算のためにシーケンスを並べ替える (組み込みの) 方法がありません。 std::list
を使用している場合std::list、値にランダムにアクセスして、並べ替えられたシーケンスの中央 (中央値) を取得することはできません。
自分でソートを実装して egstd::vectorを使用する方が良いですか、それともfor-loop-walk をstd::list使用std::list::iteratorして中央値まで使用する方が良いですか? 後者はオーバーヘッドが少ないように見えますが、より醜く感じます..
または、私にとってより良い代替手段はありますか？
任意のランダム アクセス コンテナー ( など) は、ヘッダーで使用可能な標準アルゴリズムを使用してstd::vector並べ替えることができます。std::sort<algorithm>
中央値を見つけるには、std::nth_element;を使用する方が速いでしょう。これは、選択した 1 つの要素を正しい位置に配置するのに十分な並べ替えを行いますが、コンテナーを完全に並べ替えるわけではありません。したがって、次のように中央値を見つけることができます。
int median(vector<int> &v)
{
size_t n = v.size() / 2;
nth_element(v.begin(), v.begin()+n, v.end());
return v[n];
}
中央値は、MikeSeymourの回答よりも複雑です。中央値は、サンプルに偶数または奇数のアイテムがあるかどうかによって異なります。アイテムの数が偶数の場合、中央値は中央の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)
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;
}
このスレッドからのすべての洞察をまとめると、私はこのルーチンを持つことになりました. stl-container または入力イテレータを提供する任意のクラスで動作し、奇数および偶数サイズのコンテナを処理します。また、元のコンテンツを変更しないように、コンテナーのコピーに対しても機能します。
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());
線形時間選択アルゴリズムが存在します。以下のコードは、コンテナにランダムアクセスイテレータがある場合にのみ機能しますが、それがなくても機能するように変更できます。やのようなショートカットを避けるために、もう少し注意する必要が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には、https://stackoverflow.com/users/2608582/matthew-fioravanteによる回答https://stackoverflow.com/a/34077478のような実装があります。
それは への 1 つの呼び出しと へnth_elementの 1つの呼び出しを使用しmax_element、ここにあります:
https://gitlab.com/conradsnicta/armadillo-code/-/blob/9.900.x/include/armadillo_bits/op_median_meat.hpp#L380
//! 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);
}
}