Объединение отсортированных массивов - эффективное решение

Question

Цель здесь - объединить несколько массивов, которые уже отсортированы, в результирующий массив.

Я написал следующее решение и задаюсь вопросом, есть ли способ улучшить решение

/*
    Goal is to merge all sorted arrays
*/
void mergeAll(const vector< vector<int> >& listOfIntegers,  vector<int>& result)
{

    int totalNumbers = listOfIntegers.size();
    vector<int> curpos;
    int currow = 0 , minElement , foundMinAt = 0;
    curpos.reserve(totalNumbers);

    // Set the current position that was travered to 0 in all the array elements
    for ( int i = 0; i < totalNumbers; ++i)
    {
        curpos.push_back(0);
    }

    for ( ; ; )
    {
        /*  Find the first minimum 
            Which is basically the first element in the array that hasn't been fully traversed
        */

        for ( currow = 0 ; currow < totalNumbers ; ++currow)
        {
            if ( curpos[currow] < listOfIntegers[currow].size() )
            {
                minElement = listOfIntegers[currow][curpos[currow] ];
                foundMinAt = currow;
                break;
            }
        }
        /* If all the elements were traversed in all the arrays, then no further work needs to be done */
        if ( !(currow < totalNumbers ) )
            break;
        /* 
            Traverse each of the array and find out the first available minimum value
        */
        for ( ;currow < totalNumbers; ++currow)
        {
            if ( listOfIntegers[currow][curpos[currow] ] < minElement )
            {
                minElement = listOfIntegers[currow][curpos[currow] ];
                foundMinAt = currow;
            }
        }
        /* 
            Store the minimum into the resultant array 
            and increment the element traversed
        */
        result.push_back(minElement);
        ++curpos[foundMinAt];
    }
}

Соответствующий основной идет следующим образом.

int main()
{
    vector< vector<int> > myInt;
    vector<int> result;

    myInt.push_back(vector<int>() );
    myInt.push_back(vector<int>() );
    myInt.push_back(vector<int>() );

    myInt[0].push_back(10);
    myInt[0].push_back(12);
    myInt[0].push_back(15);


    myInt[1].push_back(20);
    myInt[1].push_back(21);
    myInt[1].push_back(22);

    myInt[2].push_back(14);
    myInt[2].push_back(17);
    myInt[2].push_back(30);

    mergeAll(myInt,result);

    for ( int i = 0; i < result.size() ; ++i)
    {
        cout << result[i] << endl;
    }
}

Answer 1

Вы можете обобщить алгоритм сортировки слиянием и работать с несколькими указателями. Изначально все они указывают на начало каждого массива. Вы поддерживаете эти указатели, отсортированные (по значениям, на которые они указывают) в очереди приоритетов. На каждом шаге вы удаляете наименьший элемент в куче в O(log n) (n - количество массивов). Затем вы выводите элемент, на который указывает извлеченный указатель. Теперь вы увеличиваете этот указатель на одну позицию, и если вы не достигли конца массива, заново вставьте в очередь с приоритетами в O(log n). Продолжайте до тех пор, пока куча не станет пустой. Если имеется всего m элементов, сложность составляет O(m log n). Таким образом, элементы выводятся в отсортированном порядке.

Answer 2

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

void merge(const int list1[], int size1, const int list2[], int size2, int list3[]) {

    // Declaration & Initialization
    int index1 = 0, index2 = 0, index3 = 0;

    // Loop untill both arrays have reached their upper bound.
    while (index1 < size1 || index2 < size2) {

        // Make sure the first array hasn't reached 
        // its upper bound already and make sure we 
        // don't compare outside bounds of the second 
        // array.
        if ((list1[index1] <= list2[index2] && index1 < size1) || index2 >= size2) {
            list3[index3] = list1[index1];
            index1++;
        }
        else {
            list3[index3] = list2[index2];
            index2++;
        }
        index3++;
    }
}

Answer 3

Возможно, я неправильно понимаю вопрос ... и мне кажется, что я неправильно понимаю ваше решение.

Тем не менее, возможно, этот ответ совершенно неосновательный и бесполезный.

Но, особенно с количеством vector с и push_back, которое вы уже используете, почему вы не просто используете std::sort?

#include <algorithm>
void mergeAll(const vector<vector<int>> &origList, vector<int> &resultList)
{
    for(int i = 0; i < origList.size(); ++i)
    {
        resultList.insert(resultList.end(), origList[i].begin(), origList[i].end());
    }
    std::sort(resultList.begin(), resultList.end());
}

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

std::sort работает в O(N log (N)) http://www.cppreference.com/wiki/stl/algorithm/sort

Answer 4

Рассмотрим реализацию очереди приоритетов в этом ответе, связанном в комментарии выше: Объединение 8 отсортированных списков в c ++, какой алгоритм мне следует использовать

Время O (n lg m)(где n = общее количество элементов и m = количество списков).

Answer 5

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

т.е. предположить, что у вас есть 9 списков.

объединить список0 с 1. объединить список 2 с 3. объединить список 4 с 5. объединить список 6 с 7.

Они могут выполняться одновременно.

Тогда:

объединить список0 & 1 с 2 & 3 слились со списком 4 & 5 с 6 & 7

Опять же, они могут выполняться одновременно.

затем объединить списки 0,1,2 & 3 со списком 4,5,6 & 7

наконец слитьсписок 0,1,2,3,4,5,6 и 7 со списком 8.

Работа выполнена.

Я не уверен в сложности этого, но кажется очевидным решением иДОЛЖЕН ли я быть в некоторой степени многопоточным.

Answer 6

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

Edit: Вы можете тривиально расширить это до N массивов.

Edit: Не тривиально расширять это до N массивов :-). Делай два одновременно. Глупый я.

Answer 7

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

Answer 8

Вы можете просто вставить их все в мультимножество. Это будет обрабатывать сортировку для вас.