universales - Recomienda el contenedor C++ para mantener los 20 valores mínimos

todos los valores que existen

Question

En SQL hay la característica para decir algo como

SELECT TOP 20 distance FROM dbFile ORDER BY distance ASC

Si mi SQL es correcto con, digamos 10,000 registros, esto debería devolver las 20 distancias más pequeñas en mi base de datos.

No tengo una base de datos. Tengo una matriz simple de 100.000 elementos.

¿Existe un contenedor de C ++, Boost , MFC o STL que proporcione un código simple para una estructura como

struct closest{
    int    ID;
    double distance;
    closest():ID(-1), distance(std::numeric_limits<double>::max( )){}
};

Donde puedo construir un contenedor ordenado por distancia como

boost::container::XXXX<closest> top(20);

Y luego tener un simple

top.replace_if(closest(ID,Distance));

Donde el contenedor reemplazará la entrada con la distancia más alta actual en mi contenedor con mi nueva entrada si es menor que la distancia más alta actual en mi contenedor.

No me preocupa la velocidad. Me gustan las soluciones elegantes y limpias donde los contenedores y el código hacen todo el trabajo pesado .

EDITAR. Addendum después de todas las grandes respuestas recibidas.

Lo que realmente me hubiera gustado encontrar, debido a su elegancia. Es un contenedor ordenado que podría crear con un límite de tamaño de contenedor. En mi caso, 20. Luego podría empujar o insertar en mis corazones contenido 100 000 artículos o más. Pero. Siempre hay un pero. El contenedor mantendría el tamaño máximo de 20 al reemplazar o no insertar un artículo si su valor de comparación no estaba dentro de los 20 valores más bajos.

Sí. Ahora sé por todas estas respuestas que mediante la programación y el ajuste de los contenedores existentes se puede lograr el mismo efecto. Quizás cuando la próxima ronda de sugerencias para el comité de estándares de C & C ++ tenga lugar. Podríamos sugerir Auto clasificación (que ya tenemos) y contenedores limitadores de tamaño.

Answer 1

De hecho, tengo 100 000 puntos Lat y Lon dibujados en una esfera abierta. Quiero calcular los 20 puntos más cercanos a cada uno de los 100 000 puntos. Así que tenemos dos bucles para elegir cada punto y luego calcular ese punto contra cada otro punto y guardar los 20 puntos más cercanos.

Esto se lee como si quisieras realizar una búsqueda de vecino k más cercano en primer lugar. Para esto, usualmente usas estructuras de datos especializados (por ejemplo, un árbol de búsqueda binario) para acelerar las consultas (especialmente cuando estás haciendo 100k de ellas).

Para las coordenadas esféricas, tendría que hacer una conversión a un espacio cartesiano para arreglar el ajuste de coordenadas. Entonces usarías un Octree o kD-Tree.

Este es un enfoque que utiliza la Biblioteca rápida para los vecinos más cercanos aproximados (FLANN):

#include <vector>
#include <random>
#include <iostream>
#include <flann/flann.hpp>
#include <cmath>

struct Point3d {
    float x, y, z;
    void setLatLon(float lat_deg, float lon_deg) {
        static const float r = 6371.; // sphere radius
        float lat(lat_deg*M_PI/180.), lon(lon_deg*M_PI/180.);
        x = r * std::cos(lat) * std::cos(lon);
        y = r * std::cos(lat) * std::sin(lon);
        z = r * std::sin(lat);
    }
};

std::vector<Point3d> random_data(std::vector<Point3d>::size_type n) {
    static std::mt19937 gen{std::random_device()()};
    std::uniform_int_distribution<> dist(0, 36000);
    std::vector<Point3d> out(n);
    for (auto &i: out)
        i.setLatLon(dist(gen)/100., dist(gen)/100.);
    return out;
}

int main() {
    // generate random spherical point cloud
    std::vector<Point3d> data = random_data(1000);
    // generate query point(s) on sphere
    std::vector<Point3d> query = random_data(1);

    // convert into library datastructures
    auto mat_data = flann::Matrix<float>(&data[0].x, data.size(), 3);
    auto mat_query = flann::Matrix<float>(&query[0].x, query.size(), 3);
    // build KD-Tree-based index data structure
    flann::Index<flann::L2<float> > index(mat_data, flann::KDTreeIndexParams(4));
    index.buildIndex();
    // perform query: approximate nearest neighbor search
    int k = 5; // number of neighbors to find
    std::vector<std::vector<int>> k_indices;
    std::vector<std::vector<float>> k_dists;
    index.knnSearch(mat_query, k_indices, k_dists, k, flann::SearchParams(128));

    // k_indices now contains for each query point the indices to the neighbors in the original point cloud
    // k_dists now contains for each query point the distances to those neighbors
    // removed printing of results for brevity
}

