wake-up-neo.com

Der schnellste Weg, um den Mittelwert eines Tripels zu finden?

Gegeben sei ein Array von drei numerischen Werten, und ich würde gerne den mittleren Wert der drei wissen.

Die Frage ist, was ist das? am schnellsten Art des die Mitte der drei finden?

Mein Ansatz ist diese Art von Muster - da es drei Zahlen gibt, gibt es sechs Permutationen:

if (array[randomIndexA] >= array[randomIndexB] &&
    array[randomIndexB] >= array[randomIndexC])

Es wäre wirklich schön, wenn mir jemand helfen könnte, einen zu finden eleganter und schneller dies zu tun.

37
Gnark

Wenn Sie nach der effizientesten Lösung suchen, könnte ich mir vorstellen, dass es sich um Folgendes handelt:

if (array[randomIndexA] > array[randomIndexB]) {
  if (array[randomIndexB] > array[randomIndexC]) {
    return "b is the middle value";
  } else if (array[randomIndexA] > array[randomIndexC]) {
    return "c is the middle value";
  } else {
    return "a is the middle value";
  }
} else {
  if (array[randomIndexA] > array[randomIndexC]) {
    return "a is the middle value";
  } else if (array[randomIndexB] > array[randomIndexC]) {
    return "c is the middle value";
  } else {
    return "b is the middle value";
  }
}

Dieser Ansatz erfordert mindestens zwei und höchstens drei Vergleiche. Es ignoriert bewusst die Möglichkeit, dass zwei Werte gleich sind (wie auch Ihre Frage): Wenn dies wichtig ist, kann der Ansatz erweitert werden, um dies ebenfalls zu überprüfen.

23
Tim

