在一个数组中查找具有最小绝对值的元素

我试图在一个数组中找到一个具有最小绝对值的元素。例如，在数组[5.1，-2.2，8.2，-1，4，3，-5，6]中，我想要得到值-1。我使用以下代码（myarray是1D数组，未排序）

for (int i = 1; i < 8; ++i)
    {
        if(fabsf(myarray[i])<fabsf(myarray[0])) myarray[0] = myarray[i];
    }

然后，目标值在myarray[0]中。因为我必须多次重复这个过程，所以这段代码成为了我程序中的瓶颈。有人知道如何改进这个代码吗？提前感谢！

顺便说一句，数组的大小总是八。这可以用来优化这个代码吗？

更新：到目前为止，以下代码在我的机器上运行得稍微好一点：

float absMin = fabsf(myarray[0]); int index = 0; 
for (int i = 1; i < 8; ++i)
    {
        if(fabsf(myarray[i])<absMin) {absMin = fabsf(myarray[i]); index=i;}
    }
float result = myarray[index];

我不知道如何避免fabsf，因为我只想比较绝对值，而不是计算它们。有人知道吗？

有一些都市神话，比如内联、手动展开循环等等，它们应该会让你的代码更快。好消息是你不必这么做，至少如果你使用-O3编译器优化。

坏消息是，如果你已经使用了-O3，你就无法加快这个函数的速度：编译器会优化你的代码！例如，它肯定会像一些人建议的那样缓存fabsf(myarray[0])。通过这种"重构"，您唯一能实现的就是在程序中构建错误，降低程序的可读性。

我的建议是去其他地方寻求改进：

尽量减少对该代码的调用次数
如果这段代码是瓶颈，我猜你会一遍又一遍地重新计算最小值（否则将值填充到数组中需要大约相同的时间），所以缓存搜索结果
将成本转移到更改数组的元素，例如通过使用一些奇特的数据结构（堆、priority_queue）或通过跟踪元素的最小值。假设您的数组只有两个元素值[1,2]，所以最小值为1。现在，如果你改变
- 2点到3点，你什么都不用做
- 从2到0，您可以轻松地将最小值更新为0
- 从1到3，您必须遍历所有元素。但也许这种情况并不常见

您能在制造前存储这些值吗？

正如@Gerstrong所提到的，将数字存储在循环之外，并仅在数组更改时计算，这将给你带来提升。

调用partial_sort或nth_element将仅对数组进行排序，以使正确的值位于正确的位置。

std::nth_element(v.begin(), v.begin(), v.end(), [](float& lhs, float& rhs){
    return fabsf(lhs)<fabsf(rhs);
});

让我给出一些可能有所帮助的想法：

float minVal = fabsf(myarray[0]);
for (int i = 1; i < 8; ++i)
{
    if(fabsf(myarray[i])<minVal) minVal = fabsf(myarray[i]);
}
myarray[0] = minVal;

但是现在的编译器非常聪明，你可能不会有更多的速度，因为你已经得到了优化的代码。这取决于您提到的代码是如何调用的。

优化的另一种方法是使用C++和STL，因此可以使用典型的二进制搜索树std::set:

// Absolute comparator for std::set
bool absless_compare(const int64_t &a, const int64_t &b) 
{
   return (fabsf(a) < fabsf(b));
}
std::set<float, absless_compare> mySet = {5.1, -2.2, 8.2, -1, 4, 3, -5, 6};
const float minVal = *(mySet.begin());

使用这种方法，通过插入数字，它们已经按升序排序。less Comparator通常是std:：set的集合，但您可以将其更改为使用不同的东西，如本例中所示。这可能对更大的数据集有所帮助，但您提到只有八个值可以比较，所以这真的没有帮助。

八个元素是一个非常小的数字，在用数据填充排序函数之前，可能会将其与std::array<float,8> myarray的声明一起保存在堆栈中。你应该在你的完整代码集上使用变体，并观察有什么帮助。当然，如果您声明std::array<float,8> myarray或float[8] myarray运行时，您应该得到相同的结果。

您还可以检查fabsf是否真的使用float作为参数，并且没有将变量转换为double，这会降低性能。还有std::abs()，据我所知，它可以推导数据类型，因为在C++中，你可以使用模板等。

如果不想使用晶圆厂，显然可以调用这样的

float myAbs(const float val)
{
   return (val<0) ? -val : val;
}

或者你把比特破解为零，这会使你的数字为负数。不管怎样，我确信fabsf完全意识到了这一点，我不认为这样的代码会让它更快。

所以我会检查这个参数是否转换为double。如果你的系统中有C99标准，那么你不应该有这个问题。

一个想法是以"锦标赛"的方式进行比较，而不是线性比较。换句话说，你首先将1与2进行比较，将3与4进行比较，等等。然后你取这4个元素，做同样的事情，然后再做一次，直到你只剩下一个元素。

这不会改变比较次数。由于每次比较都会从运行中删除一个元素，因此无论发生什么，您都会有7次比较。那么，我为什么建议这样做呢？因为它从代码中删除了数据依赖项。现代处理器有多个流水线，可以同时引退多条指令。但是，当您在循环中进行比较时，每个循环迭代都取决于前一个循环。当你以锦标赛的方式进行时，前四个比较是完全独立的，所以处理器可能能够同时进行所有比较。

除此之外，您还可以在一个琐碎的循环中同时计算所有晶圆厂，并将其放入一个新的阵列中。由于晶圆厂的计算是独立的，因此可以很容易地加快速度。你可以先这样做，然后进行锦标赛风格的比较来获得指数。它应该是完全相同数量的操作，只是改变顺序，这样编译器就可以更容易地看到缺乏数据依赖性的较大块。

绝对值最小的数组元素

让数组A

A = [5.1, -2.2, 8.2, -1, 4, 3, -5, 6]

A的最小绝对值为

double miniAbsValue = A.array().abs().minCoeff();
int i_minimum = 0;  // to find the position of minimum absolute value
for(int i = 0; i < 8; i++)
 {
  double ftn = evalsH(i);
  if( fabs(ftn) == miniAbsValue )
    {
      i_minimum =  i; 
    }
  }

现在A中具有最小绝对值的元素是

A(i_minimum)

相关内容

最新更新

热门标签：