Форум программистов, компьютерный форум CyberForum.ru

Поиск min и max - C++

Восстановить пароль Регистрация
 
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
30.04.2014, 15:35     Поиск min и max #1
Здравствуйте, подскажите пожалуйста, есть ли встроенные функции С++ для поиска наименьшего и наибольшего элемента любого типа, знаю что есть в std::min_element но не знаю как привольно ей воспользоваться, вот код который у меня есть :
C++
1
2
3
4
5
6
struct ph
{
 XMFLOAT4 pos;
};
 
ph *p = new ph[num];
нужно в массиве p найти наименьший и наибольший элемент по каждой из осей (x, y, z, ось w не трогаем) причем очень быстро, так как num может иметь значение в 500 000 а все это дело необходимо еще делать в цикле с большим числом итераций, по-этому сортировка по каждой оси и выборка максимального и минимального элемента такие образом делается долго, нужно что-то быстрое, подскажите пожалуйста.
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ilot
Модератор
Эксперт С++
1765 / 1140 / 221
Регистрация: 16.05.2013
Сообщений: 3,017
Записей в блоге: 5
Завершенные тесты: 1
30.04.2014, 15:46     Поиск min и max #2
Цитата Сообщение от NEvOl Посмотреть сообщение
нужно в массиве p найти наименьший и наибольший элемент по каждой из осей (x, y, z, ось w не трогаем) причем очень быстро
Алгоритмы STL и так оптимизированны. Лучше пользоваться ими. В вашем случае:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <algorithm>  
...  
struct ph {
    XMFLOAT4 pos;
};
 
struct mycompare {
  bool operator() (ph& first,ph& last) { return first.pos < last.pos; }
} myobj;
 
...
ph *p = new ph[num];
...
min = std::min_element(p,p + num, myobj);
max = std::max_element(p,p + num, myobj);
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
30.04.2014, 21:35  [ТС]     Поиск min и max #3
блин все равно очень медленно получается, вот написал так:
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
for(int i = 0; i < num; i++)
            {
                int Cl = i;//число элементов в левом подмассиве
                int Cr = num-i-1;//число элементов в правом подмассив
                float ldx, ldy, ldz, Vl;
                if(Cl > 0)
                {
                    photon minx = *std::min_element(x, x+Cl, myobjx);//минимальный элемент левого подмассива по оси х
                    photon maxx = *std::max_element(x, x+Cl, myobjx);//максимальный элемент....
 
                    photon miny = *std::min_element(x, x+Cl, myobjy);//....
                    photon maxy = *std::max_element(x, x+Cl, myobjy);//....
 
                    photon minz = *std::min_element(x, x+Cl, myobjz);//....
                    photon maxz = *std::max_element(x, x+Cl, myobjz);//...
 
                    ldx = abs(minx.pos.x - maxx.pos.x);//находим максимальное расстояние между элементами по оси х
                    ldy = abs(miny.pos.y - maxy.pos.y);//...
                    ldz = abs(minz.pos.z - maxz.pos.z);//...
    
                    Vl = max(ldx,1)*max(ldy,1)*max(ldz,1);//находим объем
                }
                else
                    Vl = 0;
 
                float rdx, rdy, rdz, Vr;//идентичные действия с правым подмассивом
                if(Cr > 0)
                {
                    photon minx = *std::min_element(x+Cl+1, x+Cr, myobjx);
                    photon maxx = *std::max_element(x+Cl+1, x+Cr, myobjx);
 
                    photon miny = *std::min_element(x+Cl+1, x+Cr, myobjy);
                    photon maxy = *std::max_element(x+Cl+1, x+Cr, myobjy);
 
                    photon minz = *std::min_element(x+Cl+1, x+Cr, myobjz);
                    photon maxz = *std::max_element(x+Cl+1, x+Cr, myobjz);
 
                    rdx = abs(minx.pos.x - maxx.pos.x);
                    rdy = abs(miny.pos.y - maxy.pos.y);
                    rdz = abs(minz.pos.z - maxz.pos.z);
 
                    Vr = max(rdx,1)*max(rdy,1)*max(rdz,1);
                }
                else
                    Vr = 0;
                vvh a;
                a.ind = i;//считаем формулу и сохраняем
                float lVVh = ((Cl * Vl)/Vd);
                float rVVh = ((Cr * Vr)/Vd);
                a.VVH = 0+lVVh+rVVh;
                VVH.push_back(a);
            }
