Версия для печати
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум на Исходниках.RU > C/C++: Общие вопросы > Медленно работает параллельная сортировка


Автор: xux 10.04.19, 11:18
Функция shelly работает дольше, чем schell (хотя использование потоков по идее должно уменьшать время работы). Или я использую не объективный способ измерения времени выполнения?
<{CODE_COLLAPSE_OFF}><{CODE_WRAP_OFF}>
    #include <iostream>
    #include <vector>
    #include <array>
    #include <thread>
    #include <cmath>
    #include <mutex>
    #include <ctime>
    #include <chrono>
    using namespace std;/*
                        template <class T> class my_array;
                        template <class T>
                        void vn(int k, my_array<T> * th);*/
    template <class T> class my_array {
        T* veca;
        int gr;
        int tre;
        int adt;
        mutex g;
        int* adt2;
    public:
        my_array(T* veca1, int size) {
            veca = new T[size];
            for (int i = 0; i < size; i++)
                veca[i] = veca1[i];
            gr = size;
        };
        T operator[] (int n) {
            return veca[n];
        }
        void vn(int b)
        {
            int j, i;
            T t;
            int k = gr / 2;
            int er = 1;
            for (i = k + b; i < gr; i += adt)
            {
                t = veca[i];
                for (j = i; j >= k; j -= k)
                {
                    if (t < veca[j - k]) {
                        veca[j] = veca[j - k];
                    }
                    else {
                        break;
                    }
                }
                veca[j] = t;
            }
            g.lock();
            adt2[0]--;
            g.unlock();
            for (k /= 2; k > adt; k /= 2) {
                while (1) {
                    g.lock();
                    if (adt2[er - 1] == 0) {
                        g.unlock();
                        break;
                    }
                    g.unlock();
                }
                for (i = k + b; i < gr; i += adt)
                {
                    t = veca[i];
                    for (j = i; j >= k; j -= k)
                    {
                        if (t < veca[j - k]) {
                            veca[j] = veca[j - k];
                        }
                        else {
                            break;
                        }
                    }
                    veca[j] = t;
                }
                g.lock();
                adt2[er]--;
                g.unlock();
                er++;
            }
            if (b == 0) {
                for (; k > b + 1; k /= 2, er++) {
                    while (1) {
                        g.lock();
                        if (adt2[er - 1] == 0) {
                            g.unlock();
                            break;
                        }
                        g.unlock();
                    }
                    for (i = k + b; i < gr; i += k)
                    {
                        t = veca[i];
                        for (j = i; j >= k; j -= k)
                        {
                            if (t < veca[j - k]) {
                                veca[j] = veca[j - k];
                            }
                            else {
                                break;
                            }
                        }
                        veca[j] = t;
                    }
                    g.lock();
                    adt2[er]--;
                    g.unlock();
                }
                while (1) {
                    g.lock();
                    if (adt2[er - 1] == 0) {
                        g.unlock();
                        break;
                    }
                    g.unlock();
                }
                for (i = 1 + b; i < gr; i++)
                {
                    t = veca[i];
                    for (j = i; j >= 1; j--)
                    {
                        if (t < veca[j - 1]) {
                            veca[j] = veca[j - 1];
                        }
                        else {
                            break;
                        }
                    }
                    veca[j] = t;
                }
            }
            else {
                for (; k > b; k /= 2, er++) {
                    while (1) {
                        g.lock();
                        if (adt2[er - 1] == 0) {
                            g.unlock();
                            break;
                        }
                        g.unlock();
                    }
                    for (i = k + b; i < gr; i += k)
                    {
                        t = veca[i];
                        for (j = i; j >= k; j -= k)
                        {
                            if (t < veca[j - k]) {
                                veca[j] = veca[j - k];
                            }
                            else {
                                break;
                            }
                        }
                        veca[j] = t;
                    }
                    g.lock();
                    adt2[er]--;
                    g.unlock();
                }
            }
        }
        //friend void vn <>(int k, my_array<T> * th);
        void shelly(void) {
            int maxx = thread::hardware_concurrency();
            adt = gr / 2;
            (maxx < adt) ? (adt = maxx) : 1;
            int hyt = log2(gr) - 1;
            adt2 = new int[hyt];
            thread * te = new thread[adt - 1];
            for (int uy = gr / 2, i = 0; i < hyt; i++, uy /= 2) {
                adt2[i] = (adt < uy) ? adt : uy;
            }
            for (int b = 0; b < adt - 1; b++) {
                te[b] = thread(&my_array::vn, this, b);
            }
            vn(adt - 1);
            for (int b = 0; b < adt - 1; b++)
                te[b].join();
            delete[] adt2;
            delete[] te;
        };
        void schell(void) {
            int i, j, k;
            T t;
            for (k = gr / 2; k > 0; k /= 2) {
                for (i = k; i < gr; i++)
                {
                    t = veca[i];
                    for (j = i; j >= k; j -= k)
                    {
                        if (t < veca[j - k])
                            veca[j] = veca[j - k];
                        else
                            break;
                    }
                    veca[j] = t;
                }
            }
        };
        ~my_array() {
            delete[] veca;
        };
    };
    /*
    template <class TT> void vn(int b, my_array<TT> * th)
    {
    int j, i;
    TT t;
     
    for (int k = adt; k > b; k /= 2) {
    for (i = k + b; i < gr; i += k)
    {
    g[i].lock();
    t = veca[i];
    g[i].unlock();
    for (j = i; j >= k; j -= k)
    {
    if (t < veca[j - k]) {
    g[j].lock();
    g[j - k].lock();
    veca[j] = veca[j - k];
    g[j].unlock();
    g[j - k].unlock();
    }
    else
    break;
    }
    g[j].lock();
    veca[j] = t;
    g[j].unlock();
    }
    }
    }
    */
    int main()
    {
        double* hhh;
        hhh = new double[28];
        for (int i = 0; i < 28; i++) {
            hhh[i] = rand();
        }
        my_array <double> jhu(hhh, 28);
        auto start = chrono::steady_clock::now();
        jhu.shelly();
        auto end = chrono::steady_clock::now();
        int elapsed_seconds = chrono::duration_cast<chrono::microseconds>(end - start).count();
        cout << elapsed_seconds << endl;
        for (int i = 0; i < 28; i++) {
            cout << jhu[i] << " ";
        }
        return 0;
    }

Автор: Олег М 10.04.19, 12:35
Цитата xux @
Функция shelly работает дольше, чем schell (хотя использование потоков по идее должно уменьшать время работы).

Что-то у тебя эти функции совсем не одну и ту же работу делают.
Потоки, конечно, уменьшают время работы, но если при этом добавить кучу блокировок и прочих накладных расходов типа выделения памяти, то скорее будет медленнее.
Оставь один поток и посмотри - если всё реализовано правильно то он должен отработать практически также как schell() минус время на создание потока.

Powered by Invision Power Board (https://www.invisionboard.com)
© Invision Power Services (https://www.invisionpower.com)