Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.94
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 727
#1

Многопоточность при сортировке массивов - C++

13.04.2014, 22:11. Просмотров 2552. Ответов 84
Метки нет (Все метки)

Уважаемые, столкнулся с ситуацией, имею 3 массива, содержимое которых одинаково (координаты точек в 3д пространстве), произвожу сортировку каждого массива по определенному измерению (x, y, z), хотел спросить, можно ли как-то ускорить процесс, возникла идея многопоточности (т.е. одновременно выполнять сортировку 3-х массивов), но я не уверен что я корректно мыслю т.к. не разу не сталкивался с многопоточностью, подскажите как правильно ?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.04.2014, 22:11
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Многопоточность при сортировке массивов (C++):

Не могу найти ошибку при сортировке массивов - C++
Даны два числа n и m и два упорядоченных по неубыванию массива A<=A<=....<=A и B<=B<=....<=B. Образовать из элементов этих массивов новый...

Почему программа падает при сортировке массивов больших размерностей - C++
Добрый день! Подскажите почему прога крашится при размере массива 10000, при значении 1000 все прекрасно работает. #include <iostream> ...

Задача по сортировке массивов - C++
Используя метод сортировки выбором, переставить элементы так, чтобы непарные элементы оставались на своих местах, а парные стояли по...

Ошибка при сортировке - C++
При сортировке массива вылетает причем именно на последнем числе сортирую так : for (int i=0;i<count;i++) { if (a>a) { ...

Ошибка при сортировке пузырьком - C++
Видимо выход за предел массива, не пойму где ошибка #include <iostream> #include <ctime> #include <cstdlib> using...

Ошибка при сортировке Шелла - C++
Сортирую массив, вношу в него 46 элементов случайных значений в диапазоне от 1 до 26, после сортирую методом Шелла, но выдает ошибку, не...

84
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 727
15.04.2014, 09:38  [ТС] #31
ну вот я сделал небольшое приложение, вот код:
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
#include "stdafx.h"
#include <iostream>
#include <D3DX11.h>
#include <xnamath.h>
#include <vector>
#include "kdTree.h"
 
 
int _tmain(int argc, _TCHAR* argv[])
{
    int num = 262144;
    photon *p = new photon[num];
    for(int i = 0; i < num; i++)
    {
        p[i].pos.x = rand()%20-10;
        p[i].pos.y = rand()%20-10;
        p[i].pos.z = rand()%20-10;
    }
    DWORD start = GetTickCount();
    std::cout<<"num:"<<num;
    std::cout<<"\nStart at :"<<start;
    kdTree tr(p, num);
    DWORD end = GetTickCount();
    std::cout<<"\nend at:"<<end;
    std::cout<<"\ntime:"<<(end-start)/1000.f<<" s";
    char a;
    std::cin>>a;
    return 0;
}
код заголовочника kdTree.h:
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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
#include <thread>
 
using namespace std;
 
struct nodePhoton
{
    XMFLOAT4 pos;
    float energy;
    int r;
    int l;
    int k;
};
 
struct photon 
{
    XMFLOAT4 pos;
    float energy;
};
 
class nodeKdTree
{
    public:
    nodeKdTree *right;
    nodeKdTree *left;
    int rNum;
    int lNum;
    int numInArr;
    photon pht;
    int key;//1 - x 2 - y 3 - z
    void CreateTree(photon *p, nodePhoton *newP, int num, int iStart, int rootIndex, int iBranch);
};
void qSortX(photon *p, int e);
void qSortY(photon *p, int e);
void qSortZ(photon *p, int e);
 
void nodeKdTree::CreateTree(photon *p, nodePhoton *newP, int num, int iStart, int rootIndex, int iBranch)
{
    if(num == 1)
    {
        this->pht = p[0];
        newP[iStart].pos = p[0].pos;
        newP[iStart].energy = p[0].energy;
        newP[iStart].l = -1;
        newP[iStart].r = -1;
        if(iBranch == 1)
            newP[rootIndex].r = iStart;
        else
            newP[rootIndex].l = iStart;
        this->left = NULL;
        this->right = NULL;
        this->key = 0;
        this->lNum = 0;
        this->rNum = 0;
        this->numInArr = 0;
        return;
    }
    photon *x = new photon[num];
    photon *y = new photon[num];
    photon *z = new photon[num];
 
    std::memcpy(x, p,sizeof(photon)*num);
    std::memcpy(y, p,sizeof(photon)*num);
    std::memcpy(z, p,sizeof(photon)*num);
 
    std::thread th1(qSortX, x, num-1);
    std::thread th2(qSortY, y, num-1);
    std::thread th3(qSortZ, z, num-1);
 
    th1.join();
    th2.join();
    th3.join();
    //qSortX(x, num-1);
    //qSortY(y, num-1);
    //qSortZ(z, num-1);
 
 
 
    int dx = abs(x[0].pos.x - x[num-1].pos.x);
    int dy = abs(y[0].pos.y - y[num-1].pos.y);
    int dz = abs(z[0].pos.z - z[num-1].pos.z);
    this->left = new nodeKdTree();
    this->right = new nodeKdTree();
 
 
    int newIndex(-1);
    if((dx > dy && dx > dz) || (dx == dy && dx > dz) || (dx == dz && dx > dy))
    {
        int m = num/2;
        this->numInArr = m;
        int lnum;
        int rnum;
        this->pht = x[m];
        newIndex = iStart+m;
        newP[newIndex].pos = x[m].pos;
        newP[newIndex].energy = x[m].energy;
        if(iBranch == 1)
            newP[rootIndex].r = newIndex;
        if(iBranch == -1)
            newP[rootIndex].l = newIndex;
        if(rootIndex == -1)
        {
            newP[newIndex].l = -1;
            newP[newIndex].r = -1;
        }
        newP[newIndex].k = 1;
        this->key = 1;
        lnum = m;
        photon *lx = new photon[lnum];
        std::memcpy(lx, x, sizeof(photon)*lnum);
        photon *rx;
        if(num%2)
        {
            rnum = m;
            rx = new photon[rnum];
            std::memcpy(rx, x+m+1, sizeof(photon)*rnum);
        }
        else
        {
            rnum = num-m-1;
            if(rnum > 0)
            {
                rx = new photon[rnum];
                std::memcpy(rx, x+m+1, sizeof(photon)*rnum);
            }
        }
        this->left->CreateTree(lx, newP, lnum, iStart, newIndex, -1);
        delete []lx;
        this->lNum = lnum;
        this->rNum = rnum;
        if(rnum > 0)
        {
            this->right->CreateTree(rx, newP, rnum, newIndex+1, newIndex, 1);
            delete []rx;
        }
    }
    else
        if((dy > dx && dy > dz) || (dy == dz && dy > dx))
        {
            int m = num/2;
            this->numInArr = m;
            int lnum;
            int rnum;
            this->pht = y[m];
            newIndex = iStart+m;
            newP[newIndex].pos = y[m].pos;
            newP[newIndex].energy = y[m].energy;
            if(iBranch == 1)
                newP[rootIndex].r = newIndex;
            if(iBranch == -1)
                newP[rootIndex].l = newIndex;
            if(rootIndex == -1)
            {
                newP[newIndex].l = -1;
                newP[newIndex].r = -1;
            }
            newP[newIndex].k = 2;
            this->key = 2;
            lnum = m;
            photon *ly = new photon[lnum];
            std::memcpy(ly, y, sizeof(photon)*lnum);
            photon *ry;
            if(num%2)
            {
                rnum = m;
                ry = new photon[rnum];
                std::memcpy(ry, y+m+1, sizeof(photon)*rnum);
            }
            else
            {
                rnum = num-m-1;
                if(rnum > 0)
                {
                    ry = new photon[rnum];
                    std::memcpy(ry, y+m+1, sizeof(photon)*rnum);
                }
            }
            this->left->CreateTree(ly, newP, lnum, iStart, newIndex, -1);
            delete []ly;
            this->lNum = lnum;
            this->rNum = rnum;
            if(rnum > 0)
            {
                this->right->CreateTree(ry, newP, rnum, newIndex+1, newIndex, 1);
                delete []ry;
            }
        }
        else
            {
                int m = num/2;
                this->numInArr = m;
                int lnum;
                int rnum;
                this->pht = z[m];
                newIndex = iStart+m;
                newP[newIndex].pos = z[m].pos;
                newP[newIndex].energy = z[m].energy;
                if(iBranch == 1)
                    newP[rootIndex].r = newIndex;
                if(iBranch == -1)
                    newP[rootIndex].l = newIndex;
                if(rootIndex == -1)
                {
                    newP[newIndex].l = -1;
                    newP[newIndex].r = -1;
                }
                newP[newIndex].k = 3;
                this->key = 3;
                lnum = m;
                photon *lz = new photon[lnum];
                std::memcpy(lz, z, sizeof(photon)*lnum);
                photon *rz;
                if(num%2)
                {
                        rnum = m;
                        rz = new photon[rnum];
                        std::memcpy(rz, z+m+1, sizeof(photon)*rnum);
                }
                else
                {
                    rnum = num-m-1;
                    if(rnum > 0)
                    {
                        rz = new photon[rnum];
                        std::memcpy(rz, z+m+1, sizeof(photon)*rnum);
                    }
                }
                this->left->CreateTree(lz, newP, lnum, iStart, newIndex, -1);
                delete []lz;
                this->lNum = lnum;
                this->rNum = rnum;
                if(rnum > 0)
                {
                    this->right->CreateTree(rz, newP,  rnum, newIndex+1, newIndex, 1);
                    delete []rz;
                }
            }
    return;
}
 
class kdTree
{
private:
    nodeKdTree root;
    photon *p;
    nodePhoton *newP;
    int num;
public:
    int GetNum();
    nodePhoton* GetPointer();
    kdTree(photon *p, int n);
    ~kdTree();
};
 
nodePhoton* kdTree::GetPointer()
{
    return newP;
}
 
int kdTree::GetNum()
{
    return num;
}
 
kdTree::kdTree(photon *p, int n)
{
    num = n;
    kdTree::p = new photon[n];
    kdTree::newP = new nodePhoton[n];
    std::memcpy(kdTree::p, p, sizeof(photon)*n);
    kdTree::root.CreateTree(p, newP, n, 0, -1, 0);
}
 
kdTree::~kdTree()
{
 
}
 
void qSortZ(photon *p, int e)
{
    int b = 0;
    vector<XMFLOAT2> stack;
    float ind = p[e].pos.z;
    int sI = e;
    int j = e-1;
    bool s(0);
 
    do
    {
        for(int i = b; i < e; i++)
        {
            j = e-1;
            ind = p[e].pos.z;
            if(p[i].pos.z >= ind)
            {
                while(p[j].pos.z >= ind && j > i)
                {
                    j--;
                }
                if(j > i)
                {
                    photon a = p[i];
                    p[i] = p[j];
                    p[j] = a;
                    sI = i+1;
                }
                else
                    break;
            }
        }
        for(int i = b; i <= e; i++)
        {
            if(p[i].pos.z >= ind)
            {
                photon a = p[i];
                p[i] = p[e];
                p[e] = a;
                sI = i;
                if(e - i > 1)
                    stack.push_back(XMFLOAT2(sI+1, e));
                break;
            }
        }
 
        if(sI-b <= 1 && stack.size() > 0)
        {
            b = stack[stack.size()-1].x;
            e = stack[stack.size()-1].y;
            stack.pop_back();
            continue;
        }
 
        e = sI - 1;
 
 
    }while(e-b >= 1 || stack.size() != 0);
}
 
void qSortY(photon *p, int e)
{
    int b = 0;
    vector<XMFLOAT2> stack;
    float ind = p[e].pos.y;
    int sI = e;
    int j = e-1;
    bool s(0);
 
    do
    {
        for(int i = b; i < e; i++)
        {
            j = e-1;
            ind = p[e].pos.y;
            if(p[i].pos.y >= ind)
            {
                while(p[j].pos.y >= ind && j > i)
                {
                    j--;
                }
                if(j > i)
                {
                    photon a = p[i];
                    p[i] = p[j];
                    p[j] = a;
                    sI = i+1;
                }
                else
                    break;
            }
        }
        for(int i = b; i <= e; i++)
        {
            if(p[i].pos.y >= ind)
            {
                photon a = p[i];
                p[i] = p[e];
                p[e] = a;
                sI = i;
                if(e - i > 1)
                    stack.push_back(XMFLOAT2(sI+1, e));
                break;
            }
        }
 
        if(sI-b <= 1 && stack.size() > 0)
        {
            b = stack[stack.size()-1].x;
            e = stack[stack.size()-1].y;
            stack.pop_back();
            continue;
        }
 
        e = sI - 1;
 
 
    }while(e-b >= 1 || stack.size() != 0);
}
 
 
void qSortX(photon *p, int e)
{
    int b = 0;
    vector<XMFLOAT2> stack;
    float ind = p[e].pos.x;
    int sI = e;
    int j = e-1;
    bool s(0);
 
    do
    {
        for(int i = b; i < e; i++)
        {
            j = e-1;
            ind = p[e].pos.x;
            if(p[i].pos.x >= ind)
            {
                while(p[j].pos.x >= ind && j > i)
                {
                    j--;
                }
                if(j > i)
                {
                    photon a = p[i];
                    p[i] = p[j];
                    p[j] = a;
                    sI = i+1;
                }
                else
                    break;
            }
        }
        for(int i = b; i <= e; i++)
        {
            if(p[i].pos.x >= ind)
            {
                photon a = p[i];
                p[i] = p[e];
                p[e] = a;
                sI = i;
                if(e - i > 1)
                    stack.push_back(XMFLOAT2(sI+1, e));
                break;
            }
        }
 
        if(sI-b <= 1 && stack.size() > 0)
        {
            b = stack[stack.size()-1].x;
            e = stack[stack.size()-1].y;
            stack.pop_back();
            continue;
        }
 
        e = sI - 1;
 
 
    }while(e-b >= 1 || stack.size() != 0);
}
при использовании потоков затраченное время около 319 секунд, при обычной сортировке время около 55 с

Добавлено через 15 минут
но при
том я замерял время на сортировку массивов, если сортировать одним потоком то уходит около 34с если 3-мя потоками то около 25 с.
0
newbie666
Заблокирован
15.04.2014, 10:03 #32

Не по теме:

игру делаешь? В зависимости от случая, для чего тебе нужна эта сортировка, можно задействовать GPU (DirectCompute / CUDA), будет в разы, а то и в десятки раз быстрее, всё зависит от наличия последней архитектуры Kepler на твоей видеокарте


ладно, ща гляну твой супер софт
0
newbie666
Заблокирован
15.04.2014, 10:35 #33
ты что то гонишь, у меня на моём дохлом ноутбуке в 3-х потоках получился примерно 16-и кратный профит!!! Хотя я даже профайлер не дождался до конца, может он глюканул, запустил ещё пару раз отдельно на другом компе - в 3-х потоках судя по твоему счётчику в консоли было ~180 секуд, в 3-х потоках - ~60 секунд.
0
Миниатюры
Многопоточность при сортировке массивов  
newbie666
Заблокирован
15.04.2014, 10:36 #34
а вообще это полнейший гавнокод
0
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 727
15.04.2014, 11:50  [ТС] #35
знаю

Добавлено через 7 минут
Цитата Сообщение от newbie666 Посмотреть сообщение
в 3-х потоках судя по твоему счётчику в консоли было ~180 секуд, в 3-х потоках - ~60 секунд.
это как ?

Добавлено через 1 час 3 минуты
ладно в принципе не важно, если я хочу в качестве функции у потока указать метод класса, то ничем это не будет отличаться от обычной функции ?
0
newbie666
Заблокирован
15.04.2014, 12:17 #36
Цитата Сообщение от NEvOl Посмотреть сообщение
если я хочу в качестве функции у потока указать метод класса, то ничем это не будет отличаться от обычной функции ?
если догадаешься как получить у указатель на функцию класса для её вставки в качестве поточной функции
0
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 727
15.04.2014, 13:12  [ТС] #37
проблема решена, а как можно пересоздать поток, т.е. создали поток кинули ему функцию и параметры, он отработал, теперь нужно опять с этой же функцией только с другими параметрами, или только новый поток создавать ?
0
newbie666
Заблокирован
15.04.2014, 13:44 #38
Цитата Сообщение от NEvOl Посмотреть сообщение
он отработал
если он отработал - он закрылся, значит только новый, но в принципе можешь сделать три потока постоянных со своим евент лупом каким - нибуть и слать в него сообщения с данными для обработки периодический, это сложнее...
1
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 727
15.04.2014, 16:37  [ТС] #39
возник еще вопрос, поток начинает свою работу сразу после объявления ?
0
newbie666
Заблокирован
15.04.2014, 16:40 #40
Цитата Сообщение от NEvOl Посмотреть сообщение
возник еще вопрос, поток начинает свою работу сразу после объявления ?
Сразу после его создания, то есть если через стандарт, то потоковая функция вызывается сразу после:
std::thread th1(qSortX, x, num-1); , в случае WinApi - сразу после CreateThread.
А вообще мог бы такие нубские вопросы не задавать, что тебе мешало поставить брейкпоинт в потоковую функцию и посмотреть, когда она вызывается
1
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 727
15.04.2014, 22:12  [ТС] #41
все, таки я не могу успокоиться)) почему-то у меня при 3-х потоках программа выполняется около 300с, а при одном потоке всего 30с, что за фигня я не могу понять %)
0
newbie666
Заблокирован
15.04.2014, 22:42 #42
Цитата Сообщение от NEvOl Посмотреть сообщение
все, таки я не могу успокоиться)) почему-то у меня при 3-х потоках программа выполняется около 300с, а при одном потоке всего 30с, что за фигня я не могу понять %)
просто интересно, а какой у тебя CPU?
на самом деле, тут всё совсем не просто, есть такие вещи, как эксклюзивные процессорные такты, memory caolescing и многое другое. Для оптимального параллелизма код должен быть заточен под это.