Recibiría resultados similares a este (haga clic para ampliar):

Para referencia:

• https://en.wikipedia.org/wiki/Nearest_neighbor_search
• https://en.wikipedia.org/wiki/Octree
• https://en.wikipedia.org/wiki/Kd-tree
• http://www.cs.ubc.ca/research/flann/

Answer 2

He publicado una serie de enfoques para el problema similar de recuperar los 5 valores mínimos principales recientemente aquí:

• https://.com/a/33687969/1025391

Existen implementaciones que mantienen un número específico de elementos más pequeños o más grandes de un vector de entrada de diferentes maneras. El algoritmo nth_element realiza una ordenación parcial, la cola de prioridad mantiene un montón, establece un árbol de búsqueda binario y las aproximaciones basadas en deque y vector solo eliminan un elemento basado en una búsqueda mínima / máxima (lineal).

Debería ser bastante fácil implementar un operador de comparación personalizado y adaptar el número de elementos para mantener n .

Aquí está el código (refactorizado basado en la otra publicación):

#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <vector>
#include <random>
#include <iostream>
#include <chrono>

template <typename T, typename Compare = std::less<T>>
std::vector<T> filter_nth_element(std::vector<T> v, typename std::vector<T>::size_type n) {
    auto target = v.begin()+n;
    std::nth_element(v.begin(), target, v.end(), Compare());
    std::vector<T> result(v.begin(), target);
    return result;
}

template <typename T, typename Compare = std::less<T>>
std::vector<T> filter_pqueue(std::vector<T> v, typename std::vector<T>::size_type n) {
    std::vector<T> result;
    std::priority_queue<T, std::vector<T>, Compare> q;
    for (auto i: v) {
        q.push(i);
        if (q.size() > n) {
            q.pop();
        }
    }
    while (!q.empty()) {
        result.push_back(q.top());
        q.pop();
    }
    return result;
}

template <typename T, typename Compare = std::less<T>>
std::vector<T> filter_set(std::vector<T> v, typename std::vector<T>::size_type n) {
    std::set<T, Compare> s;
    for (auto i: v) {
        s.insert(i);
        if (s.size() > n) {
            s.erase(std::prev(s.end()));
        }
    }
    return std::vector<T>(s.begin(), s.end());
}

template <typename T, typename Compare = std::less<T>>
std::vector<T> filter_deque(std::vector<T> v, typename std::vector<T>::size_type n) {
    std::deque<T> q;
    for (auto i: v) {
        q.push_back(i);
        if (q.size() > n) {
            q.erase(std::max_element(q.begin(), q.end(), Compare()));
        }
    }
    return std::vector<T>(q.begin(), q.end());
}

template <typename T, typename Compare = std::less<T>>
std::vector<T> filter_vector(std::vector<T> v, typename std::vector<T>::size_type n) {
    std::vector<T> q;
    for (auto i: v) {
        q.push_back(i);
        if (q.size() > n) {
            q.erase(std::max_element(q.begin(), q.end(), Compare()));
        }
    }
    return q;
}

template <typename Clock = std::chrono::high_resolution_clock>
struct stopclock {
    std::chrono::time_point<Clock> start;
    stopclock() : start(Clock::now()) {}
    ~stopclock() {
        auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(Clock::now() - start);
        std::cout << "elapsed: " << elapsed.count() << "ms/n";
    }
};

std::vector<int> random_data(std::vector<int>::size_type n) {
    std::mt19937 gen{std::random_device()()};
    std::uniform_int_distribution<> dist;
    std::vector<int> out(n);
    for (auto &i: out)
        i = dist(gen);
    return out;
}

int main() {
    std::vector<int> data = random_data(1000000);
    stopclock<> sc;
    std::vector<int> result = filter_nth_element(data, 5);
    std::cout << "smallest values: ";
    for (auto i : result) {
        std::cout << i << " ";
    }
    std::cout << "/n";
    std::cout << "largest values: ";
    result = filter_nth_element<int, std::greater<int>>(data, 5);
    for (auto i : result) {
        std::cout << i << " ";
    }
    std::cout << "/n";
}

Ejemplo de salida es:

$ g++ test.cc -std=c++11 && ./a.out
smallest values: 4433 2793 2444 4542 5557 
largest values: 2147474453 2147475243 2147477379 2147469788 2147468894 
elapsed: 123ms

