Форум программистов, компьютерный форум, киберфорум
С под Linux
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.56/9: Рейтинг темы: голосов - 9, средняя оценка - 4.56
65 / 37 / 3
Регистрация: 30.11.2011
Сообщений: 109
1

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

28.09.2013, 00:45. Показов 1724. Ответов 3
Метки нет (Все метки)

Собственно, думаю сделать так : разделить исходный массив на подмассивы и отсортировать их в отдельных потоках сортировкой Шелла,а затем слить отсортированные подмассивы сортировкой слияния в основном потоке(разбивать планирую на 4 подмассива,поэтому нужно будет 3 раза вызывать сортировку слияния),возможно ли при таком алгоритме получить улучшение в скорости работы по сравнению с однопоточной сортировкой?

если нет,то какие варианты действий имеются,чтобы прирост скорости был?

p.s. - если у кого есть ссылки хорошие по поводу реализации пула потоков и с чем это едят - большая просьба предоставить
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
28.09.2013, 00:45
Ответы с готовыми решениями:

Многопоточная сортировка Шелла с применением процессов
Собственно,что я вообще делаю : сначала разделяю исходный массив на 4 подмассива,далее в главном...

Многопоточная сортировка
У меня есть текстовый файл, в нем хранится массив значений, мне нужно считать данные из файла,...

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

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

3
919 / 636 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
28.09.2013, 12:55 2
Цитата Сообщение от greenEYE Посмотреть сообщение
Собственно, думаю сделать так : разделить исходный массив на подмассивы и отсортировать их в отдельных потоках сортировкой Шелла,а затем слить отсортированные подмассивы сортировкой слияния в основном потоке(разбивать планирую на 4 подмассива,поэтому нужно будет 3 раза вызывать сортировку слияния),возможно ли при таком алгоритме получить улучшение в скорости работы по сравнению с однопоточной сортировкой?
При достаточно большом размере - однозначно Да. Слияние происходит значительо быстрее сортировки шелла. Тем более, и здесь два слияния можно запустить в разных потоках.
1
65 / 37 / 3
Регистрация: 30.11.2011
Сообщений: 109
28.09.2013, 23:26  [ТС] 3
в общем пробую для начала разбить массив исходный на 4 подмассива,отсортировать и просто вывести отсортированные куски в файл,
cначала вроде всё заработало,осталось только режим открытия файла для записи поменять,а то старое содержимое стирал,вроде поменял только режим этот и ничего больше не трогал,но gcc стал выдавать "ошибка сегментирования(сделан дамп памяти)"
помогите отыскать ошибку :

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
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <pthread.h>
#include <semaphore.h>
 
#define PART_SIZE 10
#define GLOBAL_SIZE 40
 
typedef struct
{
    int *mass;
    int count;
} workpart;
 
void *shellSort(void *args);
void readFromFile(const char* filename,int *array1,int *array2,int *array3,int *array4,size_t size);
void writeToFile(const char* filename, int* array, size_t size);
void workPartInit(workpart part,int *array);
 
//sem_t bin_sem;
 
int main(int argc, const char* argv[])
{
    int threadc,res;
    int *array = (int*)malloc(sizeof(int) * GLOBAL_SIZE);
    void *thread_result;
 
    int arr1[PART_SIZE],arr2[PART_SIZE],arr3[PART_SIZE],arr4[PART_SIZE];
    workpart workpart_1,workpart_2,workpart_3,workpart_4;
    pthread_t thread_1,thread_2,thread_3,thread_4;
 
    if (argc != 4)
    {
        printf("Udage: program <INPUT FILE> <OUTPUT FILE> <THREAD COUNT>\n");
        exit(EXIT_FAILURE);
    }
 
    threadc = atoi(argv[3]);
 
    readFromFile(argv[1],arr1,arr2,arr3,arr4,GLOBAL_SIZE);
    workPartInit(workpart_1,arr1);
    workPartInit(workpart_2,arr2);
    workPartInit(workpart_3,arr3);
    workPartInit(workpart_4,arr4);
 
   /* res = sem_init(&bin_sem,0,0);
    if(res != 0)
    {
        perror("Semaphore init failed");
        exit(EXIT_FAILURE);
    } */
 
    res = pthread_create(&thread_1,NULL,shellSort,(void *)&workpart_1);
    if(res != 0)
    {
        perror("1st thread creation failed");
        exit(EXIT_FAILURE);
    }
 
    res = pthread_create(&thread_2,NULL,shellSort,(void *)&workpart_2);
    if(res != 0)
    {
        perror("2nd thread creation failed");
        exit(EXIT_FAILURE);
    }
 
    res = pthread_create(&thread_3,NULL,shellSort,(void *)&workpart_3);
    if(res != 0)
    {
        perror("3rd thread creation failed");
        exit(EXIT_FAILURE);
    }
 
    res = pthread_create(&thread_4,NULL,shellSort,(void *)&workpart_4);
    if(res != 0)
    {
        perror("4th thread creation failed");
        exit(EXIT_FAILURE);
    }
    printf("Program: All threads were created\n");
 
    res = pthread_join(thread_1,&thread_result);
    if(res != 0)
    {
        perror("1st thread join failed");
        exit(EXIT_FAILURE);
    }
    printf("Program: %s\n",(char *)thread_result);
 
    res = pthread_join(thread_2,&thread_result);
    if(res != 0)
    {
        perror("2nd thread join failed");
        exit(EXIT_FAILURE);
    }
    printf("Program: %s\n",(char *)thread_result);
 
    res = pthread_join(thread_3,&thread_result);
    if(res != 0)
    {
        perror("3rd thread join failed");
        exit(EXIT_FAILURE);
    }
    printf("Program: %s\n",(char *)thread_result);
 
    res = pthread_join(thread_4,&thread_result);
    if(res != 0)
    {
        perror("4th thread join failed");
        exit(EXIT_FAILURE);
    }
    printf("Program: %s\n",(char *)thread_result);
 
    writeToFile(argv[2], arr1, PART_SIZE);
    writeToFile(argv[2], arr2, PART_SIZE);
    writeToFile(argv[2], arr3, PART_SIZE);
    writeToFile(argv[2], arr4, PART_SIZE);
    printf("Program: Sort complete! Check your output file\n");
    free(array);
 
    return EXIT_SUCCESS;
}
 