Даю тебе следующее задание. Напиши не из своего кода, а просто отдельные маленький пример с сортировкой, чтоб этот код был в строчек 10...15, чтоб удобно его изучать было и сам проверь на нём и сюда выложи. Посмотрим. Например, три вектора, которые надо отсортировать.
0
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 727
16.04.2014, 10:53  [ТС] #43
так ну вот я написал в консольке:
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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
// ConsoleApplication1.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <D3DX11.h>
#include <vector>
#include <xnamath.h>
#include <thread>
 
using namespace std;
 
struct photon 
{
    XMFLOAT4 pos;
};
 
void qSortX(photon *p, int e);
void qSortY(photon *p, int e);
void qSortZ(photon *p, int e);
 
int _tmain(int argc, _TCHAR* argv[])
{
    int num = 250000;
    bool thr(0);
    photon *p = new photon[num];
    photon *x = new photon[num];
    photon *y = new photon[num];
    photon *z = new photon[num];
    for(int i = 0; i < num; i++)
    {
        p[i].pos.x = rand()%20-10;
        p[i].pos.y = rand()%20-10;
        p[i].pos.z = rand()%20-10;
    }
    DWORD start = GetTickCount();
    std::cout<<"num:"<<num;
    cout<<endl<<"enter type threed";
    cin>>thr;
    std::cout<<"\nStart at :"<<start;
    if(thr)
    {
        cout<<endl<<"threed - 3";
        std::thread h1(qSortX, x, num-1);
        std::thread h2(qSortX, x, num-1);
        std::thread h3(qSortX, x, num-1);
        h1.join();
        h2.join();
        h3.join();
    }
    else
    {
        cout<<endl<<"threed - 1";
        qSortX(x, num-1);
        qSortY(y, num-1);
        qSortZ(z, num-1);
    }
    DWORD end = GetTickCount();
    std::cout<<"\nend at:"<<end;
    std::cout<<"\ntime:"<<(end-start)/1000.f<<" s";
    char a;
    std::cin>>a;
    _tmain(argc, argv);
    return 0;
}
 
 
void qSortZ(photon *p, int e)
{
    int b = 0;
    vector<XMFLOAT2> stack;
    float ind = p[e].pos.z;
    int sI = e;
    int j = e-1;
    bool s(0);
 
    do
    {
        for(int i = b; i < e; i++)
        {
            j = e-1;
            ind = p[e].pos.z;
            if(p[i].pos.z >= ind)
            {
                while(p[j].pos.z >= ind && j > i)
                {
                    j--;
                }
                if(j > i)
                {
                    photon a = p[i];
                    p[i] = p[j];
                    p[j] = a;
                    sI = i+1;
                }
                else
                    break;
            }
        }
        for(int i = b; i <= e; i++)
        {
            if(p[i].pos.z >= ind)
            {
                photon a = p[i];
                p[i] = p[e];
                p[e] = a;
                sI = i;
                if(e - i > 1)
                    stack.push_back(XMFLOAT2(sI+1, e));
                break;
            }
        }
 
        if(sI-b <= 1 && stack.size() > 0)
        {
            b = stack[stack.size()-1].x;
            e = stack[stack.size()-1].y;
            stack.pop_back();
            continue;
        }
 
        e = sI - 1;
 
 
    }while(e-b >= 1 || stack.size() != 0);
}
 