Tenga en cuenta que, en este caso, solo la posición del elemento n es precisa con respecto al orden impuesto por el operador de comparación proporcionado. Sin embargo, se garantiza que los otros elementos serán más pequeños / mayores o iguales a ese, dependiendo del operador de comparación provisto. Es decir, se devuelven los elementos n / max superiores, pero no están ordenados correctamente.

Tampoco espere que los otros algoritmos produzcan resultados en un orden específico. (Si bien los enfoques que utilizan la cola y el conjunto de prioridad en realidad producen resultados ordenados, sus resultados tienen el orden opuesto).

Para referencia:

• std::nth_element
• http://en.cppreference.com/w/cpp/container/priority_queue
• http://en.cppreference.com/w/cpp/container/set
• http://en.cppreference.com/w/cpp/algorithm/max_element

Answer 3

Heap es la estructura de datos que necesitas. stl pre-C ++ 11 solo tenía funciones que administraban datos de pila en sus propios arreglos. Alguien mencionó que boost tiene una clase de pila, pero no necesitas ir tan lejos como para usar boost si tus datos son enteros simples. el montón de stl lo hará bien. Y, por supuesto, el algoritmo es ordenar el montón para que el valor más alto sea el primero. Entonces, con cada nuevo valor, lo empuja en el montón, y, una vez que el montón alcanza 21 elementos en tamaño, saca el primer valor del montón. De esta manera, los 20 valores que permanecen son los 20 más bajos

Answer 4

Lo que necesita es tener un máximo de tamaño de 20. Recuerde que la raíz de su montón será el valor más grande en el montón.

Este montón contendrá los registros con la distancia más pequeña que haya encontrado hasta ahora. Para los primeros 20 valores de entre 10000, solo presiona el montón.

En este punto, recorre el resto de los registros y, para cada registro, lo compara con la raíz de su montón.

Recuerde que la raíz de su montón es básicamente lo peor de lo mejor (el registro con la distancia más grande, entre los 20 registros con la distancia más corta que haya encontrado hasta ahora).

Si el valor que está considerando no vale la pena mantenerlo (su distancia es mayor que la raíz de su árbol), ignore ese registro y siga moviéndose.

De lo contrario, saca su montón (deshacerse de la raíz) y presiona el nuevo valor. La cola de prioridad automáticamente pondrá su registro con la mayor distancia en la raíz de nuevo.

Una vez que continúe haciendo esto en todo el conjunto de valores 10000, se quedarán con los 20 registros que tienen la distancia más pequeña, que es lo que desea.

Cada push-pop toma un tiempo constante de O (1), iterando a través de todas las entradas de N es O (n), por lo que esta es una solución lineal.

Edición: pensé que sería útil mostrar mi idea en código C ++. Este es un ejemplo de juguete, puedes escribir una versión genérica con plantillas, pero elegí mantenerlo simple y minimalista:

#include <iostream>
#include <queue>
using namespace std;
class smallestElements
{
private:
    priority_queue<int,std::vector<int>,std::less<int> > pq;
    int maxSize;
public:
    smallestElements(int size): maxSize(size)
    {
    pq=priority_queue<int, std::vector<int>, std::less<int> >();
    }
    void possiblyAdd(int newValue)
    {
        if(pq.size()<maxSize)
        {
            pq.push(newValue);
            return;
        }
        if(newValue < pq.top())
        {
            pq.pop(); //get rid of the root
            pq.push(newValue); //priority queue will automatically restructure
        }
    }
    void printAllValues()
    {
        priority_queue<int,std::vector<int>,std::less<int> > cp=pq;
        while(cp.size()!=0)
        {
            cout<<cp.top()<<" ";
            cp.pop();
        }
        cout<<endl;
    }
};

¿Cómo se utiliza esto es realmente sencillo. Básicamente en tu función principal en algún lugar tendrás:

smallestElements se(20); //we want 20 smallest
//...get your stream of values from wherever you want, call the int x
se.possiblyAdd(x); //no need for bounds checking or anything fancy
//...keep looping or potentially adding until the end

se.printAllValues();//shows all the values in your container of smallest values
// alternatively you can write a function to return all values if you want

Answer 5

Mi primera idea sería utilizar un std::map o std::set con un comparador personalizado para esto (editar: o incluso mejor, un std::priority_queue como se menciona en los comentarios).

Su comparador hace su clasificación.

Esencialmente le añades todos tus elementos. Después de agregar un elemento, verifique si hay más de n elementos dentro. Si los hay, quita el último.

