Важная информация
Показано с 1 по 3 из 3

Тема: Многопоточная быстрая сортировка Dev C++

  1. #1 Многопоточная быстрая сортировка Dev C++ 
    Новичок
    Регистрация
    16.11.2017
    Сообщений
    1
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    Очень нужна помощь! Написана программа быстрой сортировки массива (однопоточная и распараллелиная). Но нужно, что бы выводилось время счета разного объёма массива одним ядром и двумя ядрами (однопоточная программа). И время счета разного объёма массива 2 - мя потоками, 4 - мя потоками.

    Однопоточная:
    C++ Code:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <iostream>
    4. using namespace std;
    5.  
    6. // Функция быстрой сортировки
    7. void quickSort(int *numbers, int left, int right)
    8. {
    9. int pivot; // разрешающий элемент
    10. int l_hold = left; //левая граница
    11. int r_hold = right; // правая граница
    12. pivot = numbers[left];
    13. while (left < right) // пока границы не сомкнулись
    14. {
    15. while ((numbers[right] >= pivot) && (left < right))
    16. right--; // передвигаем правую границу пока элемент [right] больше разрешающего элемента [pivot]
    17. if (left != right) // если границы не сомкнулись
    18. {
    19. numbers[left] = numbers[right]; // передвигаем элемент [right] на место разрешающего
    20. left++; // сдвигаем левую границу вправо
    21. }
    22. while ((numbers[left] <= pivot) && (left < right))
    23. left++; // сдвигаем левую границу пока элемент [left] меньше разрешающего элемента [pivot]
    24. if (left != right) // если границы не сомкнулись
    25. {
    26. numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
    27. right--; // сдвигаем правую границу вправо
    28. }
    29. }
    30. numbers[left] = pivot; // ставим разрешающий элемент на место
    31. pivot = left;
    32. left = l_hold;
    33. right = r_hold;
    34. if (left < pivot) // рекурсивно вызываем сортировку для левой и правой части массива
    35. quickSort(numbers, left, pivot - 1);
    36. if (right > pivot)
    37. quickSort(numbers, pivot + 1, right);
    38. }
    39. int main()
    40. {
    41. int n;
    42. int a[n];
    43. // заполнение массива случайными числами
    44. cin>>n;
    45. for (int i = 0; i<n; i++)
    46. a[i] = rand() % 20 - 10;
    47. // вывод элементов массива до сортировки
    48. for (int i = 0; i<n; i++)
    49. printf("%d ", a[i]);
    50. printf("\n");
    51. quickSort(a, 0, 9); // вызов функции сортировки
    52. // вывод элементов массива после сортировки
    53. for (int i = 0; i<n; i++)
    54. printf("%d ", a[i]);
    55. printf("\n");
    56. getchar();
    57. return 0;
    58. }




    Распараллелиная:
    C++ Code:
    1. #include <stdio.h>
    2. #include <stdlib.h>
    3. #include <omp.h>
    4. #include <iostream>
    5. using namespace std;
    6.  
    7. // Функция быстрой сортировки
    8. void quickSort(int *numbers, int left, int right)
    9. {
    10. int pivot; // разрешающий элемент
    11. int l_hold = left; //левая граница
    12. int r_hold = right; // правая граница
    13. pivot = numbers[left];
    14.  
    15.  
    16. #pragma omp parallel num_threads(2)
    17. {
    18.  
    19. while (left < right) // пока границы не сомкнулись
    20. {
    21. while ((numbers[right] >= pivot) && (left < right))
    22. right--; // передвигаем правую границу пока элемент [right] больше разрешающего элемента [pivot]
    23. if (left != right) // если границы не сомкнулись
    24. {
    25. numbers[left] = numbers[right]; // передвигаем элемент [right] на место разрешающего
    26. left++; // сдвигаем левую границу вправо
    27. }
    28. while ((numbers[left] <= pivot) && (left < right))
    29. left++; // сдвигаем левую границу пока элемент [left] меньше разрешающего элемента [pivot]
    30. if (left != right) // если границы не сомкнулись
    31. {
    32. numbers[right] = numbers[left]; // перемещаем элемент [left] на место [right]
    33. right--; // сдвигаем правую границу вправо
    34. }
    35. }
    36. numbers[left] = pivot; // ставим разрешающий элемент на место
    37. pivot = left;
    38. left = l_hold;
    39. right = r_hold;
    40. if (left < pivot) // рекурсивно вызываем сортировку для левой и правой части массива
    41. quickSort(numbers, left, pivot - 1);
    42. if (right > pivot)
    43. quickSort(numbers, pivot + 1, right);
    44. }
    45. }
    46.  
    47. int main()
    48. {
    49. int n;
    50. int a[n];
    51. // заполнение массива случайными числами
    52. cin>>n;
    53. #pragma omp parallel for
    54. for (int i = 0; i<n; i++)
    55. a[i] = rand() % 20 - 10;
    56. // вывод элементов массива до сортировки
    57. #pragma omp parallel for
    58. for (int i = 0; i<n; i++)
    59. printf("%d ", a[i]);
    60. printf("\n");
    61. quickSort(a, 0, 9); // вызов функции сортировки
    62. // вывод элементов массива после сортировки
    63. #pragma omp parallel for
    64. for (int i = 0; i<n; i++)
    65. printf("%d ", a[i]);
    66. printf("\n");
    67. getchar();
    68. return 0;
    69. }
    Последний раз редактировалось rrrFer; 16.11.2017 в 12:19.
    Ответить с цитированием  
     

  2. #2  
    Admin
    Регистрация
    09.04.2014
    Сообщений
    1,220
    Сказал(а) спасибо
    781
    Поблагодарили 493 раз(а) в 405 сообщениях
    Там есть специальные кнопки для ввода кода в сообщение...!!!
    Уважайте тех кто вам помогает...)
    Ответить с цитированием  
     

  3. #3  
    Профи Аватар для rrrFer
    Регистрация
    01.08.2013
    Сообщений
    561
    Сказал(а) спасибо
    34
    Поблагодарили 249 раз(а) в 164 сообщениях
    Абсолютно неправильно вы делаете. Неправильно все.

    1)
    Для начала (до того как замерять время) проверьте что программа вообще работает. Посмотрите какие данные вводятся.
    C++ Code:
    1. #pragma omp parallel for
    2. for (int i = 0; i<n; i++)
    3.   a[i] = rand() % 20 - 10;


    У вас массив генерируется очень специфический. В нем очень много числе будут одинаковыми. rand так устроен, что я бы не запехивал его в parallel.

    2) беру я вашу программу. Последовательную. Компилирую, запускаю, получаю:
    > g++ main.cpp -o main
    > ./main
    10
    -7 -4
    Ошибка сегментирования
    >
    10 - это то. что я ввел. А вот дальше - она упала. Пока падает последовательная - заниматься распараллеливанием вообще смысла нет.
    Упала вот почему:
    C++ Code:
    1. int n;
    2. int a[n];
    3. cin>>n;


    В переменной n хранится мусор после запуска программы, однако именно после запуска под массив a[n] должна выделиться память. Сколько же памяти выделится?

    Должно быть
    C++ Code:
    1. int *a;
    2. cin >> n;
    3. a = new int[n];


    Или типа того.

    3) алгоритм... у меня не вызывает доверия. Я не копался в нем, но выглядит подозрительно. Опять же, чтобы проверить что программа работает верно неплохо бы иметь возможность числа руками вводить, а не только их случайно генерировать.

    4) вы глобально не понимаете суть распараллеливания. Надо ведь не просто создать кучу потоков, а надо еще и задачи между ними разделить. Вы сделали так:
    C++ Code:
    1. #pragma omp parallel num_threads(2)
    2. {
    3. // весь цикл и рекурсивные вызовы сортировки
    4. }


    Т.е. у вас создается два потока и блин каждый из них начинает целиком обрабатывать массив. Причем массив один и тот же. В зависимости от скорости работы потоков у вас может что-то ломаться (гонки потоков называется).

    5) более правильно было бы создавать потоки для правой и левой частей массива (рекурсивных вызовов):
    C++ Code:
    1. if (left < pivot)
    2.   quickSort(numbers, left, pivot - 1);
    3. if (right > pivot)
    4.   quickSort(numbers, pivot + 1, right);
    5. }


    Так, чтобы эти вызовы выполнялись в разных потоках. Это например. Но у вас то проблема еще и том, что функция рекурсивная. Т.е. вы ее вызовете из главного потока, массив разделится на 2 части, каждая из которых обрабатывается в своем потоке. каждый из этих потоков опять разделяет массив и создает еще 2 потока (выходит у вас уже 4 потока). Каждый из 4х потоков создает еще 2 потока... Для массива из 1000 элементов вы создадите в районе 1000 (или 500 в зависимости от реализации) потоков.

    Такое поведение будет в OpenMP если вложенный параллелизм включен по крайней мере.

    Правильное решение этой задачи использует параллельные задачи (потоки при этом берутся из пула). Решение описано тут: [Ссылки могут видеть только зарегистрированные пользователи. ] (там как раз ваш пример с быстрой сортировкой, но коварный препод, который писал ту статью специально допустил там коварную ошибку, ищите).

    6) Вывод массива на экран у вас тоже неправильный xD

    C++ Code:
    1. #pragma omp parallel for
    2. for (int i = 0; i<n; i++)
    3.   printf("%d ", a[i]);


    Терминал, на который вы выводите один. А потоков много. Если даже массив отсортирован - на экране будет каша, т.к. несколько потоков выводят параллельно.

    Это же как helloworld:

    C++ Code:
    1. #pragma omp parallel
    2. {
    3. cout << "hello" << " " << "world" << endl;
    4. }


    Госпади, сколько ошибок. Параллельное программирование это реально так сложно и непонятно ))
    [Ссылки могут видеть только зарегистрированные пользователи. ] // программирование на Prolog, Erlang, C++
    Ответить с цитированием  
     

  4. 2 пользователя(ей) сказали cпасибо:

    >Quiet Snow< (17.11.2017), Free Admin (17.11.2017)

Информация о теме
Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Ответов: 8
    Последнее сообщение: 14.09.2018, 16:04
  2. Ответов: 1
    Последнее сообщение: 04.03.2016, 11:24
  3. указатели и сортировка
    от anshelika в разделе C/C++
    Ответов: 1
    Последнее сообщение: 07.01.2014, 21:34
  4. Ответов: 4
    Последнее сообщение: 01.04.2012, 10:08
  5. Ответов: 7
    Последнее сообщение: 09.12.2011, 16:06
Ваши права
  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •