Я пишу функцию для рекурсивного объединения двух массивов с использованием многопоточности в C ++.
#include <algorithm>
#include <iostream>
#include <thread>
#include <iterator>
#include <string>
#include <vector>
template <typename Iter>
Iter binsearch(Iter begin, Iter end, Iter value)
{
Iter L = begin, R = end;
while (L < R)
{
Iter m = std::next(L, std::distance(L, R)/2);
if (*m < *value)
L = m + 1;
else
R = m;
}
return L;
}
template <typename Iter>
void Merge(Iter lbegin, Iter lend, Iter rbegin, Iter rend, Iter dest){
auto size1 = std::distance(lbegin, lend);
auto size2 = std::distance(rbegin, rend);
while (size1 > 0 && size2 > 0)
{
if (*lbegin < *rbegin)
{
*dest = *lbegin;
lbegin++;
size1--;
}
else
{
*dest = *rbegin;
rbegin++;
size2--;
}
dest++;
}
if (size1 > 0)
std::copy(lbegin, lend, dest);
if (size2 > 0)
std::copy(rbegin, rend, dest);
}
template <typename Iter>
void parallel_merge(Iter lbegin, Iter lend, Iter rbegin, Iter rend, Iter dest,
size_t num_threads){
int m = std::distance(lbegin, lend);
int n = std::distance(rbegin, rend);
std::cout << "Thread id = " << std::this_thread::get_id() << std::endl;
std::cout << "m = " << m << ", n = " << n << std::endl;
if(num_threads <= 1)
{
Merge<Iter>(lbegin, lend, rbegin, rend, dest);
return;
}
if (m <= 0)
return;
Iter r, s, t;
if(m >= n)
{
r = std::next(lbegin, m/2);
s = binsearch(rbegin, rend, r);
t = dest + (r - lbegin) + (s - rbegin);
}
else
{
r = std::next(rbegin, n/2);
s = binsearch(lbegin, lend, r);
t = dest + (r - rbegin) + (s - lbegin);
}
*t = *r;
Iter new_dest = t;
std::cout << "r = " << *r << " s = " << *s << " t = " << *t << std::endl;
std::thread t1(parallel_merge<Iter>, lbegin, r, rbegin, s,
std::ref(dest), num_threads/2);
std::thread t2(parallel_merge<Iter>, r + 1, lend, s + 1, rend,
std::ref(new_dest), num_threads - (num_threads/2));
t1.join();
t2.join();
}
int main(int argc, char *argv[]) {
std::vector<long double> from_one_to_10;
for (size_t i = 0; i < 10; ++i) {
from_one_to_10.push_back(i + 1);
}
std::vector<long double> from_11_to_twenty;
for (size_t i = 10; i < 20 ; i++) {
from_11_to_twenty.push_back(i + 1);
}
std::vector<long double> merged(20);
std::vector<long double>::iterator it = merged.begin();
parallel_merge<std::vector<long double>::iterator>
(from_one_to_10.begin(), from_one_to_10.end(), from_11_to_twenty.begin(),
from_11_to_twenty.end(), it, 4);
std::cout << "One TO Ten Vector" << std::endl;
for (auto i = from_one_to_10.begin(); i != from_one_to_10.end(); ++i)
std::cout << *i << " ";
std::cout << std::endl;
std::cout << "Eleven TO Twenty Vector" << std::endl;
for (auto i = from_11_to_twenty.begin(); i != from_11_to_twenty.end(); ++i)
std::cout << *i << " ";
std::cout << std::endl;
std::cout << "Merged Vector" << std::endl;
for (auto i = merged.begin(); i != merged.end(); ++i)
std::cout << *i << " ";
std::cout << std::endl;
}
Почему-то я получаю странные значения в объединенном значении. В частности, вот как выглядит объединенный вектор в одном исполнении приведенного выше кода.
Объединенный вектор
1 2 3 4 5 6 7 8 9 10 8.38396e-4950 0 6.30394e -4932 1.81284e-4863 6.30394e-4932 0 6.30394e-4932 1.81284e-4863 6.30394e-4932 6.56136e-4950
Я не уверен, где я иду не так, любые указания будут очень признательны.