На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
  
> Медленно работает параллельная сортировка
    Функция shelly работает дольше, чем schell (хотя использование потоков по идее должно уменьшать время работы). Или я использую не объективный способ измерения времени выполнения?
    ExpandedWrap disabled
      #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;
      }
      Цитата xux @
      Функция shelly работает дольше, чем schell (хотя использование потоков по идее должно уменьшать время работы).

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


      Рейтинг@Mail.ru
      [ Script execution time: 0,0309 ]   [ 17 queries used ]   [ Generated: 19.03.24, 03:28 GMT ]