Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
3 / 3 / 1
Регистрация: 27.07.2017
Сообщений: 54
1

Оптимизация кода

06.09.2017, 10:40. Просмотров 329. Ответов 2
Метки нет (Все метки)

Помогите оптимизировать код.
суть программы такая, принимает на вход колличество бегунов и в массив записывает их координаты, потом колличество контрольных точек и координаты этих точек, а выводит ближашего бегуна к каждой точку в строку чкркз пробел (каждая точка в новой строке)
На вход могут поступать значения до 100 000 бегунов и 10 000 точек, проблемма именно с таким колличеством.

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
#include <iostream>
#include <cmath>
using namespace std;
 
struct point{
 float n;
 float x;
 short int y;
 
};
 
struct ras{
 short int t;
 short int k;
 float r;
};
 
int main() {
 int nt,nk;
 cin>>nt;
 //---------------------------------------------------------------------------------
 point *m = new point[nt];
 for(int i=0; i<nt; i++) {cin>>m[i].x>>m[i].y; m[i].n=i+1;}
 cin>>nk;
 //---------------------------------------------------------------------------------
 point *m1 = new point[nk];
 for(int i=0; i<nk; i++) {cin>>m1[i].x>>m1[i].y; m1[i].n=i+1;}
 //---------------------------------------------------------------------------------
 double supmin=0;
 ras **array = new ras*[nk];
 float *su = new float [nk]; 
 for(int q=0; q<nk; q++){
  float min = sqrt((m[q].x-m1[0].x)*(m[q].x-m1[0].x) + (m[q].y-m1[0].y)*(m[q].y-m1[0].y));
  array[q] = new ras[nt];
  for(int j=0; j<nt; j++){
   array[q][j].r = sqrt((m[j].x-m1[q].x)*(m[j].x-m1[q].x) + (m[j].y-m1[q].y)*(m[j].y-m1[q].y));
   if(min>=array[q][j].r){min = array[q][j].r;}
  }
  su[q]=min;
 }
 //---------------------------------------------------------------------------------
 for(int q=0; q<nk; q++){
  for(int j=0; j<nt; j++){
   if(su[q]==array[q][j].r){cout<<m[j].n<<" ";}
  }
  cout<<endl;
 }
 //---------------------------------------------------------------------------------
 delete [] array;
 delete [] m;
 delete [] m1;
 delete [] su;
 return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.09.2017, 10:40
Ответы с готовыми решениями:

Оптимизация кода
Нужно очень сильно оптимизировать код, даже пусть с использованием потоков, если это возможно! ...

Оптимизация кода
В С++ я совсем недавно, вот задали задачку: Перемножить 2 матрицы MxМ, элементами которых...

Оптимизация кода
Нужно както упростить програму /* Дан массив а если в нем встречается такой элемент что а &lt;a ...

Оптимизация кода
Покритикуйте, если не сложно. А еще очень интересно, как теперь это сделать в виде приложения на...

2
34 / 36 / 17
Регистрация: 16.04.2017
Сообщений: 478
Записей в блоге: 4
06.09.2017, 11:57 2
Зачем rast?
Зачем в point n?
Зачем в цикле создавать array[q]?

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
struct point
{
    double x;
    double y;
};
 
double distance(point* A,point* B)
{
    return sqrt((A->x-B->x)*(A->x-B->x)+(A->y-B->y)*(A->y-B->y));
}
 
int main(int argc, char *argv[])
{
    QCoreApplication a(argc, argv);
 
    int numRun=0,numPoint=0;
 
    std::cout<<"count of runners=";
    std::cin>>numRun;
 
    std::cout<<"runners:\n";
    point* runner=new point[numRun];
    for(int i=0;i<numRun;i++)
    {
        std::cout<<"input x\n";
        std::cin>>runner[i].x;
        std::cout<<"input y\n";
        std::cin>>runner[i].y;
    }
 
    std::cout<<"count of checkpoints=";
    std::cin>>numPoint;
 
    std::cout<<"checkpoints:\n";
    point* checkPoint=new point[numPoint];
    for(int i=0;i<numPoint;i++)
    {
        std::cout<<"input x\n";
        std::cin>>checkPoint[i].x;
        std::cout<<"input y\n";
        std::cin>>checkPoint[i].y;
    }
 
    double min=0,temp=0;
    int index;
    for (int i=0;i<numPoint;i++)
    {
        min=distance(&checkPoint[i],&runner[0]);
        index=0;
        for(int j=1;j<numRun;j++)
        {
            temp=distance(&checkPoint[i],&runner[j]);
            if(temp<min)
            {
                min=temp;
                index=j;
            }
 
        }
        std::cout<<"for point "<<i<<" closest runner is "<<index<<"\n";
    }
 
    return a.exec();
}
Добавлено через 2 минуты
Так как связей в цикле нет - можешь его легко распараллелить.
#pragma omp for
1
580 / 394 / 200
Регистрация: 06.09.2013
Сообщений: 1,146
06.09.2017, 13:42 3
Цитата Сообщение от T_e_n_Jl_bl_u Посмотреть сообщение
На вход могут поступать значения до 100 000 бегунов и 10 000 точек, проблемма именно с таким колличеством.
Если для такого количества должно работать, лучше строить специальную структуру данных ускоряющую поиск ближайшего соседа на плоскости kd-tree,например
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
06.09.2017, 13:42

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Оптимизация кода
main: #include &lt;iostream&gt; #include &lt;conio.h&gt; #include &quot;keyBuffer.h&quot; #include &quot;pause.h&quot;...

Оптимизация кода
Как можно оптимизировать данный программный код? Ответ объяснить void func() { for (int i...

Оптимизация кода
Здравствуйте! у меня есть такая функция, которая очень часто вызывается: int fun(int x_,int...

Оптимизация кода
Доброго времени сутки господа у меня к вам вопрос как можно оптимызуваты данный код? #include...


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

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

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