是否可以微优化 "x = max(a,b); y = min(a,b);"？

Question

我的算法一开始就像

int sumLargest2 ( int * arr, size_t n )
{
    int largest(max(arr[0], arr[1])), secondLargest(min(arr[0],arr[1])); 
    // ...

我意识到第一个可能不是最优的，因为调用 max 然后 min 是重复的，当你认为知道最小值所需的信息已经存在时，一旦你找到最大值。所以我发现我可以做

   int largest = max(arr[0], arr[1]);
   int secondLargest = arr[0] == largest ? arr[1] : arr[0];

减少无用的 min 调用，但我不确定是否真的节省了多少操作。是否有任何奇特的位移算法可以做相当于

int largest(max(arr[0], arr[1])), secondLargest(min(arr[0],arr[1]));

??????

Answer 1

怎么样：

int largestIndex = arr[1] > arr[0];
int largest = arr[largestIndex];
int secondLargest = arr[1 - largestIndex];

第一行依赖于布尔结果在 true 的情况下隐式转换为 1，在 false 的情况下转换为 0。

Answer 2

在 C++ 中，您可以使用 std::minmax to produce a std::pair of the minimum and the maximum. This is particularly easy in combination with std::tie:

#include <algorithm>
#include <utility>

int largest, secondLargest;
std::tie(secondLargest, largest) = std::minmax(arr[0], arr[1]);

GCC 至少能够将对 minmax 的调用优化为单个比较，与下面的 C 代码的结果相同。

在 C 中，您可以自己编写测试：

int largest, secondLargest;
if (arr[0] < arr[1]) {
  largest = arr[1];
  secondLargest = arr[0];
} else {
  largest = arr[0];
  secondLargest = arr[1];
}

Answer 3

如果您的目的是减少查找 min mad max 的函数调用，您可以尝试 std::minmax_element。自 C++11 起可用。

auto result = std::minmax_element(arr, arr+n);
std::cout<< "min:"<< *result.first<<"\n";
std::cout<< "max :" <<*result.second << "\n";

Answer 4

如果您只想找到两个值中较大的一个，请执行以下操作：

if(a > b)
{
    largest = a;
    second = b;
}
else
{
     largest = b;
     second = a;
}

没有函数调用，一次比较，两次赋值。

Answer 5

我假设您更愿意解决更大的问题...也就是说，获取数组中最大的两个数字的总和。

您要做的是 std::partial_sort()。让我们来实施吧。

int sumLargest2(int * arr, size_t n) {
    int * first  = arr;
    int * middle = arr + 2;
    int * last   = arr + n;

    std::partial_sort(first, middle, last, std::greater<int>());

    return arr[0] + arr[1];
}

如果您无法修改 arr，那么我建议您查看 std::partial_sort_copy()。

Answer 6

时间-space权衡如何？

#include <utility>

template<typename T>
    std::pair<T, T>
        minmax(T const& a, T const& b)
        { return b < a ? std::make_pair(b, a) : std::make_pair(a, b); }

//main
std::pair<int, int> values = minmax(a[0], a[1]);
int largest       = values.second;
int secondLargest = values.first;

Answer 7

x = max(a, b);
y = a + b - x;

不一定会更快，但会有所不同。

还要注意溢出。

Answer 8

我假设是 C++...

简答，使用std::minmax并使用正确的优化和正确的指令集参数进行编译。

冗长丑陋的答案，编译器无法做出所有必要的假设来使其非常非常快。你可以。在这种情况下，您可以更改算法以先处理所有数据，然后可以强制对数据进行对齐。完成所有这些操作后，您可以使用内部函数使其更快。

尽管我没有在这个特定案例中对其进行测试，但我已经看到使用这些准则可以显着提高性能。

由于您没有将 2 个整数传递给函数，我假设您使用的是数组并想以某种方式迭代它。您现在可以做出选择：制作 2 个数组并使用 min/max 或使用 1 个数组同时使用 a 和 b。单单这个决定就已经可以影响性能了。

如果您有 2 个数组，可以使用对齐的 malloc 在 32 字节边界上分配这些数组，然后使用内部函数进行处理。如果您想要真正的原始性能 - 这就是您要走的路。

F.ex，假设您有 AVX2。（注意：我不确定你是否这样做，你应该使用 CPU id 来检查它！）。转到此处的作弊 sheet：https://software.intel.com/sites/landingpage/IntrinsicsGuide/ 并选择你的毒药。

在这种情况下，您要查找的内在函数可能是：

_mm256_min_epi32
_mm256_max_epi32
_mm256_stream_load_si256

如果您必须对整个数组执行此操作，您可能希望在合并各个项目之前将所有内容保存在一个 __mm256 寄存器中。例如：对每个 256 位向量执行 min/max，当循环完成后，提取 32 位项并对其执行 min/max。

更好的答案：所以...至于编译器。编译器确实尝试优化这类事情，但运行遇到了问题。

如果您处理 2 个不同的数组，编译器必须知道它们是不同的才能对其进行优化。这就是为什么像 restrict 这样的东西存在的原因，它告诉编译器你在编写代码时可能已经知道的这个小东西。

另外，编译器不知道你的内存是对齐的，所以它必须检查这个和分支...对于每个调用。我们不想要这个；这意味着我们希望它内联它的东西。所以，添加 inline，将其放入头文件中，仅此而已。你也可以用aligned给他提示。

您的编译器也没有得到 int* 不会随时间变化的提示。如果无法更改，最好使用 const 关键字告诉他。

编译器使用指令集进行编译。通常，他们已经在使用 SSE，但 AVX2 可以提供很多帮助（正如我在上面的内在函数中所展示的那样）。如果你可以用这些标志编译它，一定要使用它们——它们很有帮助。

运行在发布模式下，在 'fast' 上进行优化编译，看看幕后发生了什么。如果执行所有这些操作，您应该会看到 vpmax... 指令出现在内部循环中，这意味着编译器可以很好地使用内部函数。

我不知道你还想在循环中做什么...如果你使用所有这些指令，你应该在大数组上达到内存速度。

是否可以微优化 "x = max(a,b); y = min(a,b);"？

Is it possible to micro-optimize "x = max(a,b); y = min(a,b);"?

c++

algorithm

optimization

bit-shift

c++11