寻找三个整数中最大的方法最有效的方式

Question

下面是我的伪代码。

function highest(i, j, k)
{
  if(i > j && i > k)
  {
    return i;
  }
  else if (j > k)
  {
    return j;
  }
  else
  {
    return k;
  }
}

我认为那会起作用，但在C++中这是最有效的方法吗？

- Stephano

---

你能用这个吗？http://www.cplusplus.com/reference/algorithm/max/ - alex

如果这是一份作业，那么没关系，因为提问者已经做出了尝试，展示了他的代码并且在寻求改善。这符合在SO上发布作业问题的所有准则。 - Jasarien

这更多是一个效率问题。我知道这会给我正确的答案，但作为程序员，我如何知道我正在快速高效地完成它？ - Stephano

@Stephano：您可以对其进行分析，确定它是否是程序主要的运行缓慢原因。常见错误是过于担心所有内容的效率；只需让代码易于理解和编写，并让编译器发挥作用即可。 - GManNickG

以下是最高效的方式：/* 前提条件：i 是三个值中最大的。*/ int max(int i, int j, int k) { return i; } 或者可能只需返回42。 - Skurmedel

Answer 1

要找出最大值，你需要仅查看3个整数，不多不少。但是你正在使用6个整数和3次比较。你应该能够用3次或2次比较来完成。

int ret = max(i,j);
ret = max(ret, k);
return ret;

- Chris H

---

可以写一个简短的函数：template <typename T> const T& max(const T& pA, const T& pB, const T& pC){ return max(pA, max(pB, pC)); }。 - GManNickG

max(i, max(j, k)) 可以简化为一行代码。我也喜欢模板版本。 - Nick Bedford

@Duncan: 你对于何时是内联函数的理解是错误的，而且既然这个问题是关于 C++ 的，我们正在讨论 std::max。在 C++ 中，一个名为 'max' 的宏定义是彻头彻尾的灾难。 - Roger Pate

@Duncan，@Chris：我们称之为std::max，然后就完成了。@Chris：GNU STL将中位数定义为私有函数，也许这就是你想到的。 - Potatoswatter

但是在第二行访问ret不也被认为是另一个“查找”吗？这样会使得总数变成4而不是3吧？ - jasonline

Answer 2

伪代码：

result = i
if j > result:
  result = j
if k > result:
  result = k
return result

- Ignacio Vazquez-Abrams

---

我喜欢你只使用了if语句。这是一个简洁的答案。 - Stephano

太好了！非常清晰，如果硬件有像cmov这样的预测指令，编译器就很可能会使用它们。+1（但愿我能超越邪恶的max并给予+10）。 - Norman Ramsey

非常好的回答。非常简单，没有试图聪明。+1 谦虚。 - IV.

Answer 3

怎么样？

return i > j? (i > k? i: k): (j > k? j: k);

两个比较，不使用瞬态临时堆栈变量...

- Charles Bretana

---

很棒。既迷人又刺眼。 - Skurmedel

+1 给第一个提出一行解决方案的人。我可能厌恶试图将一切变得更短，但时不时总有人向我展示一个令人印象深刻的一行代码。 - Stephano

Answer 4

你目前的方法: http://ideone.com/JZEqZTlj (0.40秒)

Chris的解决方案:

int ret = max(i,j);
ret = max(ret, k);
return ret;

http://ideone.com/hlnl7QZX（0.39秒）

由Ignacio Vazquez-Abrams提供的解决方案：

result = i;
if (j > result)
  result = j;
if (k > result)
  result = k;
return result;

http://ideone.com/JKbtkgXi (0.40秒)

还有Charles Bretana的:

return i > j? (i > k? i: k): (j > k? j: k);

http://ideone.com/kyl0SpUZ (0.40秒)

在这些测试中，所有解决方案的执行时间相差不到3%。你试图优化的代码已经非常简短了。即使你能将其中的一条指令压缩掉，它也很难对整个程序产生巨大影响（现代编译器可能会捕捉到这个小优化）。请把时间花在其他地方。

编辑：更新了测试，结果发现之前它仍然优化了部分内容。希望现在不再优化。

- Ponkadoodle

---