Hier gibt es eine Antwort mit Min/Max und keine Verzweigungen ( https://stackoverflow.com/a/14676309/2233603 ). Tatsächlich genügen 4 min/max Operationen, um den Median zu finden, es ist kein Xor erforderlich:

median = max(min(a,b), min(max(a,b),c));

Es gibt jedoch keinen Index für den Medianwert ...

Aufschlüsselung aller Fälle:

a b c
1 2 3   max(min(1,2), min(max(1,2),3)) = max(1, min(2,3)) = max(1, 2) = 2
1 3 2   max(min(1,3), min(max(1,3),2)) = max(1, min(3,2)) = max(1, 2) = 2
2 1 3   max(min(2,1), min(max(2,1),3)) = max(1, min(2,3)) = max(1, 2) = 2
2 3 1   max(min(2,3), min(max(2,3),1)) = max(2, min(3,1)) = max(2, 1) = 2
3 1 2   max(min(3,1), min(max(3,1),2)) = max(1, min(3,2)) = max(1, 2) = 2
3 2 1   max(min(3,2), min(max(3,2),1)) = max(2, min(3,1)) = max(2, 1) = 2
72
Gyorgy Szekely

Es ist möglich, die Abfrage ohne Verzweigungen zu beantworten, wenn die Hardware Min- und Max-Anfragen ohne Verzweigungen beantworten kann (die meisten CPUs können dies heute).

Der Operator ^ bezeichnet bitweise xor.

Input: triple (a,b,c)
1. mx=max(max(a,b),c)
2. mn=min(min(a,b),c)
3. md=a^b^c^mx^mn
4. return md

Das ist richtig, weil:

  • xor ist kommutativ und assoziativ
  • xor bei gleichen Bits ergibt Null
  • x oder mit null ändert das Bit nicht

Die geeigneten Min/Max-Funktionen sollten für Int/Float ausgewählt werden ..__ Wenn nur positive Fließkommandos vorhanden sind, ist es möglich, Integer Min/Max direkt in der Fließkommadarstellung zu verwenden (dies kann wünschenswert sein, da Integer-Operationen im Allgemeinen schneller sind ).

In dem unwahrscheinlichen Fall, dass die Hardware nicht min/max unterstützt, können Sie Folgendes tun:

max(a,b)=(a+b+|a-b|)/2
min(a,b)=(a+b-|a-b|)/2

Dies ist jedoch nicht korrekt, wenn Float-Operationen verwendet werden, da das genaue Minimum und Maximum erforderlich ist und nicht etwas, was dem sehr nahe kommt. Glücklicherweise wird Float Min/Max seit Ewigkeiten in Hardware unterstützt (auf x86, ab Pentium III und höher).

33
Max

Dies kann maximal mit zwei Vergleichen erfolgen.

int median(int a, int b, int c) {
    if ( (a - b) * (c - a) >= 0 ) // a >= b and a <= c OR a <= b and a >= c
        return a;
    else if ( (b - a) * (c - b) >= 0 ) // b >= a and b <= c OR b <= a and b >= c
        return b;
    else
        return c;
}
18
Zach Conn

Und noch eine Idee. Es gibt drei Zahlen {a,b,c}. Dann:

middle = (a + b + c) - min(a,b,c) - max(a,b,c);

Natürlich müssen wir uns an numerische Grenzen erinnern ...

11
jacek.ciach

So können Sie dies nur mit Hilfe von Bedingungen ausdrücken:

int a, b, c = ...
int middle = (a <= b) 
    ? ((b <= c) ? b : ((a < c) ? c : a)) 
    : ((a <= c) ? a : ((b < c) ? c : b));

EDITS: 

  1. Von @Pagas gefundene Fehler wurden behoben.
  2. @Pagas wies auch darauf hin, dass dies mit weniger als 5 Bedingungen nicht möglich ist, wenn Sie nur mit Bedingungen arbeiten. Sie können dies jedoch durch Verwendung von temporären Variablen oder Werteverschiebungen reduzieren. 
  3. Ich würde hinzufügen, dass es schwer vorherzusagen ist, ob eine reine Bedingungs- oder Zuweisungslösung schneller wäre. Es hängt wahrscheinlich davon ab, wie gut die JIT ist, aber ich denke, die bedingte Version wäre für den Optimierer einfacher zu analysieren.
7
Stephen C

Ich habe keine Lösung gesehen, die Swaps implementiert:

int middle(int a, int b, int c) {
    // effectively sort the values a, b & c
    // putting smallest in a, median in b, largest in c

    int t;

    if (a > b) {
        // swap a & b
        t = a;
        a = b;
        b = t;
    }

    if (b > c) {
        // swap b & c
        t = b;
        b = c;
        c = t;

        if (a > b) {
            // swap a & b
            t = a;
            a = b;
            b = t;
        }
    }

    // b always contains the median value
    return b;
}
4
mckamey

Sie könnten das genauso gut auf die einfachste Art und Weise schreiben. Wie Sie sagten, gibt es nur sechs Möglichkeiten. Keine vernünftige Herangehensweise wird schneller oder langsamer sein, also nehmen Sie einfach etwas leicht lesbares. 

Ich würde min () und max () für die Prägnanz verwenden, aber drei verschachtelte if/thens wären genauso gut, denke ich. 

3
Mark Bessey

Wenn Sie feststellen müssen, dass einer der X-Werte einige Kriterien erfüllt, müssen Sie diesen Wert mindestens mit den anderen X-1-Werten vergleichen. Für drei Werte bedeutet dies mindestens zwei Vergleiche. Da dies "Finden Sie den Wert, der nicht der kleinste und nicht der größte ist", können Sie mit nur zwei Vergleichen davonkommen.

Sie sollten sich dann auf das Schreiben des Codes konzentrieren, damit Sie ganz genau sehen können, was vor sich geht, und es einfach halten. Hier bedeutet dies verschachtelte ifs. Dadurch kann die JVM diesen Vergleich zur Laufzeit so weit wie möglich optimieren.

Sehen Sie sich die Lösung an, die Tim ( Schnellster Weg zum Mittelwert eines Dreifachen? ) Bietet, um ein Beispiel dafür zu sehen. Die vielen Codezeilen stellen nicht unbedingt einen größeren Code dar als verschachtelte Fragezeichen.

median = (a+b+c) - Math.min(Math.min(a,b),c) - Math.max(Math.max(a,b),c)

Dies ist die grundlegende, ich weiß nicht, wie effizient dies funktionieren würde, aber diese Funktionen verwenden, wenn Bedingungen immerhin. Wenn Sie möchten, können Sie diese Anweisung in if-else-Anweisungen umwandeln, es wird jedoch einige Zeit dauern. Warum so faul?

2
Melih Yıldız'

Hier ist die Antwort in Python, aber dieselbe Logik gilt für das Java-Programm.

def middleOfThree(a,b,c):
    middle = a
    if (a < b and b < c) or (c < b and b < a):
        middle = b 
    Elif (a < c and c < b) or (b < c and c < a):
        middle = c    
    print 'Middle of a=%d, b=%d, c=%d is %d' % (a,b,c,middle)

middleOfThree(1,2,3)
middleOfThree(1,3,2)
middleOfThree(2,1,3)
middleOfThree(2,3,1)
middleOfThree(3,2,1)
middleOfThree(3,1,2)
1
Pike Zarate

Basierend auf der hervorragenden Antwort von Gyorgy können Sie den Medianindex ohne Verzweigungen erhalten, indem Sie min/max durch bedingte Bewegungen ersetzen:

int i = (array[A] >= array[B]) ? A : B;
int j = (array[A] <= array[B]) ? A : B;
int k = (array[i] <= array[C]) ? i : C;
int median_idx = (array[j] >= array[k]) ? j : k;

javac sollte für jede dieser ternären Zuweisungen einen ConditionalNode generieren, der in Assembly cmp/cmov-Paare übersetzt wird. Beachten Sie auch, dass die Vergleiche so gewählt wurden, dass bei Gleichheit der erste Index in alphabetischer Reihenfolge zurückgegeben wird.

1
traffaillac

Methode 1

int a,b,c,result;
printf("enter three number");
scanf("%d%d%d",&a,&b,&c);
result=a>b?(c>a?a:(b>c?b:c)):(c>b?b:(a>c?a:c));
printf("middle %d",result);

Methode 2 

int a=10,b=11,c=12;
//Checking for a is middle number or not
if( b>a && a>c || c>a && a>b )
{
    printf("a is middle number");
}

//Checking for b is middle number or not
if( a>b && b>c || c>b && b>a )
{
    printf("b is middle number");
}

//Checking for c is middle number or not
if( a>c && c>b || b>c && c>a )
{
    printf("c is middle number");
}

Methode 3

if(a>b)
{
    if(b>c)
    {
        printf("b is middle one");
    }
    else if(c>a)
    {
        printf("a is middle one");
    }
    else
    {
        printf("c is middle one");
    }
}
else
{
    if(b<c)
    {
        printf("b is middle one");
    }
    else if(c<a)
    {
        printf("a is middle one");
    }
    else
    {
        printf("c is middle one");
    }
}

Ich habe den passenden Wert von den Mittelwert eines Tripels finden

1
manoj yadav

Der einfachste Weg ist die Sortierung ..__ Betrachten Sie zum Beispiel diesen Code:

import Java.util.Arrays;


int[] x = {3,9,2};
Arrays.sort(x); //this will sort the array in ascending order 

//so now array x will be x = {2,3,9};
//now our middle value is in the middle of the array.just get the value of index 1
//Which is the middle index of the array.

int middleValue = x[x.length/2]; // 3/2 = will be 1

Das ist es. So einfach ist das.

Auf diese Weise brauchen Sie die Größe des Arrays nicht zu berücksichtigen. Wenn Sie also 47 verschiedene Werte haben, können Sie diesen Code auch verwenden, um den mittleren Wert zu ermitteln.

1
Ratul Bin Tazul

Einen alten Thread aufstoßen, aber es ist immer noch die kürzeste Lösung, und niemand hat es erwähnt.

Lösung:

int median2(int a, int b, int c) {
    return (a > b) ^ (a > c) ? a : (a > b) ^ (b > c) ? c : b;
}

Tests:

(Tests umfassen alle möglichen Kombinationen, alle drucken 6)

public static void main(String[] args) {

    System.out.println(median(3, 6, 9));
    System.out.println(median(3, 9, 6));
    System.out.println(median(6, 3, 9));
    System.out.println(median(6, 9, 3));
    System.out.println(median(9, 3, 6));
    System.out.println(median(9, 6, 3));
    System.out.println(median(6, 6, 3));
    System.out.println(median(6, 6, 9));
    System.out.println(median(6, 3, 6));
    System.out.println(median(6, 9, 6));
    System.out.println(median(3, 6, 6));
    System.out.println(median(9, 6, 6));
    System.out.println(median(6, 6, 6));

}

Erklärung 1

(a > b) ^ (a > c) false wenn entweder c > a > b oder c < a < b - return a;

ansonsten (a > b) ^ (b > c) false, wenn entweder a > b > c oder a < b < c - return b;

ansonsten Rückgabe c;

Erklärung 2

Nehmen wir an, p = a > b; q = b > c; s = a > c;

Bauen wir eine Karnaugh-Karte

   | 00  01  11  10 (p, q)
---+----------------------
 0 |  b   c   *   a
 1 |  *   a   b   c
(s)|

* bedeutet, dass die Kombination nicht möglich ist (wie a > b; b > c; a < c)

Beachten Sie, dass der rechte Teil ein gespiegelter linker Teil ist und die Karte durch Einführung von t = p ^ q; u = s ^ p vereinfacht werden kann.

   |  0   1 (t)
---+---------
 0 |  b   c  
 1 |  *   a  
(u)|

Also kann die Funktion als geschrieben werden 

private static int median(int a, int b, int c) {
    boolean t = (a > b) ^ (b > c);
    boolean u = (a > b) ^ (a > c);
    if (u)
        return a;
    else if (t)
        return c;
    else
        return b;
}

Inlining von Variablen und Ersetzen von ifs durch?: Gibt die Antwort

int median2(int a, int b, int c) {
    return (a > b) ^ (a > c) ? a : (a > b) ^ (b > c) ? c : b;
}

Die Lösung funktioniert gut, auch wenn einige der Eingänge gleich sind, was nicht offensichtlich ist, aber durchaus logisch.

1
ekaerovets

Dieses wird funktionieren:

template<typename T> T median3_1_gt_2(const T& t1, const T& t2, const T& t3) {
    if (t3>t1) {
        return t1;
    } else {
        return std::max(t2, t3);
    }
}
template<typename T> T median3(const T& t1, const T& t2, const T& t3) {
    if (t1>t2) {
        return median3_1_gt_2(t1, t2, t3);
    } else {
        return median3_1_gt_2(t2, t1, t3);
    }
}

https://github.com/itroot/firing-ground/blob/864e26cdfced8394f8941c8c9d97043da8f998b4/source/median3/main.cpp

1
    if(array[aIndex] > array[bIndex]) {
        if(array[bIndex] > array[cIndex]) return bIndex;
        if(array[aIndex] > array[cIndex]) return cIndex;
        return aIndex;
    } else {
        if(array[bIndex] < array[cIndex]) return bIndex;
        if(array[aIndex] < array[cIndex]) return cIndex;
        return aIndex;
    }
1
azmi
largest=(a>b)&&(a>c)?a:(b>c?b:c);
smallest=(a<b)&&(a<c)?a:(b<c?b:c);
median=a+b+c-largest-smallest;
1
Mykola Lavrenko

Verwenden von idxA bis idxC in ary

int ab = ary[idxA] < ary[idxB] ? idxA : idxB;
int bc = ary[idxB] < ary[idxC] ? idxB : idxC;
int ac = ary[idxA] < ary[idxC] ? idxA : idxC;

int idxMid = ab == bc ? ac : ab == ac ? bc : ab;

indexMiddle zeigt auf den mittleren Wert.

Erläuterung: Von den 3 Minima 2 sind das Gesamtminimum und der andere Wert muss der mittlere Wert sein. Da wir die Gleichheit prüfen, können wir die Indizes in der letzten Zeile vergleichen, anstatt die Array-Werte vergleichen zu müssen.

0
rsp

100% branchfreie Version für ganze Zahlen:

int mid(const int a, const int b, const int c) {
    const int d0 = b - a;
    const int m = (d0 >> 31);
    const int min_ab = a + (d0 & m);
    const int max_ab = a + (d0 & ~m);
    const int d1 = c - max_ab;
    const int min_max_ab_c = max_ab + (d1 & (d1 >> 31));
    const int d2 = min_ab - min_max_ab_c;
    return min_ab - (d2 & (d2 >> 31));
}

Konstruiert mit den verzweigungsfreien Min/Max-Funktionen: 

int min(const int a, const int b) { const int d = b - a; return a + (d & (d >> 31)); }
int min(const int a, const int b) { const int d = a - b; return a - (d & (d >> 31)); }

Es sieht vielleicht nicht schön aus, aber der Maschinencode kann auf einigen Architekturen effizienter sein. Besonders die ohne min/max Anweisungen. Ich habe aber keine Benchmarks zur Bestätigung gemacht.

0
Malström

Sie können ein Array wie folgt verwenden:

private static long median(Integer i1, Integer i2, Integer i3) {

    List<Integer> list = Arrays.asList(
            i1 == null ? 0 : i1,
            i2 == null ? 0 : i2,
            i3 == null ? 0 : i3);

    Collections.sort(list);
    return list.get(1);
}
0
cizek