哪一个更适合访问数组?
解决以下练习:
写出三个不同版本的程序来打印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?