Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.76/25: Рейтинг темы: голосов - 25, средняя оценка - 4.76
5 / 4 / 4
Регистрация: 08.07.2014
Сообщений: 38
1

Многопоточная сортировка

21.11.2016, 22:10. Показов 4715. Ответов 5
Метки нет (Все метки)

Здравствуйте, форумчане. Решаю задачу обработки данных большого размера 1 гб . Данные нужно отсортировать по возрастанию за ограниченное время - 1минута. Алгоритм выбрал слияние. Пытаюсь использовать многопоточность. но никак не догоняю, в примере кода ниже мной реализован алгоритм слияния в один поток и алгоритм слияния в 2 потока. Я разбил данные на две части один поток обрабатывает одну половину, другой другую. По итогом два потока проигрывают одному, что я делаю не так?


C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
#include <iostream>
#include <fstream>
#include <random>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <thread>
 
#define ARRAY_SIZE  1111*10000
 
char Random(int min, int max)
{
    return min + rand()%(max-min);
}
 
void createFile(const char* file_name, std::ofstream* out_stream, int size_file, int min, int max)
{
    out_stream->open(file_name);
    for (int i = 0; i < size_file; ++i) {
         *out_stream << Random(min,max);
    }
 
 
    out_stream->close();
}
 
 
void readFile(char* get_data, int length, const char* file_name, std::ifstream* in_stream)
{
    int i = 0;
    in_stream->open(file_name);
    if (in_stream)
            // пока не конец файла
            while (!in_stream->eof())
            {
                //int read_value;
                // если переменная считана успешно
               *in_stream >> get_data++;
                    // вывод считанной переменной на экран
                    //cout << get_data++ << endl;
                i++;
            }
        // закрытие потока
        in_stream->close();
}
 
void Merge(char *A, int first, int last)
{
    int middle, start, final, j;
    char *mas=new char[ARRAY_SIZE];
    middle=(first+last)/2; //вычисление среднего элемента
    start=first; //начало левой части
    final=middle+1; //начало правой части
    for(j=first; j<=last; j++) //выполнять от начала до конца
    {
        if ((start<=middle) && ((final>last) || (A[start]<A[final])))
        {
            mas[j]=A[start];
            start++;
        }
        else
        {
            mas[j]=A[final];
            final++;
        }
    }
//возвращение результата в список
        for (j=first; j<=last; j++) A[j]=mas[j];
        delete[]mas;
}
//рекурсивная процедура сортировки
void MergeSort(char *A, int first, int last)
{
 
    if (first<last)
    {
        MergeSort(A, first, (first+last)/2); //сортировка левой части
        MergeSort(A, (first+last)/2+1, last); //сортировка правой части
        Merge(A, first, last); //слияние двух частей
    }
}
 
 
void printArr(char* arr, int length, int count_column)
{
    int a = 0;
    for (int i = 0; i < length; ++i)
    {
        if (a == count_column)
        {
            std::cout<<std::endl;
            a = 0;
        }
        std::cout<<(int)arr[i]<<" " ;
        a++;
    };
}
 
 
 
void MergeSortL(char *A, int first, int last)
{
 
    if (first<last)
    {
        MergeSort(A, first, (first+last)/2); //сортировка левой части
        //MergeSort(A, (first+last)/2+1, last); //сортировка правой части
        Merge(A, first, last); //слияние двух частей
    }
}
 
 
void MergeSortR(char *A, int first, int last)
{
 
    if (first<last)
    {
        //MergeSort(A, first, (first+last)/2); //сортировка левой части
        MergeSort(A, (first+last)/2+1, last); //сортировка правой части
        Merge(A, first, last); //слияние двух частей
    }
}
 
int main()
{
 
    std::ofstream out_stream;
    std::ifstream in_stream;
    const char* file_name = "data2.txt";
    createFile(file_name, &out_stream,ARRAY_SIZE, 0, 255);
    clock_t t;
    cout << "Begin" << endl;
    t = clock();
    char* buffer = new char[ARRAY_SIZE];
    readFile(buffer,ARRAY_SIZE,file_name,&in_stream);
    MergeSort(buffer,0 ,ARRAY_SIZE - 1);
    t = clock() - t;
   std::cout.setf(std::ios::fixed);
   std::cout.precision(8);
   std::cout<<"\n Time -> "<<(float)t/CLOCKS_PER_SEC<<std::endl;
   //printArr(buffer, ARRAY_SIZE, 20);
   std::cout<<std::endl << "End" << endl;
 
    cout << "Begin" << endl;
    t = clock();
    readFile(buffer,ARRAY_SIZE,file_name,&in_stream);
    buffer = new char[ARRAY_SIZE];
    std::thread threadL(MergeSort,std::ref(buffer),0,(ARRAY_SIZE/2));
    threadL.join();;
    std::thread threadR(MergeSort,std::ref(buffer),((ARRAY_SIZE)/2)+1,ARRAY_SIZE-1);
    threadR.join();
 
    Merge(buffer,0, ARRAY_SIZE-1);
 
    t = clock() - t;
    std::cout.setf(std::ios::fixed);
    std::cout.precision(8);
    std::cout<<"\n Time -> "<<(float)t/CLOCKS_PER_SEC<<std::endl;
 
    //printArr(buffer, ARRAY_SIZE, 20);
 
    std::cout<<std::endl << "End" << endl;
    return 0;
}
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
21.11.2016, 22:10
Ответы с готовыми решениями:

Многопоточная сортировка Шелла
Задача стоит в том, что надо создать массив чисел, разделить его на две части, в разных потоках...

Многопоточная сортировка: синхронизация
Добрый день, только начал изучать параллельное программирование и решил написать параллельную...

Многопоточная сортировка Шелла не делится потоки
Здравствуйте! Мне нужно сделать многопоточную сортировку методом Шелла с визуализацией работы...

Многопоточная быстрая сортировка (уменьшить время работы)
#include &quot;pch.h&quot; #include &lt;iostream&gt; #include&lt;stdio.h&gt; #include&lt;ctime&gt; #include&lt;vector&gt;...

5
223 / 213 / 80
Регистрация: 26.04.2013
Сообщений: 972
22.11.2016, 01:20 2
C++
1
char *mas=new char[ARRAY_SIZE];
DmitryBond, ты уверен, что всегда нужно именно ARRAY_SIZE элементов??? Особенно, когда ты работаешь с 2 потоками...

Добавлено через 10 минут
P.S. Я правильно понял, что ты отсортировываешь символы по возрастанию? Если так, то мне кажется, что проще завести map<char, size_t>, считать файл посимвольно, увеличивать счётчик элемента, а потом вывести ключи с учётом их количества вхождений.
1
nd2
3419 / 2799 / 1251
Регистрация: 29.01.2016
Сообщений: 9,426
22.11.2016, 02:30 3
Цитата Сообщение от DmitryBond Посмотреть сообщение
что я делаю не так?
Цитата Сообщение от DmitryBond Посмотреть сообщение
C++
1
2
3
4
std::thread threadL(MergeSort,std::ref(buffer),0,(ARRAY_SIZE/2)); 
threadL.join();; 
std::thread threadR(MergeSort,std::ref(buffer),((ARRAY_SIZE)/2)+1,ARRAY_SIZE-1); 
threadR.join();
C++
1
2
3
4
    std::thread threadL(MergeSort,std::ref(buffer),0,(ARRAY_SIZE/2));
    std::thread threadR(MergeSort,std::ref(buffer),((ARRAY_SIZE)/2)+1,ARRAY_SIZE-1);
    threadL.join();
    threadR.join();
Добавлено через 8 минут
Или так:
C++
1
2
3
    std::thread threadL(MergeSort,std::ref(buffer),0,(ARRAY_SIZE/2));
    MergeSort(buffer, ((ARRAY_SIZE)/2)+1,ARRAY_SIZE-1);
    threadL.join();
1
5 / 4 / 4
Регистрация: 08.07.2014
Сообщений: 38
22.11.2016, 15:58  [ТС] 4
Да всё правильно сортирую по возрастанию. Можно использовать map, это не так важно, но главное это скорость, данных 1 гб, я использую сортировку слиянием, сортировка происходит за 10 минут, а нужно, используя многопоточность, отсортировать за 1 минуту.
0
Don't worry, be happy
17205 / 10083 / 1945
Регистрация: 27.09.2012
Сообщений: 25,158
Записей в блоге: 1
22.11.2016, 17:04 5
Лучший ответ Сообщение было отмечено DmitryBond как решение

Решение

Попробуйте так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <thread>
#include <algorithm>
#include <vector>
 
 
 
 
int main()
{
    std::vector<int> vec {9, 5, 4, 3, 2, 4, 5, 8, 0, 5, 3, 8, 2, 9};
    auto middle = vec.begin() + (vec.end() - vec.begin()) / 2;
    std::thread th(std::sort<decltype(middle)>, vec.begin(), middle);
    std::sort(middle, vec.end());
    th.join();
    std::inplace_merge(vec.begin(), middle, vec.end());
    //std::inplace_merge(std::execution::par, vec.begin(), middle, vec.end());//Параллельная версия из C++17
    for (auto e: vec) {
        std::cout << e << " ";
    }
}
http://rextester.com/PAINR75022
Добавьте код автоматического определения количества потоков
для лучшей параллельности на заданной платформе.

P.S. В C++17 должна быть и многопоточная версия sort.
1
5 / 4 / 4
Регистрация: 08.07.2014
Сообщений: 38
22.11.2016, 23:41  [ТС] 6
Спасибо. Хороший пример выигрывает у моего больше чем на минуту. Но все равно по времени не укладываюсь.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.11.2016, 23:41

многопоточная программа
есть вот такая программа-при нажатии символа, добавляет его справа(1-ая операция); при нажатии...

Многопоточная работа программы
К сожалению, не могу сам разобраться с многопоточкой, перепробовал множество путей - отсебятина,...

Многопоточная оптимизация клеточного автомата
Здравствуйте, товарищи программисты. Я пишу клеточный автомат, и он работает очень медленно....

Многопоточная программа, thread не поддерживается моим компилятором
Библиотека theard не поддерживается моим компилятором.Компилятор g++ 4.9.3.Как узнать поддерживает...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.