Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.04.2019, 14:11   #1
Tpai
 
Регистрация: 09.06.2018
Сообщений: 9
По умолчанию Медленно работает параллельная сортировка Шелла.

Функция shelly работает дольше, чем schell (хотя использование потоков по идее должно уменьшать время работы). Или я использую не объективный способ измерения времени выполнения?
Код:
#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;
}
Tpai вне форума Ответить с цитированием
Старый 10.04.2019, 16:53   #2
Black Fregat
Программист
Участник клуба
 
Аватар для Black Fregat
 
Регистрация: 23.06.2009
Сообщений: 1,772
По умолчанию

Цитата:
Сообщение от Tpai Посмотреть сообщение
использование потоков по идее должно уменьшать время работы
Это неправильная идея. Использование потоков может уменьшать время, а может и увеличивать. Ведь само по себе создание потоков, их синхронизация и прочая обвязка тоже требуют времени. Иногда оно окупается получаемым выигрышем. А иногда нет.
Black Fregat вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Медленно работает. Вадим Вергун Помощь студентам 3 24.12.2014 18:48
параллельная сортировка бетчера kella4ka Общие вопросы C/C++ 0 31.05.2011 16:05
Параллельная сортировка. JSort Общие вопросы по Java, Java SE, Kotlin 0 09.03.2011 17:21
Сервер работает медленно kuzyakiev PHP 9 06.08.2010 14:36
Почему ХОR работает медленно? Иллидан Помощь студентам 5 01.05.2008 14:51