C ++ Как объединить отсортированные векторы в отсортированный вектор / вытолкнуть наименьший элемент из всех?

Question

У меня есть коллекция из примерно 100 или около того отсортированных vector<int>. Хотя большинство векторов имеют небольшое количество целых чисел, некоторые из них содержат большое (> 10K) из них (таким образом, векторы нет обязательно иметь одинаковый размер).

То, что я хотел бы сделать, по сути, перебрать наименьшее или наибольшее целое число, содержащееся во всех этих отсортированных векторах.

Один из способов сделать это - объединить все эти отсортированные векторы вотсортированный вектор и просто повторять.Таким образом,

Вопрос 1: Какой самый быстрый способ объединить отсортированные векторы в отсортированный вектор?

Я уверен, с другой стороны, есть быстрее / умнееспособы сделать это без слияния и повторной сортировки всего - возможно, итеративно выталкивая наименьшее целое число из этой коллекции отсортированных векторов;не объединяя их в первую очередь .. так:

Вопрос 2: Какой самый быстрый / лучший способ извлечь наименьший элемент из группы отсортированных vector<int>?

---

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

// compare vector pointers by integers pointed
struct cmp_seeds {
    bool operator () (const pair< vector<int>::iterator, vector<int>::iterator> p1, const pair< vector<int>::iterator, vector<int>::iterator> p2) const {
        return *(p1.first) >  *(p2.first);      
    }
};

int pq_heapsort_trial() {

    /* Set up the Sorted Vectors */ 
    int a1[] = { 2, 10, 100};
    int a2[] = { 5, 15, 90, 200};
    int a3[] = { 12 };

    vector<int> v1 (a1, a1 + sizeof(a1) / sizeof(int));
    vector<int> v2 (a2, a2 + sizeof(a2) / sizeof(int));
    vector<int> v3 (a3, a3 + sizeof(a3) / sizeof(int));

    vector< vector <int> * > sorted_vectors;
    sorted_vectors.push_back(&v1);
    sorted_vectors.push_back(&v2);
    sorted_vectors.push_back(&v3);
    /* the above simulates the "for" i have in my own code that gives me sorted vectors */

    pair< vector<int>::iterator, vector<int>::iterator> c_lead;
    cmp_seeds mycompare;

    priority_queue< pair< vector<int>::iterator, vector<int>::iterator>, vector<pair< vector<int>::iterator, vector<int>::iterator> >, cmp_seeds> cluster_feeder(mycompare);


    for (vector<vector <int> *>::iterator k = sorted_vectors.begin(); k != sorted_vectors.end(); ++k) {
        cluster_feeder.push( make_pair( (*k)->begin(), (*k)->end() ));
    }


    while ( cluster_feeder.empty() != true) {
        c_lead = cluster_feeder.top();
        cluster_feeder.pop();
        // sorted output
        cout << *(c_lead.first) << endl;

        c_lead.first++;
        if (c_lead.first != c_lead.second) {
            cluster_feeder.push(c_lead);
        }
    }

    return 0;
}

Answer 1

Один из вариантов - использовать std :: priority queue для поддержки кучи итераторов, где итераторы накапливаются в куче в зависимости от значений, на которые они указывают.

Вы также можете рассмотретьс использованием повторяющихся приложений std :: inplace_merge.Это будет включать сложение всех данных в большой вектор и запоминание смещений, с которых начинается и заканчивается каждый отдельный отсортированный блок, а затем их передачу в inplace_merge.Вероятно, это будет быстрее, чем решение для кучи, хотя я думаю, что в принципе сложность эквивалентна.

Обновление: Я реализовал второй алгоритм, который только что описал.Неоднократно делать слияние на месте.Этот код находится на ideone .

Это работает, сначала объединяя все отсортированные списки в один длинный список.Если было три списка источников, это означает, что есть четыре «смещения», то есть четыре точки в полном списке, между которыми отсортированы элементы.Затем алгоритм будет обрабатывать три из них одновременно, объединяя два соответствующих смежных отсортированных списка в один отсортированный список, а затем запоминая два из этих трех смещений, которые будут использоваться в new_offsets.

Это повторяется вцикл, в котором пары смежных отсортированных диапазонов объединяются, пока не останется только один отсортированный диапазон.

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

