当前位置： 文江博客话题详情

应该更慢，但更快。为什么？

发布于 2024-11-01 18:56:07 字数 3089 浏览 0 评论 0原文

好吧，让我解释一下这一点。在数组 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*)&freq);
 QueryPerformanceCounter((LARGE_INTEGER*)&start);

}

void end_timer()
{

    QueryPerformanceCounter((LARGE_INTEGER*)&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;
}
原文

Ok, so let me explain a little bit about this. In array SL[] i got pointer to lists ( I can say that the list is divided to small parts). So i go to SL[0] explore the list, then go to SL[1] explore the list.....

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;
      }
   }
}

Loop 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;
  };

}

In this function i just explore list... just do it without any array etc.

My question is: Why Find_All_Arc_SL() is always faster (milliseconds) than Find_All_Arc_AL()? These functions are working almost the same, but the first (faster one) one have to do additional work

YOU ASKED FOR FULL CODE. HERE IT IS: U can increase/decrease 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*)&freq);
 QueryPerformanceCounter((LARGE_INTEGER*)&start);

}

void end_timer()
{

    QueryPerformanceCounter((LARGE_INTEGER*)&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;
}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（3）

囚我心虐我身 2024-11-08 18:56:07

这取决于你的数据。您应该发布一个完整的（工作）示例。

另外，你是如何测量时间的？您确定比较有意义吗？

It depends on your data. You should post a full (working) example.

Also, how did you measure time? are you sure the comparison is significant?

回复 原文
对你而言 2024-11-08 18:56:07

看起来像是记忆的东西。由于访问非缓存内存可能需要数百或数千个 CPU 周期，因此内存访问的数量和局部性通常是影响程序性能的最重要因素。

在您的情况下，SL 结构比 AL 结构小。因此，Find_All_Arc_SL() 需要访问的内存较少，因此速度更快。

但总体而言，该程序似乎过于简单，无法成为现实的测试。

顺便说一句：为了提高性能，您应该使用更多的数组和更少的链表，因为数组比链表具有更好的局部性。

It looks like a memory thing. Since accessing non-cached memory can take hundreds or thounsands of CPU cycles, the amount and the locality of memory access often is the most important factor influencing the performance of a program.

In your case, the SL structure is smaller than the AL structure. So Find_All_Arc_SL() has less memory to visit and is therefore faster.

But overall, the programm seems too bare bone to be a realistic test.

BTW: For improved performance, you should use more arrays and fewer linked lists because arrays have far better locality than linked lists.

回复 原文
我的影子我的梦 2024-11-08 18:56:07

您需要循环遍历该函数才能真正感受到速度。您也没有预热函数来获取第一个方法的缓存中的值。我得到的结果是：

Find_All_Arc_SL 搜索所有 ARC TOOK 6657

Find_All_Arc_AL 搜索所有 ARC TOOK 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*)&freq);
 QueryPerformanceCounter((LARGE_INTEGER*)&start);

}

void end_timer()
{

    QueryPerformanceCounter((LARGE_INTEGER*)&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 在具有 4GB RAM 的 64 位系统上。

You need to loop through the function to get a real feel for the speed. You also didn't warm-up the functions to get the values in the cache for the first method. The results I got were:

Find_All_Arc_SL SEARCHING ALL ARC TOOK 6657

Find_All_Arc_AL SEARCHING ALL ARC TOOK 6490

with this code:

#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*)&freq);
 QueryPerformanceCounter((LARGE_INTEGER*)&start);

}

void end_timer()
{

    QueryPerformanceCounter((LARGE_INTEGER*)&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;
}

Edit: For what it's worth I had to lower your n, it was so big, malloc returned 0 on a 64-bit system with 4gb of ram.

回复 原文
~没有更多了~

关于作者

日久见人心

暂无简介

0 文章
0 评论
22 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

烙印

文章 0 评论 0

singlesman

文章 0 评论 0

给自己一个微笑

文章 0 评论 0

独孤求败

文章 0 评论 0

晨钟暮鼓

文章 0 评论 0

我是自愿种绣球花的

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文