哪一个更适合访问数组?

解决以下练习:

写出三个不同版本的程序来打印ia的元素。 一个版本应该使用一个范围来管理迭代,另外两个应该使用一个普通的for循环,一个使用下标,另一个使用指针。 在所有三个程序中直接编写所有类型。 也就是说,不要使用类型别名,自动或decltype来简化代码。[C ++ Primer]

一个问题出现了: 访问数组的哪些方法在速度方面进行了优化,为什么?


我的解决方案

  • Foreach Loop:

    int ia[3][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12}};    
    for (int (&i)[4]:ia)        //1st method using for each loop
        for(int j:i)
            cout<<j<<" ";
    
  • 嵌套for循环:

    for (int i=0;i<3;i++)       //2nd method normal for loop
        for(int j=0;j<4;j++)
            cout<<ia[i][j]<<" ";
    
  • 使用指针:

    int (*i)[4]=ia;
    for(int t=0;t<3;i++,t++){  //3rd method.  using pointers.
        for(int x=0;x<4;x++)
            cout<<(*i)[x]<<" ";
    
  • 使用auto

    for(auto &i:ia)             //4th one using auto but I think it is similar to 1st.  
        for(auto j:i)
             cout<<j<<" ";
    

  • 使用clock()基准结果

    1st: 3.6  (6,4,4,3,2,3) 
    2nd: 3.3  (6,3,4,2,3,2)
    3rd: 3.1  (4,2,4,2,3,4)
    4th: 3.6  (4,2,4,5,3,4)
    

    模拟每种方法1000次:

    1st: 2.29375  2nd: 2.17592  3rd: 2.14383  4th: 2.33333
    Process returned 0 (0x0)   execution time : 13.568 s
    

    使用的编译器:MingW 3.2 c ++ 11标志启用。 IDE:代码块


    我有一些意见和要点,我希望你能从中得到你的答案。

  • 正如你所提到的,第四个版本与第一个版本基本相同。 auto可以被认为只是一种编码快捷方式(这当然不是严格正确的,因为使用auto可能会导致获得不同的类型,从而导致不同的运行时行为,但大多数情况下都是如此。 )

  • 使用指针的解决方案可能不是人们说他们使用指针时的意思! 一种解决方案可能是这样的:

    for (int i = 0, *p = &(ia[0][0]); i < 3 * 4; ++i, ++p)
        cout << *p << " ";
    

    或者使用两个嵌套循环(这可能毫无意义):

    for (int i = 0, *p = &(ia[0][0]); i < 3; ++i)
        for (int j = 0; j < 4; ++j, ++p)
            cout << *p << " ";
    

    从现在起,我假设这是你写的指针解决方案。

  • 在这样一个微不足道的例子中,完全支配你运行时间的部分就是cout 。 与进行I / O操作相比,花在循环簿记和检查上的时间将完全可以忽略不计。 因此,使用哪种循环技术并不重要。

  • 现代编译器擅长优化这种无处不在的任务和访问模式(遍历数组)。因此,所有这些方法都可能生成完全相同的代码(可能除了指针版本,我将在后面讨论)。 )

  • 大多数代码的性能取决于内存访问模式,而不是编译器如何生成汇编分支指令(以及其余操作)。这是因为如果所需的内存块不在CPU高速缓存中,它将花费大约相当于几百个CPU周期的时间(这只是一个球场数),以便从RAM中获取这些字节。 由于所有示例都以完全相同的顺序访问内存,因此它们在内存和缓存方面的行为将相同,并且具有大致相同的运行时间。

    作为一个侧面说明,这些示例访问内存的方式是访问内存的最佳方式! 线性,连续和从头到尾。 同样,这里的cout也存在问题,这可能是一个非常复杂的操作,甚至可能会在每次调用时调用操作系统,这可能导致从CPU高速缓存几乎完全删除(逐出)所有有用的东西。

  • 在32位系统和程序中, int和指针的大小通常是相等的(均为32位!)这意味着传递和使用索引值或指向数组的指针并不重要。 然而,在64位系统中,指针是64位,但int通常仍然是32位。 这表明在64位系统和程序中使用索引而不是指针(甚至迭代器)通常更好。

    在这个特定的例子中,这并不重要。

  • 您的代码非常具体且简单,但通常情况下,尽可能多地向编译器提供有关代码的更多信息。 这意味着您必须使用最狭窄,最具体的设备来完成工作。 这又意味着对于编译器而言,泛型for循环(即for (int i = 0; i < n; ++i) )比基于范围的for循环更糟糕(即for (auto i : v) ),因为在后一种情况下,编译器只是知道你将遍历整个范围,而不是在它之外,或者跳出循环或什么,而在泛型for循环的情况下,特别是如果你的代码更复杂,编译器不能确定这一点,必须插入额外的检查和测试,以确保代码按照C ++标准所说的那样执行。

  • 在很多(大多数?)情况下,尽管您可能认为性能很重要, 但事实并非如此 。 大部分时间你重写某些东西来获得性能,你并没有太大的收获。 大多数情况下,您获得的性能提升并不值得您承受的可读性和可维护性方面的损失。 因此,正确设计您的代码和数据结构(并保持性能),但避免这种“微型优化”,因为它几乎总是不值得,甚至会损害代码的质量。

  • 一般来说,速度方面的表现是很难推论的。 理想情况下,您必须使用合理的科学测量和统计方法,在实际工作条件下使用真实硬件上的实际数据来测量时间。 即使测量一段代码运行的时间也不是微不足道的。 衡量绩效很困难,而推断这一点很难,但现在这是识别瓶颈和优化代码的唯一途径。

  • 我希望我已经回答了你的问题。

    编辑:我为你正在做的事情写了一个非常简单的基准。 代码在这里。 它是为Windows编写的,应该可以在Visual Studio 2012上编译(因为基于范围的for循环)。以下是时序结果:

    Simple iteration (nested loops): min:0.002140, avg:0.002160, max:0.002739
        Simple iteration (one loop): min:0.002140, avg:0.002160, max:0.002625
       Pointer iteration (one loop): min:0.002140, avg:0.002160, max:0.003149
     Range-based for (nested loops): min:0.002140, avg:0.002159, max:0.002862
     Range(const ref)(nested loops): min:0.002140, avg:0.002155, max:0.002906
    

    相关数字是“最小”时间(每个测试超过2000次,对于1000x1000阵列)。如您所见,测试之间完全没有区别。 请注意,您应该打开编译器优化或测试2将是一场灾难,情况4和5将比1和3稍差。

    这里是测试代码:

    // 1. Simple iteration (nested loops)
    unsigned sum = 0;
    for (unsigned i = 0; i < gc_Rows; ++i)
        for (unsigned j = 0; j < gc_Cols; ++j)
            sum += g_Data[i][j];
    
    // 2. Simple iteration (one loop)
    unsigned sum = 0;
    for (unsigned i = 0; i < gc_Rows * gc_Cols; ++i)
        sum += g_Data[i / gc_Cols][i % gc_Cols];
    
    // 3. Pointer iteration (one loop)
    unsigned sum = 0;
    unsigned * p = &(g_Data[0][0]);
    for (unsigned i = 0; i < gc_Rows * gc_Cols; ++i)
        sum += *p++;
    
    // 4. Range-based for (nested loops)
    unsigned sum = 0;
    for (auto & i : g_Data)
        for (auto j : i)
            sum += j;
    
    // 5. Range(const ref)(nested loops)
    unsigned sum = 0;
    for (auto const & i : g_Data)
        for (auto const & j : i)
            sum += j;
    

    它有很多影响它的因素:

  • 这取决于编译器
  • 这取决于使用的编译器标志
  • 这取决于使用的计算机
  • 只有一种方法可以知道确切答案:测量处理巨大数组(可能来自随机数生成器)时使用的时间,除了数组大小应该至少为1000x1000之外,这与您已经完成的方法相同。

    链接地址: http://www.djcxy.com/p/6187.html

    上一篇: Which one is more optimized for accessing array?

    下一篇: Can a local variable's memory be accessed outside its scope?