代码之家 › 专栏 › 技术社区 › Neil Slater

一种检测扁平多维数组中“角点秩”的有效方法

optimization c

Neil Slater · 技术社区 · 12 年前

这是一小段经常被称为代码的代码,也是我试图优化的卷积算法的一部分(从技术上讲,这是我的第一次优化,我已经将速度提高了2倍,但现在我陷入了困境):

inline int corner_rank( int max_ranks, int *shape, int pos ) {
  int i;
  int corners = 0;
  for ( i = 0; i < max_ranks; i++ ) {
    if ( pos % shape[i] ) break;
    pos /= shape[i];
    corners++;
  }
  return corners;
}

该代码用于计算位置的属性 pos 在一个N维数组中(已经被扁平化为指针,加上算术运算)。 max_ranks 是维度,以及 shape 是每个维度中的大小数组。

示例三维阵列可能具有 max_ranks = 3 和 shape = { 3, 4, 5 } 前几个元素的示意图布局可能如下所示:

 0       1       2       3       4       5       6       7       8
 [0,0,0] [1,0,0] [2,0,0] [0,1,0] [1,1,0] [2,1,0] [0,2,0] [1,2,0] [2,2,0]

 Returned by function:
 3       0       0       1       0       0       1       0       0

其中第一行0..8显示了由 销售时点情报系统 ,下面的数字给出了多维索引。编辑:下面是函数返回的值(2的值在位置12、24和36处返回)。

该函数有效地返回多维索引中的“前导”零的数量,并按原样设计,以避免在每次增量时需要完全转换为数组索引。

我能用这个功能做些什么吗?让它本质上更快?有没有聪明的方法可以避免 % ,或者另一种计算“角落排名”的方法——顺便说一句,如果它有一个我不知道的更正式的名字。

1 回复 | 直到 12 年前

Andy Stangeland 12 年前

你唯一应该回来的时候 max_ranks 是如果 pos 等于零。通过检查此项,可以从for循环中删除条件检查。这将提高最坏情况下的完成时间,并提高大max_ranks值的循环速度。

这是我的补充,还有一种避免除法运算的替代方法。我相信这和手写一样快 div 就像@twalberg所建议的那样,除非有某种方法可以在不进行第二次乘法的情况下产生余数。

我担心,由于最常见的答案是0(甚至没有通过第一次mod调用),你不会看到太多改进。我的猜测是,你的平均运行时间非常接近模函数本身的运行时间。你可以尝试搜索一种更快的方法来确定一个数字是否是 销售时点情报系统 。您实际上不需要计算余数;你只需要知道是否有是是否为余数。

如果我通过重组你的代码使事情变得混乱,我很抱歉。我相信这会稍微快一点,除非您的编译器已经在进行这些优化。

inline int corner_rank( int max_ranks, int *shape, int pos ) {
  // Most calls will not get farther than this.
  if (pos % shape[0] != 0) return 0;

  // One check here, guarantees that while loop below always returns.
  if (pos == 0) return max_ranks;

  int divisor = shape[0] * shape[1];
  int i = 1;
  while (true) {
    if (pos % divisor != 0) return i;
    divisor *= shape[++i];
  }
}

同时尝试声明 销售时点情报系统 和 divisor 作为尽可能小的类型。如果它们永远不会大于255,则可以使用 unsigned char 。我知道有些处理器用较小的数字进行除法的速度比用较大的数字更快,但你必须适当地设置变量类型。