¿Cuál es el enfoque correcto al usar el contenedor STL para el cálculo mediano?

Question

Digamos que necesito recuperar la mediana de una secuencia de 1000000 valores numéricos aleatorios.

Si se usa algo pero STL :: list, no tengo forma (incorporada) de ordenar la secuencia para el cálculo de la mediana.

Si utilizo STL :: list, no puedo acceder aleatoriamente a los valores para recuperar el medio (mediana) de la secuencia ordenada.

¿Es mejor implementar la clasificación por mí mismo y usar, p. STL :: vector, o ¿es mejor usar STL :: list y usar STL :: list :: iterator para for-loop-walk al valor mediano? Este último parece menos costoso, pero también se siente más feo ...

¿O hay más y mejores alternativas para mí?

Answer 1

Cualquier recipiente de acceso aleatorio (como std::vector) pueden ser ordenados con el algoritmo estándar std::sort, disponible en la cabecera <algorithm>.

Para encontrar la mediana, sería más rápido usar std::nth_element; esto hace suficiente para colocar un elemento elegido en la posición correcta, pero no ordena completamente el contenedor. Por lo que podría encontrar la mediana de la siguiente manera:

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

Puede ordenar std::vector usando la función de biblioteca std::sort.

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

Answer 3

Existe una linear-time selection algorithm. El código siguiente solo funciona cuando el contenedor tiene un iterador de acceso aleatorio, pero se puede modificar para que funcione sin —, solo tendrá que ser un poco más cuidadoso para evitar atajos como end - begin y .

#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 es más compleja que la respuesta de Mike Seymour. La mediana difiere dependiendo de si hay un número par o impar de elementos en la muestra. Si hay un número par de elementos, la mediana es el promedio de los dos elementos del medio. Esto significa que la mediana de una lista de enteros puede ser una fracción. Finalmente, la mediana de una lista vacía no está definida. Aquí está el código que pasa mis casos de prueba básicos:

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

Aquí hay una versión más completa de la respuesta de 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]); 
    } 
} 

Se ocupa de entrada par o impar de longitud.

Answer 6

Este algoritmo maneja las entradas de tamaño par e impar de manera eficiente utilizando el algoritmo STL nth_element (amortiguado O (N)) y el algoritmo max_element (O (n)). Tenga en cuenta que nth_element tiene otro efecto secundario garantizado, es decir, que todos los elementos anteriores a n tienen una garantía de menos de v[n], pero no necesariamente están clasificados.

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

armando todas las ideas de este hilo terminé teniendo esta rutina. funciona con cualquier stl-container o cualquier clase que proporcione iteradores de entrada y maneje contenedores de tamaño impar e impar. También hace su trabajo en una copia del contenedor, para no modificar el contenido original.

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

Aquí hay una respuesta que considera la sugerencia de @MatthieuM. es decir, no modifica el vector de entrada. Se utiliza un solo tipo parcial (en un vector de índices) para ambas gamas de cardinalidad par e impar, mientras que los rangos vacíos se manejan con las excepciones lanzadas por el método de un vector 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