Графики
По графику видно, что компилятор самостоятельно способен оптимизировать программу, но если оптимизировать ее самостоятельно, зная методы оптимизации, можно сильно ему помочь и значительно снизить время исполнения
Компиляция на Clang показывает худшие результаты, т.к. этот компилятор, в основном используют для оптимизации систем на ARM-процессоре, а у меня на ПК стоит система x86
Выводы
Анализируя графики, можно сделать несколько выводов. Скорость выполнения кода зависит от компилятора; даже когда флаги оптимизации были отключены, GCC всё равно был быстрее
Рассматривая график выполнения кода GCC с флагом оптимизации и без него можно заметить, что компиляторы сами пытаются оптимизировать код. Чем выше уровень оптимизации, тем более радикальные изменения компилятор вносит в программу. Компиляторы могут изменять программу только так, чтобы оптимизация не изменила поведение для всех входных данных. Однако компиляторы не могут оптимизировать код, в котором отсутствует качественная система управления указателями, т.е. указатели, например, могут указывать на одну и ту же область памяти, а компилятор может этого не знать, и т.д.
Если функция вызывается очень много раз, создание памяти при каждом вызове может привести к перегрузке системы и замедлению работы программы. В этом случае создание памяти вне функции может быть более эффективным решением.
Возможно, увеличение показателя кеш-миссов связан с тем, что было убрано ООП и другие особенности С++, из-за чего пришлось в некоторых случаях управлять указателями самостоятельно, поэтому на программиста возлагается больше ответственности за управление памятью; также от замера к замеру кеш-миссы сильно разнились.
Приложение
#Dijkstra.cpp #include <iostream>
#include <time.h>
// #include <conio.h>
#include <math.h>
#include <cstring>
#include <fstream>
using namespace std;
const int inf = 1000; //сокращенное от infinity
char Universum[] = "abcdefghijklmnopqrstuvwxyz";
const int TIMES = 1e7;
class Graph{
private:
int n, m; //кол-во вершин и ребер
int **G; //матрица расстояний от каждой вершины до каждой
public:
Graph(int);
double exe(int index, int start, int end, int N) const;
~Graph() {for (int i=0; i<n; i++) delete [] G[i]; delete [] G;};
};
char Ch(int c) { return c + 'a';}
int length(int a);
int enter(int N);
int main()
{
// srand(time(NULL));
int N;
cout << "Enter size of graph(<=26): ";
cin >> N;
while (N>26 || N<1)
{
cout << "Wrong size!\n";
cin >> N;
}
Graph one(N);
int start, end;
long double averageTime = 0.0;
cout << "\nEnter start vertex: ";
start = enter(N);
cout << "Enter final vertex: ";
end = enter(N);
for (int i = 0; i < TIMES; i++)
averageTime += one.exe(i, start, end, N);
cout << "\nTime of " << TIMES << " iterations: " << averageTime / CLOCKS_PER_SEC << endl;
return 0;
}
//нельзя допустить, чтобы в графе были бессвязные вершины (иначе данные будут недочитываться)
Graph::Graph(int N): n(0), m(0)
{
int i, j;
string s;
G = new int*[N];
for (i=0; i<N; i++)
G[i] = new int[N];
for (i=0; i<N; i++)
for (j=0; j<N; j++)
G[i][j] = 0;
cout << "\nMatrix";
for (i=0; i<2*N; i++) cout << ' ';
cout << "Dijkstra\n";
do{
s.resize(0);
for (int k=0; k<N; k++)
if (rand()%2 == 0) s += Universum[k];
if (s.size() == 0) s += Universum[rand()%N];
for (auto k : s)
if (isalpha(k)){
j = tolower(k) - 'a';
G[n][j] = 1;
}
++n;
}while(isalpha(s[0]) && n<N);
for (i=0; i<N; ++i)
for (j=0; j<N; ++j)
G[i][j] *= rand()%9 + 1; //наращивание ребер
//умножение на число от 1 до 9, чтобы красиво выводилась таблица
n=m=0;
#ifndef FROMFILE
for (i=0; i<N; ++i)
{
int f = 0;
cout << endl << Ch(i) << ": ";
for (j=0; j<N; ++j)
if (G[i][j])
{
++f;
cout << Ch(j)<<' ';
}
else cout << "- ";
m += f;
if (f) ++n;
else break;
cout << " ";
//вывод нагруженных ребер
for (j=0; j<N; ++j) cout << G[i][j] << ' ';
}
cout << "\n|V| = " << n << " |E| = " << m << endl;
#endif
}
double Graph::exe(int index, int start, int end, int N) const
{
clock_t startTime = clock();
int tmp, minindex, min, i;
int d[N], //минимальное расстояние
v[N]; //посещенные вершины
for (i=0; i<N; i++) {
d[i] = inf;
v[i] = 0;
}
d[start] = 0;
do{
minindex = inf;
min = inf;
for (int i = 0; i<N; i++)
{ // if vertex isn't visited and it's weight < min
if ((v[i] == 0) && (d[i]<min))
{
min = d[i];
minindex = i;
}
}
//Sum founded min weight to current weight
if (minindex != inf)
{
for (int i = 0; i<N; i++)
if (G[minindex][i] > 0)
{
tmp = min + G[minindex][i];
if (tmp < d[i]) d[i] = tmp;
}
v[minindex] = 1;
}
}while(minindex < inf);
if (index == TIMES-1){
cout << "\nShortest distances to vertices: \n";
for (i = 0; i<N; i++)
{
cout << Ch(i);
if (d[i] == inf) cout << ' ';
else for (int j=0; j<length(d[i]); j++) cout << ' ';
}
cout << endl;
for (i = 0; i<N; i++)
if (d[i] == inf) cout << "- ";
else cout << d[i] << ' ';
cout << endl;
}
//for (int i = 0; i<N; i++) cout << v[i] << ' ';
//Going backwards
int ver[N]; // массив посещенных вершин
ver[0] = end + 1; // идем с конца
int k = 1; // индекс предыдущей вершины
int w = d[end]; // вес конечной вершины
if (d[end] == inf)
{
cout << "\nIt's impossible to reach this vertex\n ";
// getch();
exit(1);
}
while (end != start) // пока не дошли до начальной вершины
{
for (int i = 0; i<N; i++) // просматриваем все вершины
if (G[i][end] != 0) // если связь есть
{
tmp = w - G[i][end]; // определяем вес пути из предыдущей вершины
if (tmp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
w = tmp;
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
if (index == TIMES - 1){
cout << "\nOutput of shortest way from " << Ch(ver[k-1] -1) << " to "<< Ch(ver[0]-1) << ":\n";
for (int i = k - 1; i >= 0; i--)
cout << Ch(ver[i] -1) << ' ';
}
return clock() - startTime;
}
int length(int a)
{
int c=0;
if (a != 0)
while (a!=0)
{
a /= 10;
c++;
}
else c++;
return c;
}
int enter(int N)
{
char ch;
cin >> ch;
while (ch > 'a'+ N - 1 || ch < 'a')
{
cout << "Wrong option\n";
cin >> ch;
}
return ch - 'a';
}
#Dijkstra_2.c
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
const int inf = 1000; //сокращенное от infinity
const char Universum[] = "abcdefghijklmnopqrstuvwxyz";
const int TIMES = 1e7;
char Ch(const int c) { return c + 'a';}
int length(int a) { return (a==0)?1: log10(a)+1; }
int enter(const int N);
void initGraph(const int N, int** G);
void exe(const int N, int index, int** G, int start, int end, int*, int*, int*);
int main()
{
// srand(time(NULL));
int **G = NULL; //матрица расстояний от каждой вершины до каждой
int N;
int len;
printf("Enter size of graph(<=26): ");
scanf("%d", &N);
while (getchar() != '\n'); //это - лучшая практика
while (N>26 || N<1)
{
printf("Wrong size!\n");
scanf("%d", &N);
while (getchar() != '\n');
}
G = (int**)calloc(N, sizeof(int*));
for (int i=0; i<N; ++i)
G[i] = (int*)calloc(N, sizeof(int));
initGraph(N, G);
int start, end;
double averageTime = 0.0L;
printf("\nEnter start vertex: ");
start = enter(N);
printf("Enter final vertex: ");
end = enter(N);
clock_t startTime = clock();
int* d = (int*)malloc(N * sizeof(int));//минимальное расстояние
int* v = (int*)calloc(N, sizeof(int));//посещенные вершины
int* ver = (int*)malloc(N * sizeof(int));// массив посещенных вершин
len = TIMES - 3;
for (int i = 0; i < len; i += 4){
exe(N, i, G, start, end, d, v, ver);
exe(N, i+1, G, start, end, d, v, ver);
exe(N, i+2, G, start, end, d, v, ver);
exe(N, i+3, G, start, end, d, v, ver);
}
printf("\nTime of %d iterations: %.5lf\n", TIMES, (double)(clock() - startTime) / CLOCKS_PER_SEC);
// printf("\nPress any key to exit\n");
// getch();
for (int i=0; i<N; ++i){
free(G[i]);
}
free(G);
free(d);
free(v);
free(ver);
return 0;
}
//нельзя допустить, чтобы в графе были бессвязные вершины (иначе данные будут недочитываться)
void initGraph(const int N, int** G){
int i, j;
int n = 0; //число вершин
int m = 0; //число ребер
printf("\nMatrix");
for (i=0; i<N+N; ++i)
printf(" ");
printf("Dijkstra\n");
int stringIndex;
char* string = NULL;
string = (char*)malloc(N * sizeof(char));
//цикл "наращивания смежности" (1, если можно попасть, иначе 0)
do{
stringIndex = 0;
// string = (char*)malloc(N * sizeof(char));
memset(string, '\0', sizeof(string));
for (i=0; i<N; ++i)
if (rand()%2 == 0)
string[stringIndex++] = Universum[i];
if (stringIndex == 0){
string[stringIndex++] = Universum[rand()%N];
}
string[stringIndex] = '\0';
for (i = 0; i < stringIndex; ++i){
j = string[i] - 'a';
G[n][j] = 1;
}
++n;
// free(string);
}while(n<N);
free(string);
for (i=0; i<N; ++i)
for (j=0; j<N; ++j)
G[i][j] *= rand()%9 + 1; //наращивание ребер
//умножение на число от 1 до 9, чтобы красиво выводилась таблица
n=m=0;
int f;
for (i=0; i<N; ++i)
{
f = 0;
printf("\n%c: ", Ch(i));
for (j=0; j<N; ++j)
if (G[i][j])
{
++f;
printf("%c ", Ch(j));
}
else printf("- ");
m += f;
if (f) ++n;
else break;
printf(" ");
//вывод нагруженных ребер
for (j=0; j<N; ++j)
printf("%d ", G[i][j]);
}
printf("\n|V| = %d |E| = %d\n", n, m);
}
void exe(const int N, int index, int** G, int start, int end, int* d, int* v, int* ver){
int tmp, minindex, min, i, j;
// int* d = (int*)malloc(N * sizeof(int));//минимальное расстояние
// int* v = (int*)calloc(N, sizeof(int));//посещенные вершины
// int* ver = (int*)malloc(N * sizeof(int));// массив посещенных вершин
int dist;
int vertex;
int len;
for (i=0; i<N; ++i){
d[i] = inf;
v[i] = 0;
ver[i] = 0;
}
d[start] = 0;
do{
minindex = inf;
min = inf;
for (i = 0; i<N; ++i)
{ // if vertex isn't visited and it's weight < min
dist = d[i];
if (!v[i] && dist<min)
{
min = dist;
minindex = i;
}
}
//Sum founded min weight to current weight
if (minindex != inf)
{
for (i = 0; i<N; ++i){
vertex = G[minindex][i];
if (vertex > 0)
{
tmp = min + vertex;
if (tmp < d[i])
d[i] = tmp;
}
}
v[minindex] = 1;
}
}while(minindex < inf);
if (index == TIMES-1){
printf("\nShortest distances to vertices: \n");
for (i = 0; i<N; ++i)
{
printf("%c", Ch(i));
len = length(d[i]);
if (d[i] == inf)
printf(" ");
else for (j=0; j<len; ++j) printf(" ");
}
printf("\n");
for (i = 0; i<N; ++i){
dist = d[i];
if (dist == inf)
printf("- ");
else printf("%d ", dist);
}
printf("\n");
}
//for (int i = 0; i<N; i++) cout << v[i] << ' ';
//Going backwards
ver[0] = end + 1; // идем с конца
int k = 1; // индекс предыдущей вершины
int w = d[end]; // вес конечной вершины
if (w == inf)
{
printf("\nIt's impossible to reach this vertex\n ");
exit(1);
}
while (end != start) // пока не дошли до начальной вершины
{
for (i = 0; i<N; ++i){ // просматриваем все вершины
vertex = G[i][end];
if (vertex != 0) // если связь есть
{
tmp = w - vertex; // определяем вес пути из предыдущей вершины
if (tmp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
w = tmp;
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
++k;
}
}
}
}
if (index == TIMES - 1){
printf("\nOutput of shortest way from %c to %c:\n", Ch(ver[k-1] -1), Ch(ver[0]-1));
for (i = k - 1; i >= 0; --i)
printf("%c ", Ch(ver[i]-1));
}
// free(d);
// free(v);
// free(ver);
}
int enter(const int N)
{
char ch;
scanf("%c", &ch);
while (getchar() != '\n');
while (ch > 'a'+ N - 1 || ch < 'a')
{
printf("Wrong option\n");
scanf("%c", &ch);
while (getchar() != '\n');
}
return ch - 'a';
}
Санкт-Петербург
2023