3 つの int の最大値を見つける最も効率的な方法

StackOverflow https://stackoverflow.com/questions/2233166

  •  19-09-2019
  •  | 
  •  

質問

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

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

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

役に立ちましたか？

解決

あなたは以上でも以下でもなく、正確に3 int型を見てする必要はありません最大を検索するには。あなたは3と比較して6を見ています。あなたは3と2を比較して、それを行うことができる必要があります。

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

他のヒント

擬似コード：

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

どの程度

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

2つの比較、過渡的な一時的なスタック変数を用いない...

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

クリスの解決策:

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

http://ideone.com/hlnl7QZX (0.39秒)

イグナシオ・バスケス＝エイブラムスによる解決策:

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 命令を絞り出すことができたとしても、プログラム全体に大きな違いが生じる可能性は高くありません (最新のコンパイラーはその小さな最適化をキャッチする可能性があります)。他の場所で時間を過ごしてください。

編集： テストを更新したところ、以前はまだ一部が最適化されていたことが判明しました。もうそうではないことを願います。

このような質問については、をお使いの最適化コンパイラがやっているだけで何とハードウェア上で利用できるだけで何かを知るために勝るものははありません。あなたが持っている基本的なツールは、2つの比較またはMAXの両方の必要かつ十分なものである、バイナリ比較またはバイナリ最大である場合。

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

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

一般的な現代のIntelハードウェア上で、コンパイラはそれが非常に簡単に条件分岐より分岐予測器の上にI-キャッシュ上の小さな負荷の少ないストレスを置くだけで2つの比較および2つのcmov命令を発するようにわかりますので。あなたはx86-64のを使用している場合（また、コードが明確で読みやすいです。）、コンパイラがさえレジスタ内のすべてのものを維持します。

あなたはハードのプログラムにこのコードを埋め込むために押されるしようとしている注意してください。のあなたの選択は違いがどこ...

私は知的な運動として、条件付きジャンプを排除したいです。これは、パフォーマンス上の任意の測定可能な効果を持っているかどうか私も分からない：）

#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ソリューションは、はるかに高速である、おそらくされます。

：これが最も効率的であるかどうか、それはあるかもしれない、それは間違いなく短いだ場合は、

わかりません 

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

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 ...); }

public int maximum(int a,int b,int c){
    int max = a;
    if(b>max)
        max = b;
    if(c>max)
        max = c;
    return max;
}

私はあなたのコンピューティングリソースを無駄にしないようにしようと、パフォーマンスについて話している「最も効率的」で考えます。しかし、あなたはあなたのソースコードの可読性について多分少ないコードを書くかを参照する可能性があります。私は以下の例を提供しています、そしてあなたが受け取った答えから別のバージョンを好む場合、あなたが有益な何かを見つけるかどうかを評価またはすることができます。

/* 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);
    }
}

#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;
}

3つの数字のグレイテスト

int greater = a>b ? (a>c? a:c) :(b>c ? b:c); 
System.out.println(greater);
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top