код работает, но недопустимо долго, подскажите пожалуйста как его можно оптимизировать, я как понимаю основное время занимает поиск минимальных и максимальных элементов ?

Добавлено через 4 часа 39 минут
замерил время выполнения одной итерации цикла выходит около 0.016 секунды, при условии что num будет равна 262000 на прохождение цикла уйдет почти целый час, как ускорить подскажите ?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
30.04.2014, 22:01     Поиск min и max #4
Про ускорение пока не понятно, но вот из кода:
C++
1
2
3
4
5
photon minx = *std::min_element(x, x+Cl, myobjx);
// ...
photon miny = *std::min_element(x, x+Cl, myobjy);
// ...
photon minz = *std::min_element(x, x+Cl, myobjz);
Оно делает-то то что нужно? Почему-то один и тот же массив, но три разных функтора, хотя должно быть, наверное, наоборот, семь пирогов и одна свеча. И что собой представляют myobjx, myobjy, myobjz?
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
30.04.2014, 22:17  [ТС]     Поиск min и max #5
grizlik78, да делает все правильно, вот функторы:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct mycomparex
{
    bool operator() (photon &f, photon &l)
    {
        return f.pos.x < l.pos.x;
    };
}myobjx;
 
struct mycomparey
{
    bool operator() (photon &f, photon &l)
    {
        return f.pos.y < l.pos.y;
    };
}myobjy;
 
struct mycomparez
{
    bool operator() (photon &f, photon &l)
    {
        return f.pos.z < l.pos.z;
    };
}myobjz;
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
30.04.2014, 23:07     Поиск min и max #6
Понятно, название массива сбивает с толку, у каждого элемента 3 координаты.
Следующий вопрос: внутри цикла по i содержимое массива x не меняется? Тогда для каждой из координат можно создать 4 массива: для мин и макс слева, и то же самое справа. Массив "слева" заполнить одним проходом от начала к концу, массив "справа" заполнить одним проходом от конца к началу. Тогда здесь стандартные алгоритмы ни к чему, надо просто сравнивать текущий элемент с текущими минимумом и максимумом, при необходимости обновлять и записывать в массивы. А уже после этого работать данным алгоритмом уже с этими массивами.

Добавлено через 46 минут
Громоздко, можно попробовать макросами утоптать или ещё как. Не проверялось, ибо неполный код.
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
std::vector<float> ldx(num), ldy(num), ldz(num);
std::vector<float> rdx(num), rdy(num), rdz(num);
for(int i = 0; i < num; i++)
{
    minx_l = maxx_l = x[0].pos.x;
    miny_l = maxy_l = x[0].pos.y;
    minz_l = maxz_l = x[0].pos.z;
    minx_r = maxx_r = x[num-1].pos.x;
    miny_r = maxy_r = x[num-1].pos.y;
    minz_r = maxz_r = x[num-1].pos.z;
    for(int i = 1; i < num; i++)
    {
        ldx[i] = maxx_l - minx_l;
        if (x[i].pos.x < minx_l)
            minx_l = x[i].pos.x;
        if (maxx_l < x[i].pos.x)
            maxx_l = x[i].pos.x;
 
        ldy[i] = maxy_l - miny_l;
        if (x[i].pos.y < miny_l)
            miny_l = x[i].pos.y;
        if (maxy_l < x[i].pos.y)
            maxy_l = x[i].pos.y;
 
        ldz[i] = maxz_l - minz_l;
        if (x[i].pos.z < minz_l)
            minz_l = x[i].pos.z;
        if (maxz_l < x[i].pos.z)
            maxz_l = x[i].pos.z;
 
        rdx[i] = maxx_r - minx_r;
        if (x[num-1-i].pos.x < minx_r)
            minx_r = x[num-1-i].pos.x;
        if (maxx_r < x[num-1-i].pos.x)
            maxx_r = x[num-1-i].pos.x;
 
        rdy[i] = maxy_r - miny_r;
        if (x[num-1-i].pos.y < miny_r)
            miny_r = x[num-1-i].pos.y;
        if (maxy_r < x[num-1-i].pos.y)
            maxy_r = x[num-1-i].pos.y;
 
        rdz[i] = maxz_r - minz_r;
        if (x[num-1-i].pos.z < minx_r)
            minz_r = x[num-1-i].pos.z;
        if (maxz_r < x[num-1-i].pos.z)
            maxz_r = x[num-1-i].pos.z;
    }
}
 
