是否可以微优化“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

在C++中，可以使用std::minmax生成最小值和最大值的std::pair。这是在组合特别容易与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 2

如何：

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

第一行依赖于布尔结果在真在假的情况下的情况下和0的隐式转换为1。

Answer 3

如果你的目的是要减少函数调用找到分钟疯狂的麦克斯，你可以尝试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

时空交易怎么样？

#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 ::极大极小和正确的优化和正确的指令集编译参数。

冗长难看的答案，编译器无法做出使其真的非常快的必要假设。您可以。在这种情况下，您可以更改算法以首先处理所有数据，并且可以强制数据对齐。做所有这些，你可以使用内部函数来加快速度。

尽管我没有在这种特殊情况下对它进行测试，但我已经看到使用这些指导方针可以获得巨大的性能提升。

既然你不及格2点的整数的功能，我使用一个数组，并希望以某种方式遍历它你的假设。您现在可以选择：制作2个阵列并使用最小/最大值或使用1个阵列，同时使用a和b。这一决定本身已经可以影响业绩。

如果你有2个阵列，这些都可以在有排列的malloc的32字节边界分配，然后用内部函数进行处理。如果你想要获得真正的原始表现 - 这是一条走的路。

F.ex，让我们假设你有AVX2。 （注意：我不知道你是否应该这样做，你应该使用CPU ID检查这个！）。去这里的作弊表：https://software.intel.com/sites/landingpage/IntrinsicsGuide/并挑选你的毒药。

你要找的内部函数在这种情况下可能：

• _mm256_min_epi32
• _mm256_max_epi32
• _mm256_stream_load_si256

如果你要为整个数组做到这一点，你可能希望在合并各个项目之前将所有内容保存在一个__mm256寄存器中。例如：每256位向量做一个最小/最大值，当循环完成时，提取32位项目并对其做最小/最大值。

龙更好的回答：所以...至于编译器。编译器确实试图优化这些类型的东西，但遇到问题。

如果您有处理2个不同的阵列，编译器必须知道，他们是为了能够优化它的不同。这就是为什么像restrict这样的东西存在的原因，它可以告诉编译器这个你在编写代码时可能已经知道的小东西。

此外，编译器不知道你的内存对齐，所以它必须检查并支...每个呼叫。我们不想要这个;这意味着我们希望它能够嵌入其内容。所以，加上inline，把它放在一个头文件中就是这样。您也可以使用aligned给他一个提示。

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

编译器使用指令集进行编译。通常情况下，他们已经使用SSE，但AVX2可以提供很多帮助（正如我上面介绍的那样）。如果你可以用这些标志进行编译，一定要使用它们 - 它们有很多帮助。

在发布模式下运行，在'fast'上进行优化编译并查看底下发生了什么。如果你这样做了，你应该看到vpmax...指令出现在内部循环中，这意味着编译器使用内部函数就好了。

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