14

以下は私の擬似コードです。

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

それはうまくいくと思いますが、それは C++ で最も効率的な方法ですか?

4

13 に答える 13

28

最大のものを見つけるには、正確に 3 つの int を調べる必要があります。あなたは3つの比較で6を見ています。3回と2回の比較でできるはずです。

int ret = max(i,j);
ret = max(ret, k);
return ret;
于 2010-02-09T23:02:36.963 に答える
16

擬似コード：

result = i
if j > result:
  result = j
if k > result:
  result = k
return result
于 2010-02-09T23:04:38.363 に答える
13

どうですか

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

2 つの比較、一時的な一時スタック変数の使用なし...

于 2010-02-09T23:13:27.147 に答える
8

現在の方法: http://ideone.com/JZEqZTlj (0.40 秒)

クリスの解決策：

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 秒)

そしてチャールズ・ブレタナの：

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

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

これらのテストのうち、すべてのソリューションの実行時間は他のソリューションと比べて 3% 以内です。最適化しようとしているコードは、そのままでは非常に短いです。そこから 1 つの命令を絞り出すことができたとしても、プログラム全体で大きな違いが生じる可能性は低いです (最新のコンパイラーはその小さな最適化をキャッチする可能性があります)。他の場所で時間を過ごしてください。

編集：テストを更新しましたが、以前はまだ一部を最適化していたことが判明しました。うまくいけば、それはもうありません。

于 2010-02-09T23:49:31.957 に答える
6

このような質問については、最適化コンパイラが何をしているか、ハードウェアで何が利用できるかを知ることに代わるものはありません。基本的なツールがバイナリ比較またはバイナリ max である場合、2 つの比較または max が必要かつ十分です。

私はイグナシオのソリューションを好みます：

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

一般的な最新の Intel ハードウェアでは、コンパイラーは 2 つの比較と 2 つのcmov命令を発行するのが非常に簡単であることに気付くため、条件付き分岐よりも I キャッシュの負荷が小さくなり、分岐予測子のストレスが少なくなります。(また、コードは明確で読みやすいです。) x86-64 を使用している場合、コンパイラはすべてをレジスタに保持します。

あなたの選択が違いを生むプログラムにこのコードを埋め込むのは難しいことに注意してください...

于 2010-02-10T00:13:36.270 に答える
4

私は知的運動として条件付きジャンプを排除するのが好きです。これがパフォーマンスに測定可能な影響を与えるかどうかはわかりませんが:)

#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解決策はおそらくはるかに速いです。

于 2010-02-10T00:13:46.273 に答える
3

これが最も効率的かどうかはわかりませんが、そうかもしれませんし、間違いなく短いです:

int maximum = max( max(i, j), k);
于 2010-02-09T23:53:13.327 に答える
0 
public int maximum(int a,int b,int c){
    int max = a;
    if(b>max)
        max = b;
    if(c>max)
        max = c;
    return max;
}
于 2013-08-14T20:17:17.637 に答える
0 
#include<stdio.h>
int main()
{
    int a,b,c,d,e;
    scanf("%d %d %d",&a,&b,&c);
    d=(a+b+abs(a-b))/2;
    e=(d+c+abs(c-d))/2;
    printf("%d is Max\n",e);
    return 0;
}
于 2019-06-09T17:59:17.830 に答える