for(int i = 0; i < num; i++)
{
    int Cl = i;//число элементов в левом подмассиве
    int Cr = num-i-1;//число элементов в правом подмассив
    float Vl;
    if(Cl > 0)
    {
        Vl = max(ldx[Cl],1)*max(ldy[Cl],1)*max(ldz[Cl],1);//находим объем
    }
    else
        Vl = 0;
 
    float Vr;//идентичные действия с правым подмассивом
    if(Cr > 0)
    {
        Vr = max(rdx[Cr],1)*max(rdy[Cr],1)*max(rdz[Cr],1);
    }
    else
        Vr = 0;
    vvh a;
    a.ind = i;//считаем формулу и сохраняем
    float lVVh = ((Cl * Vl)/Vd);
    float rVVh = ((Cr * Vr)/Vd);
    a.VVH = 0+lVVh+rVVh;
    VVH.push_back(a);
}
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
01.05.2014, 12:50  [ТС]     Поиск min и max #7
grizlik78, что-то я не много не понял ваш метод, я пока сделал так:
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
qSortX(x, num-1);//сортирую массив х по возрастанию
for(int i = 0; i < num; i++)
            {
                if(i - 1 >= 0)
                {
                    ldx = x[i-1].pos.x - x[0].pos.x; //беру крайние элементы в подмассиве
                    if(ldx == 0)
                        ldx = 1;
                    float lminy, lmaxy, lminz, lmaxz;
                    lminy = lmaxy = x[0].pos.y;//осуществляю поиск минимального и максимального эелемнта в левом подмассиве
                    lminz = lmaxz = x[0].pos.z;
                    for(int j = 0; j < i; j++)
                    {
                        if(lminy > x[j].pos.y)
                            lminy = x[j].pos.y;
                        if(lmaxy < x[j].pos.y)
                            lmaxy = x[j].pos.y;
 
                        if(lminz > x[j].pos.z)
                            lminz = x[j].pos.z;
                        if(lmaxz < x[j].pos.z)
                            lmaxz = x[j].pos.z;
                    }
                    ldy = lmaxy-lminy;
                    if(ldy == 0)
                        ldy = 1;
                    ldz = lmaxz-lminz;
                    if(ldz == 0)
                        ldz = 1;
                }
                //тоже самое только для правого подмассива
                if(i + 1 < num)
                {
                    rdx = x[num-1].pos.x - x[i+1].pos.x;
                    if(rdx == 0)
                        rdx = 1;
                    float rminy, rmaxy, rminz, rmaxz;
                    rminy = rmaxy = x[0].pos.y;
                    rminz = rmaxz = x[0].pos.z;
                    for(int j = num-1; j > i; j--)
                    {
                        if(rminy > x[j].pos.y)
                            rminy = x[j].pos.y;
                        if(rmaxy < x[j].pos.y)
                            rmaxy = x[j].pos.y;
 
                        if(rminz > x[j].pos.z)
                            rminz = x[j].pos.z;
                        if(rmaxz < x[j].pos.z)
                            rmaxz = x[j].pos.z;
                    }
                    rdy = rmaxy-rminy;
                    if(rdy == 0)
                        rdy = 1;
                    rdz = rmaxz-rminz;
                    if(rdz == 0)
                        rdz = 1;
                }
                int Cl = i;
                int Cr = num - 1 - i;
 
                float Vl, Vr;
                if(Cl > 0)
                    Vl = ldx*ldy*ldz;
                else
                    Vl = 0;
 
                if(Cr > 0)
                    Vr = rdx * rdy * rdz;
                else
                    Vr = 0;
 
                vvh a;
                a.ind = i;
                a.VVH = ((Cl*Vl)/Vd) + ((Cr*Vr)/Vd); 
                VVH.push_back(a);
 
            }