void workPartInit(workpart curpart,int *array)
{
    curpart.mass = array;
    curpart.count = PART_SIZE;
}
 
void *shellSort(void *curworkpart)
{
    int n = ((workpart *)curworkpart)->count;
    int *a = ((workpart *)curworkpart)->mass;
 
    int step = n / 2;
    int j;
 
    while (step > 0)
    {
        int i = step;
        for (; i < n - step; i++)
        {
            j = i;
            while ((j >= 0) && (a[j]) > a[j + step])
            {
                int buf = a[j];
                a[j] = a[j + step];
                a[j + step] = buf;
                j--;
            }
        }
        step /= 2;
    }
    pthread_exit("Thread exit");
}
 
void readFromFile(const char* filename,int *array1,int *array2,int *array3,int *array4,size_t size)
{
    FILE* fo;
    fo = fopen(filename, "r");
    int i = 1;
 
    if (fo == 0)
    {
        perror(filename);
        exit(EXIT_FAILURE);
    }
 
    while (size--)
    {
        if(i <= 10)
            fscanf(fo, "%d", array1++);
        if(i >= 11 && i <= 20)
            fscanf(fo, "%d", array2++);
        if(i >= 21 && i <= 30)
            fscanf(fo, "%d", array3++);
        if(i >= 31 && i <= 40)
            fscanf(fo, "%d", array4++);
        i++;
    }
 
    fclose(fo);
}
 
void writeToFile(const char* filename, int* array, size_t size)
{
    FILE* fo;
    fo = fopen(filename, "r+");
 
    if (fo == 0)
    {
        perror(filename);
        exit(EXIT_FAILURE);
    }
 
    while (size--)
    {
        fprintf(fo, "%d ", *array++);
    }
 
    fclose(fo);
}
Добавлено через 4 часа 8 минут
обнаружил,что при считывании в массивы с файла считывалась фигня - исправил

обваливание программы происходит,когда пытаюсь в shellSort,когда идёт обращение к массиву
0
919 / 636 / 198
Регистрация: 08.09.2013
Сообщений: 1,693
28.09.2013, 23:57 4
Функцию shellSort оставил вашу.
main наспех написал, так как достаточно трудно разобраться в коде.
Проверил для 400 случайных целых чисел. Вроде бы сортирует в четыре потока правильно. Слияние не писал.
Первым числом в исходном файле стоит количество чисел. Дальше сами числа.
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
main () {
  FILE *f= fopen ("infile", "rt");
  if (!f) {
    printf ("can not open file %s\n", "infile");
    return -1;
  }
  int n, i, j;
  fscanf (f, "%d", &n);
  int *in= malloc (n * sizeof(int));
  if (!in) {
    printf ("can not allocate memory\n");
    return -1;
  }
  for (i= 0; i < n; i++) fscanf (f, "%d", in+i);
  fclose (f);
  workpart wp[4];
  pthread_t thr[4];
  for (i=0; i < 4; i++) {
    wp[i].data= in + n/4*i;
    wp[i].count= (i<3) ? n/4 : n - n/4*3;
    if (pthread_create(&thr[i], NULL, shellSort,( void *)&wp[i])) {
      printf ("thread %d creation failed", i);
      return -1;
    }
  }
  for (i=0; i < 4; i++) if (pthread_join (thr[i], NULL)) {
    printf ("thread %d join failed", i);
    return -1;
  }
  f= fopen ("outfile", "w");
  if (!f) {
    printf ("can not create file %s", "outfile");
    return -1;
  }
  fprintf (f, "%d\n", n);
  for (i=0; i < 4; i++) for (j=0; j < wp[i].count; j++)
    fprintf (f, "%d\n", wp[i].data[j]);
  fclose (f);
  free (in);
}
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.09.2013, 23:57

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

Многопоточная сортировка
У меня есть текстовый файл, в нем хранится массив значений, мне нужно считать данные из файла,...

Сортировка Шелла. Написал программу, не могу понять, почему сортировка не выполняется
Программа создает динамический массив с рандомным заполнением. Дальше выбор сортировок, пузырьком...

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


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru