Was ist der beste Weg, um den minimalen oder maximalen Wert von einem Array von Zahlen zu erhalten?

Den theoretischen Antworten von allen anderen sind alle nett, aber seien wir pragmatisch. ActionScript bietet die tools, die Sie benötigen, so dass Sie nicht selbst schreiben eine Schleife, in diesem Fall!

Beachten Sie zunächst, dass Math.min() und Math.max() können eine beliebige Anzahl von Argumenten. Es ist auch wichtig zu verstehen, die apply() Methode zur Verfügung, um Function Objekte. Es ermöglicht Ihnen die Argumente an die Funktion mit einem Array. Lassen Sie uns den Vorteil von beiden:

var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);

Hier ist der beste Teil: der "loop" ist eigentlich die Ausführung von nativen code (in Flash Player), so dass es ist schneller als die Suche nach der minimalen oder maximalen Wert mit einem reinen ActionScript-Schleife.

InformationsquelleAutor der Antwort joshtynjala

Wenn

1. Das array ist nicht sortiert
2. Finden, die min und max ist gleichzeitig durchgeführt

Dann gibt es einen Algorithmus, der Sie findet, min-und max-3n/2 Anzahl der Vergleiche. Was man tun muss, ist ein Prozess, der Elemente des Arrays paarweise. Der größere der beiden, sollten verglichen werden mit der aktuellen max und das kleinere der beiden verglichen werden sollte, mit dem Strom min. Auch braucht man Besondere Vorsicht, wenn das Feld enthält ungerade Anzahl von Elementen.