при num = 262000 на все уходит около 5-ти минут, нужно еще быстрее...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
01.05.2014, 13:08     Поиск min и max #8
Мой код должен был делать вычисления, аналогичные посту #3, но сейчас, ещё раз посмотрев на #3 заметил сомнительное место.
Для левого подмассива:
C++
1
photon minx = *std::min_element(x, x+Cl, myobjx);
Тут понятно: от начала массива и до элемента с номером Cl, не включая его, всего Cl элементов.
Для правого:
C++
1
photon minx = *std::min_element(x+Cl+1, x+Cr, myobjx);
А тут непонятно. Мне подумалось, что должны проверяться элементы от Cl+1 до конца, всего Cr элементов. Но в коде не так. Правая граница всё время уменьшается и может стать левее левой. Разве это так задумано?
NEvOl
12 / 11 / 0
Регистрация: 13.08.2012
Сообщений: 616
01.05.2014, 13:38  [ТС]     Поиск min и max #9
grizlik78, да тут ошибка, должно быть так:
C++
1
photon minx = *std::min_element(x+Cl+1, x+num, myobjx);
т.е. получается от Cl+1 и до конца массива

Добавлено через 10 минут
вообще суть такова, имеется исходный массив в котором находятся координаты точек, мы должны разбить этот массивы на 2 подмассива (левый и правый) по определенной оси (в моем случае о оси x) и в каждом из подмассивов на основании координат точек должны посчитать объем ограничивающего этих точек бокса, пример:
исходный массив:
(0;0;0), (5;6;10), (-1;16;-3), (11;3;6), (-5;-1;7)
сортируем массив по оси x:
(-5;-1;7), (-1;16;-3), (0;0;0), (5;6;10), (11;3;6)
начинаем разбивать о очереди каждым элементом на 2 подмассива,
разбиваем первым элементом (-5;-1;7):
в левом подмассиве получаем 0, следовательно объем 0
правый подмассив:
(-1;16;-3), (0;0;0), (5;6;10), (11;3;6)
максимальная дистанция по оси х равна 11 - (-1) = 12
теперь ищем максимальную дистанцию по си y и z:
по оси y: 16 - 0 = 16
по оси z: 10 - (-3) = 13
ограничивающий объем равен 12*16*13,
следующая итерация
делим исходный массив 2-ым элементом (-1;16;-3):
левый подмассив (-5;-1;7) = объем равен 1
правый подмассив (0;0;0), (5;6;10), (11;3;6)
считаем объем и так далее пока всеми элементами не разобъем...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2014, 13:41     Поиск min и max
Еще ссылки по теме:

C++ Поиск max и min с stack
C++ Поиск max или min элемента указанного столбца матрицы
C++ Арбузы (оптимальный поиск min и max)

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

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
01.05.2014, 13:41     Поиск min и max #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Идея моего кода проста. Пусть имеется массив, для которого известны минимум и максимум его элементов. Если мы добавляем к этому массиву один элемент слева или справа, то чтобы найти минимум и максимум в новом массиве нет необходимости просматривать все элементы нового массива. Достаточно сравнить добавленный элемент с уже известными минимумом и максимумом. Вот мой код, если я не наделал ошибок, этим и занимается. Берётся сначала один элемент, затем к нему по одному справа добавляются ещё, каждый раз находится новый максимум и минимум, а их разность записывается в массив для дальнейшего использования. Одновременно то же самое делается с конца массива к началу.
В результате вместо квадратичной сложности для #3 получается линейная для #6.
А вот код #7 выглядит каким-то совсем другим...
Yandex
Объявления
01.05.2014, 13:41     Поиск min и max
Ответ Создать тему
Опции темы

Текущее время: 05:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru