libreria - push_back c++

¿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 utilizo algo más que 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 yo mismo e ir con, por ejemplo, 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

Al reunir 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 2

Aquí hay una respuesta que considera la sugerencia de @MatthieuM. es decir , no modifica el vector de entrada . Utiliza un único tipo parcial (en un vector de índices) para ambos rangos de cardinalidad par e impar, mientras que los rangos vacíos se manejan con excepciones lanzadas por el método de vectores 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)];
}

Manifestación

Answer 3

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

Maneja entrada impar o incluso de longitud.

Answer 4

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 se garantiza que todos los elementos anteriores a n son menores que v[n] , pero que no están necesariamente ordenados.

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

Existe un algoritmo de selección de tiempo lineal . El código siguiente solo funciona cuando el contenedor tiene un iterador de acceso aleatorio, pero se puede modificar para que funcione sin necesidad de hacerlo; solo tendrá que ser un poco más cuidadoso para evitar atajos como 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 6

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í hay un 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 7

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

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

Answer 8

Cualquier contenedor de acceso aleatorio (como std::vector ) se puede ordenar con el algoritmo estándar std::sort , disponible en el encabezado <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. Para que pueda encontrar la mediana de esta manera:

int median(vector<int> &v)
{
    size_t n = v.size() / 2;
    nth_element(v.begin(), v.begin()+n, v.end());
    return v[n];
}