Рекомендовать контейнер С++ для хранения 20 верхних минимальных значений

Ответ 1

Вам нужно иметь максимальный размер размера 20. Напомним, что корень вашей кучи будет самым большим значением в куче.

Эта куча будет содержать записи с наименьшим расстоянием, с которыми вы столкнулись. Для первых 20 из 10000 значений вы просто нажимаете на кучу.

На этом этапе вы перебираете остальные записи и для каждой записи сравниваете ее с корнем своей кучи.

Помните, что корень вашей кучи в основном самый худший из самых лучших. (Запись с наибольшим расстоянием среди 20 записей с самым коротким расстоянием, с которым вы столкнулись до сих пор).

Если значение, которое вы рассматриваете, не стоит держать (его расстояние больше, чем корень вашего дерева), игнорируйте эту запись и просто продолжайте двигаться.

В противном случае вы попнете свою кучу (избавьтесь от корня) и введете новое значение. Очередь приоритетов автоматически поместит свою запись с наибольшим расстоянием в корне.

Как только вы продолжаете делать это по всему набору значений 10000, вы останетесь с 20 записями, которые имеют наименьшее расстояние, и это то, что вы хотите.

Каждый push-pop принимает постоянное время O (1), итерация через все входы N равна O (n), поэтому это линейное решение.

Изменить: Я подумал, что было бы полезно показать мою идею в коде на С++. Это пример игры, вы можете написать общую версию с шаблонами, но я решил сохранить ее простой и минималистический:

#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;
    }
};

Как вы это используете, это действительно прямо. в основном в вашей основной функции где-нибудь вы будете:

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

Ответ 2

Если речь идет о фильтрации 20 наименьших элементов из потока "на лету", то решение, основанное на std::priority_queue (или std::multiset), - это путь.

Однако, если речь идет о поиске 20 наименьших элементов в заданном массиве, я бы вообще не пошел на специальный контейнер, а просто алгоритм std::nth_element - алгоритм частичной сортировки, который даст вам n наименьших элементов - EDIT: или std::partial_sort (спасибо Jarod42), если элементы также должны быть отсортированы. Он имеет линейную сложность, и это всего лишь одна строка для записи (+ оператор сравнения, который вам нужен в любом случае):

#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();
}

Если вы не хотите изменять порядок исходного массива, сначала вам нужно сделать копию всего массива.

Ответ 3

Моя первая идея будет использовать std::map или std::set с помощью специального компаратора для этого (отредактируйте: или даже лучше, std::priority_queue, как указано в комментариях).

Ваш компаратор выполняет вашу сортировку.

Вы по существу добавляете к нему все свои элементы. После добавления элемента убедитесь, что внутри него больше элементов n. Если есть, удалите последний.

Ответ 4

Я не уверен на 100%, что нет более элегантного решения, но даже std:: set довольно красиво.

Все, что вам нужно сделать, это определить правильный компаратор для ваших элементов (например, оператор a > ), а затем сделать следующее:

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

Ответ 5

Я бы использовал nth_element, как предлагал @juanchopanza, прежде чем удалил его.

Его код выглядел так:

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

затем

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

Хотя если бы это было только двадцать, то я использовал бы std::array.

Ответ 6

Просто чтобы вы все могли видеть, что я делаю сейчас, что кажется сработавшим.

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";
    }
}

Как вы можете видеть. У меня 100 000 латов и длинных очков нарисованы на сфере openGl. Я вычисляю каждую точку против каждой другой точки и сохраняю в настоящее время самые близкие 20 пунктов. Существует некоторая примитивная оптимизация, не нажимая значение, если оно больше, чем 20 ближайшая точка.

Поскольку я привык к тому, чтобы Prolog брал часы, чтобы решить что-то, я не беспокоюсь о скорости. Я забегу на ночь.

Спасибо всем за вашу помощь. Это очень ценится. Все еще нужно проверять код и результаты, но счастлив, что я двигаюсь в правильном направлении.

Ответ 7

Недавно я опубликовал ряд подходов к аналогичной проблеме получения пяти верхних минимальных значений:

• fooobar.com/questions/264853/...

Существуют реализации, которые по-разному сохраняют определенное количество наименьших или наибольших элементов из входного вектора. Алгоритм nth_element выполняет частичную сортировку, приоритетная очередь поддерживает кучу, задает двоичное дерево поиска, а подходы, основанные на декадах и векторах, просто удаляют элемент на основе (линейного) поиска min/max.

Это должно быть довольно легко реализовать пользовательский оператор сравнения и адаптировать количество элементов для сохранения 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";
}

Пример вывода:

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

Заметим, что в этом случае только положение n-го элемента является точным относительно порядка, налагаемого предоставленным оператором сравнения. Остальные элементы гарантируют, что они будут меньше/больше или равны этому, в зависимости от оператора сравнения. То есть возвращаются верхние n min/max, но они неправильно отсортированы.

Не ожидайте, что другие алгоритмы будут давать результаты в определенном порядке. (Хотя подходы, использующие приоритетную очередь и набор, фактически производят отсортированный вывод, их результаты имеют противоположный порядок).

Для справки:

• http://en.cppreference.com/w/cpp/algorithm/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

Ответ 8

На самом деле у меня есть 100 000 очков Lat и Lon, нарисованных на сфере opengl. Я хочу разработать 20 ближайших пунктов для каждого из 100 000 пунктов. Таким образом, у нас есть две петли, чтобы выбрать каждую точку, затем вычислить эту точку против каждой другой точки и сохранить ближайшие 20 очков.

Это означает, что вы хотите выполнить поиск k-ближайшего соседа в первую очередь. Для этого обычно используются специализированные структуры данных (например, дерево двоичного поиска) для ускорения запросов (особенно, когда вы делаете 100 тыс. Из них).

Для сферических координат вам нужно сделать преобразование в декартовое пространство, чтобы исправить обход координат. Затем вы будете использовать Octree или kD-Tree.

Здесь используется подход с быстрой библиотекой для приближенных ближайших соседей (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
}

Вы получите результаты, подобные этому (нажмите, чтобы увеличить):

Для справки:

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

Ответ 9

Куча - это структура данных, которая вам нужна. pre-С++ 11 stl имел только функции, которые управляли данными кучи в ваших собственных массивах. Кто-то сказал, что boost имеет класс кучи, но вам не нужно заходить так далеко, чтобы использовать boost, если ваши данные являются простыми целыми числами. stl куча будет прекрасно. И, конечно, алгоритм состоит в том, чтобы упорядочить кучу, чтобы первое значение было первым. Таким образом, с каждым новым значением вы нажимаете его на кучу, и, как только куча достигает 21 элемента по размеру, вы выталкиваете первое значение из кучи. Таким образом, все 20 значений остаются всегда самыми низкими.