Answer 6

No estoy 100% seguro de que no haya una solución más elegante, pero incluso std :: set es bastante bonito.

Todo lo que tiene que hacer es definir un comparador adecuado para sus elementos (por ejemplo, un operador>) y luego hacer lo siguiente:

std::set<closest> tops(arr, arr+20)
tops.insert(another);
tops.erase(tops.begin());

Answer 7

Si se trata de filtrar los 20 elementos más pequeños de un flujo sobre la marcha, entonces una solución basada en std::priority_queue (o std::multiset ) es el camino a seguir.

Sin embargo, si se trata de encontrar los 20 elementos más pequeños en una matriz dada, no buscaría un contenedor especial, sino simplemente el algoritmo std::nth_element - un algoritmo de clasificación parcial que le dará los n elementos más pequeños - EDITAR : o std::partial_sort (gracias Jarod42) si los elementos también tienen que ordenarse. Tiene una complejidad lineal y solo es una línea para escribir (+ el operador de comparación, que necesita en cualquier caso):

#include <vector>
#include <iostream>
#include <algorithm>

struct Entry {
    int ID;
    double distance;    
};

std::vector<Entry> data;    

int main() {
    //fill data;

    std::nth_element(data.begin(), data.begin() + 19, data.end(), 
        [](auto& l, auto& r) {return l.distance < r.distance; });

    std::cout << "20 elements with smallest distance: /n"; 
    for (size_t i = 0; i < 20; ++i) {
        std::cout << data[i].ID << ":" << data[i].distance << "/n";
    }
    std::cout.flush();
}

Si no desea cambiar el orden de su matriz original, primero tendría que hacer una copia de toda la matriz.

Answer 8

Solo para que todos puedan ver lo que estoy haciendo actualmente que parece funcionar.

struct closest{
    int base_ID;
    int ID;
    double distance;

    closest(int BaseID, int Point_ID, 
    double Point_distance):base_ID(BaseID), 
    ID(Point_ID),distance(Point_distance){}
    closest():base_ID(-1), ID(-1),
    distance(std::numeric_limits<double>::max( )){}

    bool operator<(const closest& rhs) const
    {
        return distance < rhs.distance;
    }
};



void calc_nearest(void) 
{ 
    boost::heap::priority_queue<closest> svec;

    for (int current_gift = 0; current_gift < g_nVerticesPopulated; ++current_gift)
    {   double best_distance=std::numeric_limits<double>::max();    
        double our_distance=0.0;
        svec.clear();

        for (int all_other_gifts = 0; all_other_gifts < g_nVerticesPopulated;++all_other_gifts)
        {   
            our_distance = distanceVincenty(g_pVertices[current_gift].lat,g_pVertices[current_gift].lon,g_pVertices[all_other_gifts].lat,g_pVertices[all_other_gifts].lon);
            if (our_distance != 0.0)
            {
                if (our_distance < best_distance) // don''t bother to push and sort if the calculated distance is greater than current 20th value
                    svec.push(closest(g_pVertices[current_gift].ID,g_pVertices[current_gift].ID,our_distance));

                if (all_other_gifts%100 == 0)
                {
                    while (svec.size() > no_of_closest_points_to_calculate) svec.pop(); // throw away any points above no_of_closest_points_to_calculate
                    closest t =  svec.top(); // the furthest of the no_of_closest_points_to_calculate points for optimisation
                    best_distance = t.distance;
                }
            }
        }
        std::cout << current_gift << "/n";
    }
}

Como puedes ver. Tengo 100 000 puntos lat y largos dibujados en una esfera abierta. Estoy calculando cada punto contra cada otro punto y solo estoy reteniendo actualmente los 20 puntos más cercanos. Hay una optimización primitiva en marcha al no presionar un valor si es más grande que el vigésimo punto más cercano.

Como estoy acostumbrado a que Prolog tome horas para resolver algo, no me preocupa la velocidad. Voy a ejecutar esto durante la noche.

Gracias a todos por vuestra ayuda. Es muy apreciado. Todavía tengo que auditar el código y los resultados, pero me alegro de que me esté moviendo en la dirección correcta.

Answer 9

Yo usaría nth_element como @juanchopanza sugirió antes de que lo eliminara.

Su código parecía:

bool comp(const closest& lhs, const closest& rhs)
{
    return lhs.distance < rhs.distance;
}

entonces

std::vector<closest> v = ....;
nth_element(v.begin(), v.begin() + 20, v.end(), comp);

Aunque si solo fuera veinte elementos, usaría un std::array .