Почему объединенный массив имеет странные значения? - PullRequest
0 голосов
/ 30 апреля 2020

Я пишу функцию для рекурсивного объединения двух массивов с использованием многопоточности в 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

Я не уверен, где я иду не так, любые указания будут очень признательны.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...