In c++ - code ("borrowing code von Mehrdad).

struct MinMax{
   int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   MinMax  min_max;
   int index;
   int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
   if ( n%2 != 0 ){//if n is odd

     min_max.Min = array[start];
     min_max.Max = array[start];

     index = start + 1;
   }
   else{//n is even
     if ( array[start] < array[start+1] ){
       min_max.Min = array[start];
       min_max.Max = array[start+1];
     }
     else{
       min_max.Min = array[start+1];
       min_max.Max = array[start];
     }
     index = start + 2;
   }

   int big, small;
   for ( int i = index; i < n-1; i = i+2 ){
      if ( array[i] < array[i+1] ){ //one comparison
        small = array[i];
        big = array[i+1];
      }
      else{
        small = array[i+1];
        big = array[i];
      }
      if ( min_max.Min > small ){ //one comparison
        min_max.Min = small;
      }
      if ( min_max.Max < big ){ //one comparison
        min_max.Max = big;
      }
   }

   return min_max;
}

Es ist sehr leicht zu sehen, dass die Anzahl der Vergleiche, die es nimmt, ist 3n/2. Läuft die Schleife n/2 mal und in jeder iteration werden 3 Vergleiche durchgeführt werden. Dies ist wahrscheinlich das optimum kann man erreichen. In diesem moment, ich kann nicht zeigen Sie auf eine bestimmte Quelle. (Ich denke aber, dass ich gesehen habe, ein Beweis dafür, dass irgendwo.)

Die rekursive Lösung von Mehrdad oben, wohl auch erreicht, diese minimale Anzahl von vergleichen (die Letzte Zeile muss geändert werden). Aber mit der gleichen Anzahl von vergleichen, die eine iterative Lösung immer schlagen eine rekursive Lösung aufgrund der overhead in der Funktionsaufruf, wie er erwähnt. Wenn man jedoch kümmert sich nur über die Suche nach min und max ein paar zahlen (als Eric Belair hat), wird niemand bemerken einen Unterschied in der heutigen computer mit einem der Ansätze vor. Für ein großes array der Unterschied erheblich sein können.

Obwohl sich diese Lösung und die Lösung von Matthew Brubaker hat O(n) Komplexität, in der Praxis sollte man sorgfältig beurteilen, die versteckten Konstanten beteiligt. Die Anzahl der Vergleiche in seine Lösung ist 2n. Der speedup gewann mit der Lösung mit 3n/2 Vergleiche, im Gegensatz zu 2n Vergleiche würde sichtbar sein.

InformationsquelleAutor der Antwort

Müssen Sie eine Schleife durch das array, keine andere Möglichkeit zu prüfen, alle Elemente. Nur eine Korrektur für den code - wenn alle Elemente negativ sind, maxValue auf 0 am Ende. Sollten Sie initialisieren es mit der minimal mögliche Wert für integer.

Und wenn Sie gehen, um zu suchen das array viele Male, ist es eine gute Idee, Sortieren Sie zuerst als die Suche ist schneller (binäre Suche) und die minimale und maximale Elemente sind nur der erste und der Letzte.

InformationsquelleAutor der Antwort Rumen Georgiev

Math.max() ist eigentlich as3-code, kompiliert, AVM2-opcodes, und als solche ist nicht mehr "native" als jede andere as3-code. Als Folge, es ist nicht unbedingt die Schnellste Implementierung.

Eigentlich gegeben, dass es funktioniert auf Array-Typ, es ist langsamer als sorgfältig geschriebenen code usign Vektor:

Habe ich eine schnelle benchmark-Vergleich der verschiedenen naive Vektor-und Array-Implementierungen der Mathematik.max, mit gskinner ist PerformanceTest (Vektor-und Array wird gefüllt mit identischen Zufallszahlen).
Der Schnellste Vektor-Umsetzung zu sein schien, mehr als 3x schneller als Mathe.max mit der letzten AIR-SDK/release-player (flash-player GEWINNEN 14,0,0,122 VERSION, kompiliert mit den AIR-SDK-14):

Durchschnitt 3,5 ms für 1.000.000 Werte, im Vergleich zu Mathe.max() durchschnittlich 11ms :

function max(values:Vector.<Number>):Number
{
    var max:Number = Number.MIN_VALUE;
    var length:uint = values.length;
    for (var i:uint = 0; i < length ; ++i)
        if (values[i] > max)
            max = values[i];
    return max;
}

Schlussfolgerung ist, dass, wenn Sie sind besorgt über die Leistung, die Sie verwenden sollten, Vektor über Array-überall können Sie in den ersten Platz, und nicht immer verlassen sich auf Standard-Implementierungen, vor allem, wenn Sie erzwingen Sie die Verwendung des Array -

PS:gleiche Implementierung mit einer for-each () - Schleife 12x langsamer ...!

InformationsquelleAutor der Antwort jauboux

Wenn Sie das array einmal und wollen das maximum nur einmal Durchlaufen, ist das beste, was Sie tun können.

Wenn Sie möchten, ändern Sie das array und gelegentlich auch wollen zu wissen die maximale element verwenden, sollten Sie Priorität. Eine der besten Datenstrukturen für die ist Fibonacci-Heap, wenn das zu kompliziert ist, verwenden Sie eine Binary Heap, die ist langsamer, aber immer noch gut.

Zu minimum und maximum finden, einfach bauen zwei Haufen, und ändern Sie die Vorzeichen der zahlen in einem von Ihnen.

InformationsquelleAutor der Antwort martinus

Wenn Sie möchten, finden sowohl die min und max in der gleichen Zeit, die Schleife kann wie folgt geändert werden:

int min = int.maxValue;
int max = int.minValue;

foreach num in someArray {
  if(num < min)
    min = num;
  if(num > max)
    max = num;
}

Dürfte dies erreichen O(n) timing.

InformationsquelleAutor der Antwort Matthew Brubaker

Gibt es eine Reihe von Möglichkeiten, dies getan werden kann.

1. Brute-force. Lineare Suche für min und max getrennt. (2N
   Vergleiche und 2N Schritte)
2. Linear Durchlaufen und prüfen jede Zahl für min und max. (2N Vergleiche)
3. Verwenden und herrsche". (Zwischen 2N und 3N/2 Vergleiche)
4. Vergleichen von Paaren, die unten erklärt (3N/2 Vergleiche)

So finden Sie max. und min. in der Reihe, mit einem minimum an vergleichen?

Wenn Sie wirklich paranoid über Geschwindigkeit, Laufzeit & Anzahl der Vergleiche, siehe auch
http://www.geeksforgeeks.org/maximum-and-minimum-in-an-array/

InformationsquelleAutor der Antwort Shogo Warrior

Unten ist die Lösung mit o(n):-

public static void findMaxAndMinValue(int A[]){
    int min =0, max = 0;
    if(A[0] > A[1] ){
        min = A[1];
        max = A[0];
    }else{
        max = A[1];
        min = A[0];
    }
    for(int i = 2;i<A.length ;i++){
        if(A[i] > max){
            max = A[i];
        }
        if(min > A[i]){
            min = A[i];
        }
    }
    System.out.println("Maxinum Value is  "+min+" & Minimum Value is  "+max);
}

InformationsquelleAutor der Antwort Ajay

Nach der Lektüre jeder ' s Kommentare (vielen Dank für Ihre Interesse), fand ich, dass die "beste" Möglichkeit (geringste Menge an code, die am besten durchführen) zu tun, war einfach Sortieren Sie das Array, und dann nehmen Sie den ersten Wert im Array:

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

myArray.sort(Array.NUMERIC);

var minValue:int = myArray[0];

Funktioniert das auch für ein Array von Objekten - Sie verwenden einfach den Array.sortOn () - Funktion und eine Eigenschaft angeben:

//Sample data
var myArray:Array /* of XML */ = 
    [
    <item level="2" name="a" />
    <item level="3" name="b" />
    <item level="3" name="c" />
    <item level="2" name="d" />
    <item level="5" name="e" />
    ]

//Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);

var lowestLevel:int = myArray[0].@level;

Ich hoffe, dies hilft jemand anderes eines Tages!

InformationsquelleAutor der Antwort Eric Belair