#c #graph
#c #График
Вопрос:
Хорошо, итак, позвольте мне немного объяснить об этом. В массиве SL[] я получил указатель на списки (я могу сказать, что список разделен на небольшие части). Итак, я перехожу к SL [0] изучить список, затем перехожу к SL [1] изучить список…..
typedef struct TSL {
struct TSL *next;
int a;
} LSL;
LSL* SL[n] = {0}; // Array of pointers ;)
// Loop 1
void Find_All_Arc_SL()
{
int i;
LSL *tmp;
for(i=0;i<n;i )
{
tmp = SL[i];
while(tmp != 0)
{
//printf("I find arc! %d -> %d",i,tmp->a);
tmp = tmp -> next;
}
}
}
Цикл 2.
typedef struct TAL {
struct TAL *next;
int v;
int a;
} LAL;
LAL *AL = 0;
void Find_All_Arc_AL()
{
LAL *tmp;
tmp = AL;
while(tmp != 0)
{
//printf("I find arc %d -> %d n",tmp->v,tmp->a);
tmp = tmp -> next;
};
}
В этой функции я просто исследую список … просто делаю это без какого-либо массива и т.д.
Мой вопрос: Почему Find_All_Arc_SL() всегда быстрее (миллисекунды), чем Find_All_Arc_AL() ? Эти функции работают почти одинаково, но первая (более быстрая) должна выполнять дополнительную работу
ВЫ ПРОСИЛИ ПРЕДОСТАВИТЬ ПОЛНЫЙ КОД. ВОТ ОНО: Вы можете увеличивать / уменьшать n
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define n 5500
//Define struct
typedef struct TSL {
struct TSL *next;
int a;
} LSL;
typedef struct TAL {
struct TAL *next;
int v;
int a;
} LAL;
// Poiner and array of pointers
LAL *AL = 0;
LSL* SL[n] = {0};
// To Calculate time
__int64 freq, start, end, diff;
// Build graph
void Create_AL()
{
LAL *tmp;
int p,k;
for(p=0;p<n;p )
for(k=0;k<n;k )
{
// Add arc
tmp = malloc (sizeof(LAL));
tmp->v = p;
tmp->a = k;
if(AL == 0) { tmp->next = 0; AL = tmp; }
else { tmp->next = AL; AL = tmp; }
}
}
// Find arc
void Find_All_Arc_AL()
{
LAL *tmp;
tmp = AL;
while(tmp != 0)
{
//printf("I found arc %d -> %d n",tmp->v,tmp->a);
tmp = tmp -> next;
};
}
// Build graph
void Create_SL()
{
LSL *tmp;
int p,k;
for(p=0;p<n;p )
for(k=0;k<n;k )
{
// Add arc
tmp = malloc(sizeof(LSL));
tmp -> a = k;
if(SL[p] == 0) { tmp -> next = 0; SL[p] = tmp; }
else { tmp -> next = SL[p]; SL[p] = tmp; }
}
}
void Find_All_Arc_SL()
{
int i;
LSL *tmp;
for(i=0;i<n;i )
{
tmp = SL[i];
while(tmp != 0)
{
//printf("I find arc %d -> %d n", i, tmp->a);
tmp = tmp -> next;
}
}
}
/**
** CALCULATE TIME!
**/
void start_timer()
{
freq = 0; start = 0; end = 0; diff = 0;
QueryPerformanceFrequency((LARGE_INTEGER*)amp;freq);
QueryPerformanceCounter((LARGE_INTEGER*)amp;start);
}
void end_timer()
{
QueryPerformanceCounter((LARGE_INTEGER*)amp;end);
diff = ((end - start) * 1000) / freq;
}
int main(int argc, char *argv[])
{
Create_SL();
start_timer();
Find_All_Arc_SL();
end_timer();
printf("Find_All_Arc_SL SEARCHING ALL ARC TOOK %d n",diff);
Create_AL();
start_timer();
Find_All_Arc_AL();
end_timer();
printf("Find_All_Arc_AL SEARCHING ALL ARC TOOK %d n",diff);
system("PAUSE");
return 0;
}
Комментарии:
1. Что-то подсказывает мне, что вы неправильно его измеряете. Либо разные данные, разные шаблоны доступа, разные стратегии прогрева, либо неправильные методы секундомера. Покажите больше кода!
Ответ №1:
Это зависит от ваших данных. Вы должны опубликовать полный (рабочий) пример.
Кроме того, как вы измеряли время? вы уверены, что сравнение существенно?
Ответ №2:
Это похоже на проблему с памятью. Поскольку доступ к некэшированной памяти может занимать сотни или тысячи циклов процессора, объем и локальность доступа к памяти часто являются наиболее важным фактором, влияющим на производительность программы.
В вашем случае структура SL меньше структуры AL. Таким образом, Find_All_Arc_SL() требуется меньше памяти для посещения и, следовательно, быстрее.
Но в целом программа кажется слишком простой, чтобы быть реалистичным тестом.
Кстати: Для повышения производительности вам следует использовать больше массивов и меньше связанных списков, потому что массивы имеют гораздо лучшую локальность, чем связанные списки.
Ответ №3:
Вам нужно выполнить цикл по функции, чтобы получить реальное представление о скорости. Вы также не прогрели функции, чтобы получить значения в кэше для первого метода. Результаты, которые я получил, были:
ПОИСК Find_All_Arc_SL ПО ВСЕЙ ДУГЕ ЗАНЯЛ 6657
ПОИСК Find_All_Arc_AL ПО ВСЕЙ ДУГЕ ЗАНЯЛ 6490
с помощью этого кода:
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
#define n 500
//Define struct
typedef struct TSL {
struct TSL *next;
int a;
} LSL;
typedef struct TAL {
struct TAL *next;
int v;
int a;
} LAL;
// Poiner and array of pointers
LAL *AL = 0;
LSL* SL[n] = {0};
// To Calculate time
__int64 freq, start, end, diff;
// Build graph
void Create_AL()
{
LAL *tmp;
int p,k;
for(p=0;p<n;p )
for(k=0;k<n;k )
{
// Add arc
tmp = malloc (sizeof(LAL));
tmp->v = p;
tmp->a = k;
if(AL == 0) { tmp->next = 0; AL = tmp; }
else { tmp->next = AL; AL = tmp; }
}
}
// Find arc
void Find_All_Arc_AL()
{
LAL *tmp;
tmp = AL;
while(tmp != 0)
{
//printf("I found arc %d -> %d n",tmp->v,tmp->a);
tmp = tmp -> next;
};
}
// Build graph
void Create_SL()
{
LSL *tmp;
int p,k;
for(p=0;p<n;p )
for(k=0;k<n;k )
{
// Add arc
tmp = malloc(sizeof(LSL));
tmp -> a = k;
if(SL[p] == 0) { tmp -> next = 0; SL[p] = tmp; }
else { tmp -> next = SL[p]; SL[p] = tmp; }
}
}
void Find_All_Arc_SL()
{
int i;
LSL *tmp;
for(i=0;i<n;i )
{
tmp = SL[i];
while(tmp != 0)
{
//printf("I find arc %d -> %d n", i, tmp->a);
tmp = tmp -> next;
}
}
}
/**
** CALCULATE TIME!
**/
void start_timer()
{
freq = 0; start = 0; end = 0; diff = 0;
QueryPerformanceFrequency((LARGE_INTEGER*)amp;freq);
QueryPerformanceCounter((LARGE_INTEGER*)amp;start);
}
void end_timer()
{
QueryPerformanceCounter((LARGE_INTEGER*)amp;end);
diff = ((end - start) * 1000) / freq;
}
int main(int argc, char *argv[])
{
int i;
Create_SL();
Find_All_Arc_SL();
start_timer();
for(i=0;i<2000; i)
Find_All_Arc_SL();
end_timer();
printf("Find_All_Arc_SL SEARCHING ALL ARC TOOK %d n",diff);
Create_AL();
Find_All_Arc_AL();
start_timer();
for(i=0;i<2000; i)
Find_All_Arc_AL();
end_timer();
printf("Find_All_Arc_AL SEARCHING ALL ARC TOOK %d n",diff);
system("PAUSE");
return 0;
}
Редактировать: как бы то ни было, мне пришлось снизить ваш, n он был таким большим, malloc возвращал 0 в 64-разрядной системе с 4 ГБ оперативной памяти.