Answer 2

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

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

Я считаю, что это должно иметь асимптотическую сложность O(E log M), где E - общее количество элементов, а M - количество векторов.

Если вы действительно выталкиваете все из векторов, вы можете создать кучу указателей на свои векторы, вы можете также рассматривать их как кучи, чтобы избежать потери производительности при удалении с фронта вектора. (или вы можете сначала скопировать все в deque s)

---

Объединение их всех вместе путем объединения пар одновременно имеет одинаковую асимптотическую сложность, если вы внимательно относитесь к порядку. Если вы упорядочите все векторы в полном сбалансированном двоичном дереве, а затем попарно объединитесь при переходе вверх по дереву, тогда каждый элемент будет скопирован log M раз, что также приведет к алгоритму O(E log M).

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

(действительно, вы хотите упорядочить по «стоимости копирования» вместо длины. Дополнительная вещь для оптимизации для определенных типов значений)

---

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

Answer 3

Я использовал приведенный здесь алгоритм и немного абстрагировался; преобразование в шаблоны. Я кодировал эту версию в VS2010 и использовал лямбда-функцию вместо функтора. Я не знаю, является ли это в каком-то смысле «лучше», чем предыдущая версия, но, может быть, это кому-нибудь пригодится?

#include <queue>
#include <vector>

namespace priority_queue_sort
{
    using std::priority_queue;
    using std::pair;
    using std::make_pair;
    using std::vector;

    template<typename T>
    void value_vectors(const vector< vector <T> * >& input_sorted_vectors, vector<T> &output_vector)
    {
        typedef vector<T>::iterator iter;
        typedef pair<iter, iter>    iter_pair;

        static auto greater_than_lambda = [](const iter_pair& p1, const iter_pair& p2) -> bool { return *(p1.first) >  *(p2.first); };

        priority_queue<iter_pair, std::vector<iter_pair>, decltype(greater_than_lambda) > cluster_feeder(greater_than_lambda);

        size_t total_size(0);

        for (auto k = input_sorted_vectors.begin(); k != input_sorted_vectors.end(); ++k)
        {
            cluster_feeder.push( make_pair( (*k)->begin(), (*k)->end() ) );
            total_size += (*k)->size();
        }

        output_vector.resize(total_size);
        total_size = 0;
        iter_pair c_lead;
        while (cluster_feeder.empty() != true)
        {
            c_lead = cluster_feeder.top();
            cluster_feeder.pop();
            output_vector[total_size++] = *(c_lead.first);
            c_lead.first++;
            if (c_lead.first != c_lead.second) cluster_feeder.push(c_lead);
        }
    }

    template<typename U, typename V>
    void pair_vectors(const vector< vector < pair<U, V> > * >& input_sorted_vectors, vector< pair<U, V> > &output_vector)
    {
        typedef vector< pair<U, V> >::iterator iter;
        typedef pair<iter, iter> iter_pair;

        static auto greater_than_lambda = [](const iter_pair& p1, const iter_pair& p2) -> bool { return *(p1.first) >  *(p2.first); };

        priority_queue<iter_pair, std::vector<iter_pair>, decltype(greater_than_lambda) > cluster_feeder(greater_than_lambda);

        size_t total_size(0);

        for (auto k = input_sorted_vectors.begin(); k != input_sorted_vectors.end(); ++k)
        {
            cluster_feeder.push( make_pair( (*k)->begin(), (*k)->end() ) );
            total_size += (*k)->size();
        }

        output_vector.resize(total_size);
        total_size = 0;
        iter_pair c_lead;

        while (cluster_feeder.empty() != true)
        {
            c_lead = cluster_feeder.top();
            cluster_feeder.pop();
            output_vector[total_size++] = *(c_lead.first);  
            c_lead.first++;
            if (c_lead.first != c_lead.second) cluster_feeder.push(c_lead);
        }
    }
}

Алгоритм priority_queue_sort::value_vectors сортирует векторы, содержащие только значения; тогда как priority_queue_sort::pair_vectors сортирует векторы, содержащие пары данных, по первому элементу данных. Надеюсь, кто-нибудь может использовать это когда-нибудь: -)