Effizienteste Weg, die größte von drei ints zu finden

Question

Unten ist mein Pseudo-Code.

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

ich denke, das funktioniert, aber ist, dass die effizienteste Art und Weise in C ++?

Answer 1

Um die größte notwendigen Informationen auf genau 3 ints suchen, nicht mehr und nicht weniger. Sie befinden sich in 6 mit 3 vergleicht. Sie sollten es tun können in 3 und 2 vergleicht.

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

Answer 2

Pseudocode:

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

Answer 3

Wie wäre es

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

zwei Vergleiche, keine Verwendung von transienten temporären Stapelvariablen ...

Answer 4

Ihre aktuelle Methode: http://ideone.com/JZEqZTlj (0.40s)

Chris Lösung:

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

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

Lösung von Ignacio Vazquez-Abrams:

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

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

Und Charles Bretana ist:

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

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

Von diesen Tests werden alle Lösungen nehmen innerhalb von 3% der Menge an Zeit wie die anderen auszuführen. Der Code, den Sie optimieren möchten, ist extrem kurz, wie es ist. Auch wenn Sie in der Lage 1 Anweisung drücken aus ihm heraus, ist es nicht wahrscheinlich einen großen Unterschied über die Gesamtheit des Programms zu machen (moderne Compiler könnte, dass kleine Optimierung fangen). Verbringen Sie Ihre Zeit an anderer Stelle.

EDIT: Aktualisiert die Tests stellt sich heraus, es war immer noch Teile davon zu optimieren, bevor er aus. Hoffentlich ist es nicht mehr.

Answer 5

Für eine Frage wie diese, gibt es keinen Ersatz für das Wissen, genau das, was Ihr optimierenden Compiler tut, und genau das, was auf der Hardware verfügbar ist . Wenn das grundlegende Werkzeug haben Sie Binärvergleich oder Binär-max, zwei Vergleiche oder maxs sind notwendig und ausreichend ist.

ziehe ich Ignacio Lösung:

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

, weil über die gemeinsame moderne Intel-Hardware, wird der Compiler es extrem einfach findet nur zwei Vergleiche zu emittieren und zwei cmov Anweisungen, die eine geringere Belastung auf der I-Cache legen und weniger Stress auf dem Verzweigungsprädiktor als bedingte Verzweigungen. (Auch der Code ist klar und leicht zu lesen.) Wenn Sie x86-64 verwenden, wird der Compiler auch alles in den Registern halten.

Beachten Sie in ein Programm einzubetten diesen Code hart bedrängt werden werden , wo Ihre Wahl macht einen Unterschied ...

Answer 6

Ich mag bedingte Sprünge als geistige Übung zu beseitigen. Ob dies einen messbaren Effekt auf die Leistung habe ich keine Ahnung aber:)

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

Dieses Bit Fummeln ist nur zum Spaß, die cmov Lösung ist wahrscheinlich viel schneller.

Answer 7

Nicht sicher, ob dies die effizienteste ist oder nicht, aber es könnte sein, und es ist auf jeden Fall kürzer:

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

Answer 8

Es gibt einen Vorschlag diese in die Bibliothek unter N2485 C ++ enthalten. Der Vorschlag ist einfach, so dass ich den sinnvollen Code unten enthalten haben. Offensichtlich ist dies setzt voraus, variadische Vorlagen

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

Answer 9

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

Answer 10

ich glaube, durch „effizienteste“ Sie über die Leistung sprechen, nicht versuchen, IT-Ressourcen zu verschwenden. Aber man könnte mit Bezug zu weniger Codezeilen oder vielleicht über die Lesbarkeit des Quellcodes zu schreiben. Ich bin ein Beispiel unter Bereitstellung, und Sie können beurteilen, wenn Sie etwas nützlich finden, oder wenn Sie eine andere Version von den Antworten bevorzugen Sie erhalten haben.

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

Answer 11

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

Answer 12

Greatest von 3 Zahlen

int greater = a>b ? (a>c? a:c) :(b>c ? b:c); 
System.out.println(greater);