эффективное объединение n отсортированных массивов в C ++ (набор против вектора)?

Question

Мне нужно реализовать эффективный алгоритм для поиска отсортированного объединения из нескольких отсортированных массивов.Поскольку моя программа выполняет множество таких операций, я смоделировал ее с помощью C ++.Мой первый подход (method1) состоял в том, чтобы просто создать пустой вектор и добавить каждый элемент в других векторах к пустому вектору, а затем использовать std :: sort и std :: unique для получения желаемого отсортированного объединения всех элементов.Тем не менее, я подумал, что было бы более эффективно выгрузить все векторные элементы в набор (method2), потому что наборы уже сделают их уникальными и отсортированными за один раз.К моему удивлению, method1 оказался в 5 раз быстрее, чем method2!Я что-то здесь не так делаю?не должен ли method2 быть быстрее, потому что он делает меньше вычислений?Заранее спасибо

//// method1 с векторами:

std::vector<long> arr1{5,12,32,33,34,50};
std::vector<long> arr2{1,2,3,4,5};
std::vector<long> arr3{1,8,9,11};

std::vector<long> arr;

int main(int argc, const char * argv[]) {

double sec;
clock_t t;
t=clock();
for(long j=0; j<1000000; j++){ // repeating for benchmark
    arr.clear();
    for(long i=0; i<arr1.size(); i++){
        arr.push_back(arr1[i]);
    }
    for(long i=0; i<arr2.size(); i++){
        arr.push_back(arr2[i]);
    }
    for(long i=0; i<arr3.size(); i++){
        arr.push_back(arr3[i]);
    }
    std::sort(arr.begin(), arr.end());
    auto last = std::unique(arr.begin(), arr.end());
    arr.erase(last, arr.end());
}
t=clock() - t;
sec = (double)t/CLOCKS_PER_SEC;
std::cout<<"seconds = "<< sec <<" clicks = " << t << std::endl;

return 0;
}

//// method2 с наборами:

std::vector<long> arr1{5,12,32,33,34,50};
std::vector<long> arr2{1,2,3,4,5};
std::vector<long> arr3{1,8,9,11};

std::set<long> arr;

int main(int argc, const char * argv[]) {

double sec;
clock_t t;
t=clock();
for(long j=0; j<1000000; j++){ //repeating for benchmark
    arr.clear();
    arr.insert(arr1.begin(), arr1.end());
    arr.insert(arr2.begin(), arr2.end());
    arr.insert(arr3.begin(), arr3.end());
}
t=clock() - t;
sec = (double)t/CLOCKS_PER_SEC;
std::cout<<"seconds = "<< sec <<" clicks = " << t << std::endl;

return 0;
}

Answer 1

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

Это объединяет в общей сложности N элементов K очередей за O (N log K).

Поскольку вы объединяете vector<int>, ваши очереди могут быть либо tuple<int, vector *> (текущая позиция и вектор), либо tuple<vector::const_iterator, vector::const_iterator> (текущая позиция и конец)

Answer 2

Вот как это делается с 2 векторами.Вы можете легко обобщить процесс на N векторов.

vector<int> v1{ 4, 8, 12, 16 };
vector<int> v2{ 2, 6, 10, 14 };

vector<int> merged;
merged.reserve(v1.size() + v2.size());

// An iterator on each vector
auto it1 = v1.begin();
auto it2 = v2.begin();

while (it1 != v1.end() && it2 != v2.end())
    {
    // Find the iterator that points to the smallest number.
    // Grab the value.
    // Advance the iterator, and repeat.

    if (*it1 < *it2)
        {
        if (merged.empty() || merged.back() < *it1)
            merged.push_back(*it1);
        ++it1;
        }
    else
        {
        if (merged.empty() || merged.back() < *it2)
            merged.push_back(*it2);
        ++it2;
        }
    }

while(it1 != v1.end())
    {
    merged.push_back(*it1);
    ++it1;
    }

while (it2 != v2.end())
    {
    merged.push_back(*it2);
    ++it2;
    }

// if you print out the values in 'merged', it gives the expected result
[2, 4, 6, 8, 10, 12, 14, 16]

... И вы можете обобщить следующее.Обратите внимание, что вспомогательная структура, содержащая и текущий и конечный итератор, будет более чистой, но идея остается прежней.

vector<int> v1{ 4, 8, 12, 16 };
vector<int> v2{ 2, 6, 10, 14 };
vector<int> v3{ 3, 7, 11, 15 };
vector<int> v4{ 0, 21};

vector<int> merged;
// reserve space accordingly...

using vectorIt = vector<int>::const_iterator;

vector<vectorIt> fwdIterators;
fwdIterators.push_back(v1.begin());
fwdIterators.push_back(v2.begin());
fwdIterators.push_back(v3.begin());
fwdIterators.push_back(v4.begin());
vector<vectorIt> endIterators;
endIterators.push_back(v1.end());
endIterators.push_back(v2.end());
endIterators.push_back(v3.end());
endIterators.push_back(v4.end());

while (!fwdIterators.empty())
    {
    // Find out which iterator carries the smallest value
    size_t index = 0;
    for (size_t i = 1; i < fwdIterators.size(); ++i)
        {
        if (*fwdIterators[i] < *fwdIterators[index])
            index = i;
        }

    if (merged.empty() || merged.back() < *fwdIterators[index])
        merged.push_back(*fwdIterators[index]);

    ++fwdIterators[index];
    if (fwdIterators[index] == endIterators[index])
        {
        fwdIterators.erase(fwdIterators.begin() + index);
        endIterators.erase(endIterators.begin() + index);
        }
    }

// again, merged contains the expected result
[0, 2, 3, 4, 6, 7, 8, 10, 11, 12, 14, 15, 16, 21]

... И, как некоторые отмечали, использование кучи было бы дажебыстрее

// Helper struct to make it more convenient
struct Entry
{
vector<int>::const_iterator fwdIt;
vector<int>::const_iterator endIt;

Entry(vector<int> const& v) : fwdIt(v.begin()), endIt(v.end()) {}
bool IsAlive() const { return fwdIt != endIt; }
bool operator< (Entry const& rhs) const { return *fwdIt > *rhs.fwdIt; }
};


int main()
{
vector<int> v1{ 4, 8, 12, 16 };
vector<int> v2{ 2, 6, 10, 14 };
vector<int> v3{ 3, 7, 11, 15 };
vector<int> v4{ 0, 21};

vector<int> merged;
merged.reserve(v1.size() + v2.size() + v3.size() + v4.size());

std::priority_queue<Entry> queue;
queue.push(Entry(v1));
queue.push(Entry(v2));
queue.push(Entry(v3));
queue.push(Entry(v4));

while (!queue.empty())
    {
    Entry tmp = queue.top();
    queue.pop();

    if (merged.empty() || merged.back() < *tmp.fwdIt)
        merged.push_back(*tmp.fwdIt);

    tmp.fwdIt++;

    if (tmp.IsAlive())
        queue.push(tmp);
    }

Это похоже на большое копирование объекта 'Entry', хотя, возможно, указатель на запись с правильной функцией сравнения был бы лучше для std :: priority_queue.