首页 > 试题广场 >

设有 N 个物体的坐标 (x, y, z) 和速度 (vx,

[单选题]
设有 N 个物体的坐标 (x, y, z) 和速度 (vx, vy, vz),求经过 dt 时间之后物体的新坐标,以下有两种方式(C++):
方法一:
struct Object {
  float x, y, z;
  float vx, vy, vz;
};

Object obj[N];

for (int i = 0; i < N; i++) {
  obj[i].x += obj[i].vx * dt;
  obj[i].y += obj[i].vy * dt;
  obj[i].z += obj[i].vz * dt;
}
方法二:
struct ObjectArray {
  float x[N], y[N], z[N];
  float vx[N], vy[N], vz[N];
};

ObjectArray obj_all;

for (int i = 0; i < N; i++) {
  obj_all.x[i] += obj_all.vx[i] * dt;
  obj_all.y[i] += obj_all.vy[i] * dt;
  obj_all.z[i] += obj_all.vz[i] * dt;
}
在最高级别的优化选项(-O3)下,两种方式运行速度相比()
  • 方法一运行速度更快
  • 方法二运行速度更快
  • 两种方法速度差不多

猜测的可能原因:

(1)必要的假设:

1)使用索引对问数组的一个元素的一次访问过程用时 m

2)根据结构体变量对其一个成员的一次访问过程用时 n

(2)在代码1中,以obj[i].x为例分析:

1)访问obj[i].x需要依次获得obj、obj[i]、obj[i].x的地址。

2)obj的地址在循环之初就可以确定了,而且在程序后续运行过程中直接重复使用即可。

3)在每更新一次i的时候,obj[i]的地址需要重新确定。根据obj访问obj[i]用时m

4)由于obj[i].x的地址与obj[i]的地址间的偏移是固定的,所以在obj[i]地址重新确定的时候,obj[i].x的地址也需要根据obj[i]重新确定。根据obj[i]访问obj[i].x用时n

5)访问一次obj[i].x用时(m+n)。则整个循环用时6N*(m+n).

(3)在代码2中,以obj_all.x[i]为例分析:

1)访问obj_all.x[i]需要依次获得obj_all、obj_all.x、obj_all.x[i]的地址。

2)obj_all的地址在循环之初就可以确定了,而且在程序后续运行过程中直接重复使用即可。

3)obj_all.x的地址与obj_all的地址的偏移是固定的,由于obj_all的地址固定,所以obj_all.x的地址固定。在循环中,obj_all.x的地址只需要在循环之初获取一次即可,后边直接重复使用即可。根据obj_all访问获取obj_all.x的地址用时n。

4)在每更新一次i的时候,obj_all.x[i]的地址需要重新确定。根据obj_all.x访问obj.x[i]用时m。

5)访问一次obj_all.x[i]用时m。则整个循环用时(6N*m+6n)

(4)比较与结论
令6N(m+n)>=(6Nm+6n),(N,m,n为正整数,m,n为常数)

得:N>=1

即:当N>1时,代码2比代码1高效,当N等于1时,代码1和代码2相当。也即,在效率方面,代码2不严格地比代码1更加高效,当且仅当N等于1时两者相当。


编辑于 2022-01-06 01:32:39 回复(1)
我的理解是构造N个对象,调用N次构造函数比较费劲吧。希望大佬能给出解析
发表于 2020-09-03 20:52:18 回复(4)

空间换时间

发表于 2021-09-18 20:08:54 回复(0)
我觉得是从两个角度产生了效率提升:连续的内存访问增加了cash命中率,同时编译器更容易将此循环向量化
发表于 2020-10-23 09:40:29 回复(3)
  • 这个题可以参考二维数组,先给行赋值和先给列赋值,哪个更快

  • 方法一是先给列赋值,方法二是先给行赋值

  • 先给列赋值会产生许多缺页中断,耗时较长,故先给行赋值运行更快

发表于 2022-08-03 10:02:12 回复(1)
感觉第二个也没有更好的局部性啊,得跳过所有的x,y,z才能用vx,第一个一整块就包含了x,vx...
编辑于 2024-01-17 11:27:15 回复(0)
空间换时间
发表于 2022-09-22 19:04:25 回复(0)
我的理解是方法二编译器做了优化把类直接去掉只剩下数组,所以不需要指针访问成员变量,这里的类不是必须的编译器可以做优化
发表于 2022-01-31 00:18:41 回复(0)
这道题目考点在于结构体内存对齐的作用。
注意:数组,虽然是连续的内存,但是其效率未必赶得上内存对齐
发表于 2021-02-22 18:44:22 回复(0)