void qSortY(photon *p, int e)
{
    int b = 0;
    vector<XMFLOAT2> stack;
    float ind = p[e].pos.y;
    int sI = e;
    int j = e-1;
    bool s(0);
 
    do
    {
        for(int i = b; i < e; i++)
        {
            j = e-1;
            ind = p[e].pos.y;
            if(p[i].pos.y >= ind)
            {
                while(p[j].pos.y >= ind && j > i)
                {
                    j--;
                }
                if(j > i)
                {
                    photon a = p[i];
                    p[i] = p[j];
                    p[j] = a;
                    sI = i+1;
                }
                else
                    break;
            }
        }
        for(int i = b; i <= e; i++)
        {
            if(p[i].pos.y >= ind)
            {
                photon a = p[i];
                p[i] = p[e];
                p[e] = a;
                sI = i;
                if(e - i > 1)
                    stack.push_back(XMFLOAT2(sI+1, e));
                break;
            }
        }
 
        if(sI-b <= 1 && stack.size() > 0)
        {
            b = stack[stack.size()-1].x;
            e = stack[stack.size()-1].y;
            stack.pop_back();
            continue;
        }
 
        e = sI - 1;
 
 
    }while(e-b >= 1 || stack.size() != 0);
}
 
 
void qSortX(photon *p, int e)
{
    int b = 0;
    vector<XMFLOAT2> stack;
    float ind = p[e].pos.x;
    int sI = e;
    int j = e-1;
    bool s(0);
 
    do
    {
        for(int i = b; i < e; i++)
        {
            j = e-1;
            ind = p[e].pos.x;
            if(p[i].pos.x >= ind)
            {
                while(p[j].pos.x >= ind && j > i)
                {
                    j--;
                }
                if(j > i)
                {
                    photon a = p[i];
                    p[i] = p[j];
                    p[j] = a;
                    sI = i+1;
                }
                else
                    break;
            }
        }
        for(int i = b; i <= e; i++)
        {
            if(p[i].pos.x >= ind)
            {
                photon a = p[i];
                p[i] = p[e];
                p[e] = a;
                sI = i;
                if(e - i > 1)
                    stack.push_back(XMFLOAT2(sI+1, e));
                break;
            }
        }
 
        if(sI-b <= 1 && stack.size() > 0)
        {
            b = stack[stack.size()-1].x;
            e = stack[stack.size()-1].y;
            stack.pop_back();
            continue;
        }
 
        e = sI - 1;
 
 
    }while(e-b >= 1 || stack.size() != 0);
}
функции сортировки использовал теже что и в прошлый раз, тут все работает адекватно, т.е. при сортировки 1-им потоком требуется около 130 с при сортировки 3-мя потоками требуется около 50 с, следовательно проблема в функции CreateTree, буду копать ее.
0
NEvOl
19 / 18 / 0
Регистрация: 13.08.2012
Сообщений: 727
18.04.2014, 11:02  [ТС] #44
хм... с сортировкой я вроде разобрался, действительно работает быстрее, но вот меня беспокоит функция создания kd дерева, в ней так же происходит сортировка массивов, если я использую 3 потока для сортировки то построение выполняется в разы медленнее чем когда одним потоком сортирую, код далек от совершенства, но рабочий, подскажите пожалуйста почему так ? при проверке показало что если использовать 3 потока для сортировки то времени уходит около 1000 секунд, а при использовании одного потока для сортировки всего 20 с, это у меня вообще в голове не укладывается как так ?
переделал немного код:
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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
void nodeKdTree::CreateTree(photon *p, nodePhoton *newP, int num, int iStart, int rootIndex, int iBranch, bool thr)
{
    if(num == 1)
    {
        this->pht = p[0];
        newP[iStart].pos = p[0].pos;
        newP[iStart].energy = p[0].energy;
        newP[iStart].l = -1;
        newP[iStart].r = -1;
        if(iBranch == 1)
            newP[rootIndex].r = iStart;
        else
            newP[rootIndex].l = iStart;
        this->left = NULL;
        this->right = NULL;
        this->key = 0;
        this->lNum = 0;
        this->rNum = 0;
        this->numInArr = 0;
        return;
    }
    photon *x = new photon[num];
    photon *y = new photon[num];
    photon *z = new photon[num];
 
    std::memcpy(x, p,sizeof(photon)*num);
    std::memcpy(y, p,sizeof(photon)*num);
    std::memcpy(z, p,sizeof(photon)*num);
 
    if(thr)
    {
        std::thread th1(qSortX, x, num-1);
        std::thread th2(qSortY, y, num-1);
        std::thread th3(qSortZ, z, num-1);
 
        th1.join();
        th2.join();
        th3.join();
    }
    else
    {
        qSortX(x, num-1);
        qSortY(y, num-1);
        qSortZ(z, num-1);
    }
 
    int dx = abs(x[0].pos.x - x[num-1].pos.x);
    int dy = abs(y[0].pos.y - y[num-1].pos.y);
    int dz = abs(z[0].pos.z - z[num-1].pos.z);
    this->left = new nodeKdTree();
    this->right = new nodeKdTree();
 
 
    int newIndex(-1);
    if((dx > dy && dx > dz) || (dx == dy && dx > dz) || (dx == dz && dx > dy))
    {
        int m = num/2;
        this->numInArr = m;
        int lnum;
        int rnum;
        this->pht = x[m];
        newIndex = iStart+m;
        newP[newIndex].pos = x[m].pos;
        newP[newIndex].energy = x[m].energy;
        if(iBranch == 1)
            newP[rootIndex].r = newIndex;
        if(iBranch == -1)
            newP[rootIndex].l = newIndex;
        if(rootIndex == -1)
        {
            newP[newIndex].l = -1;
            newP[newIndex].r = -1;
        }
        newP[newIndex].k = 1;
        this->key = 1;
        lnum = m;
        photon *lx = new photon[lnum];
        std::memcpy(lx, x, sizeof(photon)*lnum);
        photon *rx;
        if(num%2)
        {
            rnum = m;
            rx = new photon[rnum];
            std::memcpy(rx, x+m+1, sizeof(photon)*rnum);
        }
        else
        {
            rnum = num-m-1;
            if(rnum > 0)
            {
                rx = new photon[rnum];
                std::memcpy(rx, x+m+1, sizeof(photon)*rnum);
            }
        }
        this->left->CreateTree(lx, newP, lnum, iStart, newIndex, -1, thr);
        delete []lx;
        this->lNum = lnum;
        this->rNum = rnum;
        if(rnum > 0)
        {
            this->right->CreateTree(rx, newP, rnum, newIndex+1, newIndex, 1, thr);
            delete []rx;
        }
    }
    else
        if((dy > dx && dy > dz) || (dy == dz && dy > dx))
        {
            int m = num/2;
            this->numInArr = m;
            int lnum;
            int rnum;
            this->pht = y[m];
            newIndex = iStart+m;
            newP[newIndex].pos = y[m].pos;
            newP[newIndex].energy = y[m].energy;
            if(iBranch == 1)
                newP[rootIndex].r = newIndex;
            if(iBranch == -1)
                newP[rootIndex].l = newIndex;
            if(rootIndex == -1)
            {
                newP[newIndex].l = -1;
                newP[newIndex].r = -1;
            }
            newP[newIndex].k = 2;
            this->key = 2;
            lnum = m;
            photon *ly = new photon[lnum];
            std::memcpy(ly, y, sizeof(photon)*lnum);
            photon *ry;
            if(num%2)
            {
                rnum = m;
                ry = new photon[rnum];
                std::memcpy(ry, y+m+1, sizeof(photon)*rnum);
            }
            else
            {
                rnum = num-m-1;
                if(rnum > 0)
                {
                    ry = new photon[rnum];
                    std::memcpy(ry, y+m+1, sizeof(photon)*rnum);
                }
            }
            this->left->CreateTree(ly, newP, lnum, iStart, newIndex, -1, thr);
            delete []ly;
            this->lNum = lnum;
            this->rNum = rnum;
            if(rnum > 0)
            {
                this->right->CreateTree(ry, newP, rnum, newIndex+1, newIndex, 1, thr);
                delete []ry;
            }
        }
        else
            {
                int m = num/2;
                this->numInArr = m;
                int lnum;
                int rnum;
                this->pht = z[m];
                newIndex = iStart+m;
                newP[newIndex].pos = z[m].pos;
                newP[newIndex].energy = z[m].energy;
                if(iBranch == 1)
                    newP[rootIndex].r = newIndex;
                if(iBranch == -1)
                    newP[rootIndex].l = newIndex;
                if(rootIndex == -1)
                {
                    newP[newIndex].l = -1;
                    newP[newIndex].r = -1;
                }
                newP[newIndex].k = 3;
                this->key = 3;
                lnum = m;
                photon *lz = new photon[lnum];
                std::memcpy(lz, z, sizeof(photon)*lnum);
                photon *rz;
                if(num%2)
                {
                        rnum = m;
                        rz = new photon[rnum];
                        std::memcpy(rz, z+m+1, sizeof(photon)*rnum);
                }
                else
                {
                    rnum = num-m-1;
                    if(rnum > 0)
                    {
                        rz = new photon[rnum];
                        std::memcpy(rz, z+m+1, sizeof(photon)*rnum);
                    }
                }
                this->left->CreateTree(lz, newP, lnum, iStart, newIndex, -1, thr);
                delete []lz;
                this->lNum = lnum;
                this->rNum = rnum;
                if(rnum > 0)
                {
                    this->right->CreateTree(rz, newP,  rnum, newIndex+1, newIndex, 1, thr);
                    delete []rz;
                }
            }
    return;
}
 
