Qual è l'approccio corretto quando si utilizza il contenitore STL per il calcolo mediano?

Question

Diciamo che ho bisogno di recuperare la mediana da una sequenza di 1000000 valori numerici casuali.

Se si utilizza qualcosa ma STL :: elenco, non ho (incorporato) modo per ordinare la sequenza per il calcolo mediano.

Se si utilizza STL :: list, non è possibile accedere in modo casuale ai valori per recuperare il middle (mediano) della sequenza ordinata.

È meglio implementare me stesso l'ordinamento e andare ad es. STL :: vector, o è meglio usare STL :: list e usare STL :: list :: iterator per for-loop-walk al valore mediano? Quest'ultimo sembra meno drammatico, ma si sente anche più brutto ..

O ci sono altre alternative migliori per me?

Answer 1

Qualunque contenitore ad accesso casuale (come std::vector) può essere ordinato con lo standard std::sort algoritmo, disponibile nell'intestazione <algorithm>.

Per trovare la mediana, sarebbe più veloce utilizzare std::nth_element; questo fa abbastanza per mettere un elemento scelto nella posizione corretta, ma non ordina completamente il contenitore. Così si potrebbe trovare la mediana in questo modo:

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

È possibile ordinare uno std::vector utilizzando la funzione di libreria std::sort.

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

Answer 3

Esiste una linear-time selection algorithm. Il codice riportato di seguito funziona solo quando il contenitore ha un iteratore di accesso casuale, ma può essere modificato per funzionare senza —, ma dovrai fare un po 'più attenzione per evitare scorciatoie come end - begin e 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; 
} 

Answer 4

La mediana è più complessa della risposta di Mike Seymour. La mediana differisce a seconda che nel campione ci sia un numero pari o dispari di oggetti. Se c'è un numero pari di oggetti, la mediana è la media dei due elementi centrali. Ciò significa che la mediana di un elenco di numeri interi può essere una frazione. Infine, la mediana di una lista vuota non è definita. Ecco il codice che passa i miei casi di test di base:

///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 5

Ecco una versione più completa della risposta di Mike Seymour:

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

Esso gestisce l'input dispari o anche di lunghezza.

Answer 6

Questo algoritmo gestisce gli input di dimensione pari e dispari in modo efficiente utilizzando l'algoritmo STL nth_element (amortized O (N)) e l'algoritmo max_element (O (n)). Nota che nth_element ha un altro effetto collaterale garantito, vale a dire che tutti gli elementi precedenti allo n sono tutti garantiti per essere inferiori a v[n], ma non necessariamente ordinati.

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

mettendo insieme tutti gli approfondimenti da questo thread ho finito per avere questa routine. funziona con qualsiasi stl-container o qualsiasi classe che fornisce iteratori di input e gestisce contenitori di dimensioni pari e dispari. Funziona anche su una copia del contenitore, per non modificare il contenuto originale.

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 8

Ecco una risposta che considera il suggerimento di @MatthieuM. cioè non modifica il vettore di input. Si utilizza un unico ordinamento parziale (su un vettore di indici) per entrambe le gamme di pari e dispari cardinalità, mentre intervalli vuoti sono trattati con eccezioni generate dal metodo di un vettore 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)]; 
} 

Demo