Хранение только N наименьших элементов с STL (с дубликатами)

Question

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

int main(int argc, char *argv[])
{
    std::set<int> s;   //EDIT:  std::multiset is an answer to Q1

    for (int i : {6, 6, 5, 8, 3, 4, 0, 2, 8, 9, 7, 2})  //Billions of elements in reality
    {
        if ( (s.size() < 5) || (i <= *(--s.end())) )  //Insert only if not full or when the element to be inserted is smaller than the greatest one already in the set
        {
            if (s.size() >= 5)  //Limit the number of smallest elements that are kept. In reality ~8000
                s.erase(*(--s.end())); //Erase the largest element

            s.insert(i);
        }
    }

    for (int d: s)
        std::cout << d << " ";  //print the 5 smallest elements in ascending order      

    std::cout << '\n';

    return 0;
}

Вывод:

0 2 3 4

Вывод должен быть:

0 2 2 3 4

Q1 : Что необходимо изменить, чтобы разрешить дублирование?
Q2 : Как сделать этот код быстрее, не тратя ГБ памяти на хранение всех элементов ввода? (сейчас код слишком медленный, как есть).

Answer 1

Это звучит как классический вопрос для собеседования «Как хранить наименьшее N элементов без знания размера данных, которые будут обработаны?».

Один из ответов - использовать максимальную кучуN элементов, а затем настройте кучу (удалите верхний элемент, добавьте новый элемент, сложите в кучу), если последующий элемент меньше или равен самому верхнему элементу в куче.

Это легко сделатьиспользуя функции библиотеки C ++ std :: make_heap , std :: pop_heap и std :: push_heap .

Вот пример:

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

int main(int argc, char *argv[])
{
    std::vector<int> s; 
    for (int i : {6, 6, 5, 8, 3, 4, 0, 2, 8, 9, 7, 2})
    {
        // add the first 5 elements to the vector
        if (s.size() < 5)
        {
            s.push_back(i);
            if ( s.size() == 5 )
                // make the max-heap of the 5 elements   
                std::make_heap(s.begin(), s.end());
            continue;
        }

        // now check if the next element is smaller than the top of the heap
        if (s.front() >= i)
        {
            // remove the front of the heap by placing it at the end of the vector
            std::pop_heap(s.begin(), s.end());

            // get rid of that item now 
            s.pop_back();

            // add the new item 
            s.push_back(i);

            // heapify
            std::push_heap(s.begin(), s.end());
        }
    }

    // sort the heap    
    std::sort_heap(s.begin(), s.end());

    for (int d : s)
        std::cout << d << " ";  //print the 5 smallest elements in ascending order      

    std::cout << '\n';

    return 0;
}

Вывод:

0 2 2 3 4

Конечно, вы можете сделать это функцией и заменить жестко закодированный 5 на N.

Если естьэто миллиарды элементов, т.е. гораздо больше элементов, чем N, единственное, что будет храниться в куче, это N элементов.

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

Answer 2

Q2 и ответы: сначала найдите N элементов мультимножества (я не уверен, отсортирован ли он по убыванию или по убыванию, поэтому настройте это), и push_back() переведите их в std::vector.

Answer 3

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

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

int main() 
{

    std::vector<int> vec{ 6, 6, 5, 8, 3, 4, 0, 2, 8, 9, 7, 2 };
    int numElements = 5;

    std::partial_sort(vec.begin(), vec.begin() + numElements, vec.end());

    for (int i = 0; i < numElements; ++i)
    {
        std::cout << vec[i]  << "\n";
    }

    return 0;
}

, если вы не хотитесохранить все входные данные, это зависит немного от того, как вы читаете входные данные, но решение будет немного другим.Например, прочитайте чанки, возьмите наименьшее 5 из каждого чанка и, в конце, просто выполните еще раз на объединенной «наименьшей 5» каждого чанка.