void qSortZ(photon *p, int e)
{
    std::qsort(p, e+1, sizeof(photon), funcZ);
}
 
void qSortY(photon *p, int e)
{
    std::qsort(p, e+1, sizeof(photon), funcY);
}
 
 
void qSortX(photon *p, int e)
{
    std::qsort(p, e+1, sizeof(photon), funcX);
}
 
int funcX(const void* a, const void* b)
{
    if((*(photon*)a).pos.x > (*(photon*)b).pos.x)
        return 1;
    if((*(photon*)a).pos.x < (*(photon*)b).pos.x)
        return -1;
    return 0;
}
 
int funcY(const void* a, const void* b)
{
    if((*(photon*)a).pos.y > (*(photon*)b).pos.y)
        return 1;
    if((*(photon*)a).pos.y < (*(photon*)b).pos.y)
        return -1;
    return 0;
}
 
int funcZ(const void* a, const void* b)
{
    if((*(photon*)a).pos.z > (*(photon*)b).pos.z)
        return 1;
    if((*(photon*)a).pos.z < (*(photon*)b).pos.z)
        return -1;
    return 0;
}
пояснения:
в функцию передается исходный массив с координатами точек в 3D(p), новый массив который постепенно заполняется и представляет само kd дерево(newP), количество элементов в переданном массиве p (num), индекс начала переданного подмассива в исходном массиве p (iStart), индекс узла дерева чьи ветви рассчитываются в текущий момент в массиве newp (rootIndex), индекс правой - 1 и левой - -1 ветви (iBranch) и последним параметром является метод сортировки массивов 3-мя потоками или одним (thr). Суть функции заключается в том что сортируются координаты точек по 3-м осям (x, y, z) затем находится по какой из осей максимальное расстояние между крайними точками, массив разбивается на 2 части, центральный элемент сохраняется после этого остальные части массива (правая и левая) отправляются рекурсивно в эту же функцию и так пока весь массив не переберется. помогите пожалуйста разобраться.
0
newbie666
Заблокирован
18.04.2014, 11:46 #45
Ты в VisualStudio прогаешь? Запускай из меню ANALIZE->StartPerformenceAnalize и смотри, какая часть кода у тебя больше всего времени занимает... И вообще учись профайлерами пользоваться. Или выкладывай сюда архив с проектом и комментом - "ТУТ У МЕНЯ КОСЯК!!!! ЕСЛИ РАСКОМЕНТИТЬ ЭТИ СТРОЧКИ, ТО БУДЕТ НА МНОГО МЕДЛЕННЕЕ!"
0
18.04.2014, 11:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.04.2014, 11:46
Привет! Вот еще темы с ответами:

Использование массива индексов при сортировке - C++
Задали задачку отсортировать обычный одномерный массив. Так же, нужно использовать массив индексов, чтобы показать, как отсортирован...

Количество перестановок при сортировке массива - C++
Как вывести число количества перестановок после сортировки массива, допустим выбору?

Не совсем корректный вывод при сортировке - C++
В скриншоте видно что у меня с файла выводит имя цветка, цвет, количество цветов(этот параметр выводит как текстовое значение, хотя в файле...

Ошибка при сортировке двумерного массива по возрастанию - C++
По убыванию сортировка работает полноценно,а по возрастанию первое число НЕ понимаю откуда появляется :wall:. Помогите решить данную...


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

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

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