好的，我对更新后的版本（稍微）更满意了。但是SO不允许我删除-1（“投票过时，除非此答案被编辑”），抱歉。 - sfussenegger

哇，太棒了。我不知道ideone的存在。这让我在失眠时有事可做 :)。 - Stephano

Answer 5

对于这样的问题，没有什么可以替代了解你的优化编译器正在做什么以及硬件上有什么可用的。如果你拥有的基本工具是二进制比较或二进制最大值，那么两个比较或最大值都是必要且充分的。

我更喜欢Ignacio的解决方案：

result = i;
if (j > result)
  result = j;
if (k > result)
  result = k;
return result;

因为在常见的现代Intel硬件上，编译器非常容易发出只有两个比较和两个cmov指令的代码，这会对I-cache产生较小的负荷和分支预测器产生较小的压力，而不是条件分支。(此外，这段代码清晰易读。)如果你使用的是x86-64，编译器甚至会将所有内容保留在寄存器中。

请注意，您可能很难将此代码嵌入到一个需要做出选择的程序中...

- Norman Ramsey

Answer 6

作为一种智力练习，我喜欢消除条件跳转。虽然我不知道这是否对性能有任何可衡量的影响 :)

#include <iostream>
#include <limits>

inline int max(int a, int b)
{
    int difference = a - b;
    int b_greater = difference >> std::numeric_limits<int>::digits;
    return a - (difference & b_greater);
}

int max(int a, int b, int c)
{
    return max(max(a, b), c);
}

int main()
{
    std::cout << max(1, 2, 3) << std::endl;
    std::cout << max(1, 3, 2) << std::endl;
    std::cout << max(2, 1, 3) << std::endl;
    std::cout << max(2, 3, 1) << std::endl;
    std::cout << max(3, 1, 2) << std::endl;
    std::cout << max(3, 2, 1) << std::endl;
}

这种位操作只是为了好玩，cmov 解决方案可能更快。

- fredoverflow

---

移位加二进制与操作真是巧妙！ - Ponkadoodle

Answer 7

不确定这是否是最有效的方法，但可能是，并且肯定更短：

int maximum = max( max(i, j), k);

- Scott Smith

Answer 8

有一个提案将其纳入N2485下的C++库中。该提案很简单，因此我在下面包含了相关的代码。显然，这需要可变模板。

template < typename T >
const T & max ( const T & a )
{ return a ; }

template < typename T , typename ... Args >
const T & max( const T & a , const T & b , const Args &... args )
{ return  max ( b > a ? b : a , args ...); }

- Sam Mokari

Answer 9

在C++中找到2个或多个数字的最大值或最小值的最简单方法是：

int a = 3, b = 4, c = 5;
int maximum = max({a, b, c});

int a = 3, b = 4, c = 5;
int minimum = min({a, b, c});

你可以提供任意数量的变量。

有趣的是，它也非常高效，至少与Ignacio Vazquez-Abrams的解决方案（https://godbolt.org/z/j1KM97）一样高效：

        mov     eax, dword ptr [rsp + 8]
        mov     ecx, dword ptr [rsp + 4]
        cmp     eax, ecx
        cmovl   eax, ecx
        mov     ecx, dword ptr [rsp]
        cmp     eax, ecx
        cmovl   eax, ecx

与GCC类似，MSVC在循环中会出现混乱。

- tanmay001

---

我相信这是最高效和现代的答案。 - r4bb1t

它在头文件<algorithm>中定义为模板constexpr T max (initializer_list il, Compare comp); - Naman Jain

Answer 10

我认为你所说的“最高效”是指性能，尽量不浪费计算资源。但你可能也在谈论写更少的代码，或者关于源代码的可读性。我在下面提供了一个例子，你可以评估是否有用，或者你更喜欢从你收到的答案中选择另一个版本。

/* Java version, whose syntax is very similar to C++. Call this program "LargestOfThreeNumbers.java" */
class LargestOfThreeNumbers{
    public static void main(String args[]){
        int x, y, z, largest;
        x = 1;
        y = 2;
        z = 3;
        largest = x;
        if(y > x){
            largest = y;
            if(z > y){
                largest = z;
            }
        }else if(z > x){
            largest = z;
        }
        System.out.println("The largest number is: " + largest);
    }
}

- Jaime Montoya