Was ist der beste Weg, um den Minimal- oder Maximalwert aus einer Reihe von Zahlen zu bekommen?

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

Frage

Lassen Sie uns sagen, ich habe ein Array von Zahlen: [2,3,3,4,2,2,5,6,7,2]

Was ist der beste Weg, um den Minimal- oder Maximalwert in diesem Array zu finden?

Im Moment das Maximum zu bekommen, ich durch das Array am Looping und eine Variable auf den Wert zurückzusetzen, wenn er größer als der vorhandene Wert ist: 

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

var maxValue:Number = 0;

for each (var num:Number in myArray)
{
    if (num > maxValue)
        maxValue = num;
}

Dies scheint einfach nicht wie die leistungsfähigste Art und Weise, dies zu tun (ich versuche, Schleifen zu vermeiden, wann immer möglich).

War es hilfreich?

Lösung

Die theoretischen Antworten von allen anderen sind ordentlich, aber wir pragmatisch sein. Actionscript bietet die Tools, die Sie benötigen, so dass Sie nicht einmal eine Schleife in diesem Fall schreiben müssen!

Beachten Sie zunächst, dass Math.min() und Math.max() beliebige Anzahl von Argumenten annehmen kann. Außerdem ist es wichtig, die apply() Methode zur Verfügung zu Function Objekten zu verstehen. Es ermöglicht Ihnen, Argumente an die Funktion zu übergeben ein Array verwenden. Lassen Sie uns die Vorteile von beiden nehmen: 

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: die „Schleife“ native Code tatsächlich ausgeführt wird (im Flash Player), so dass es schneller ist als für die Minimal- oder Maximalwert sucht eine reine Actionscript-Schleife mit

.

Andere Tipps

Es gibt keine zuverlässige Möglichkeit, das Minimum / Maximum zu erhalten, ohne jeden Wert zu testen. Sie wollen nicht eine Art oder so etwas versuchen, durch das Array zu Fuß sind O (n), die besser als jede Sortieralgorithmus ist, kann im allgemeinen Fall tun.

Wenn

  1. Das Array ist nicht sortiert
  2. Das Finden der Min- und Max erfolgt gleichzeitig

Dann gibt es einen Algorithmus, der die min und max in 3N / 2 Anzahl der Vergleiche findet. Was benötigt man zu tun ist, um die Elemente der Anordnung in Paaren zu verarbeiten. Die größere der beiden sollte mit dem aktuellen max und der kleinere der beiden verglichen werden sollten mit dem aktuellen min verglichen werden. Auch nehmen die man braucht besondere Pflege, wenn das Array ungerade Anzahl von Elementen enthält.

In c ++ Code (Kreditaufnahme einige 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 einfach zu sehen, dass die Anzahl der Vergleiche dauert es ist / 2 3n. Die Schleife läuft n / 2-fache und in jeder Iteration 3-Vergleiche durchgeführt. Dies ist wahrscheinlich das Optimum einer erreichen kann. In diesem Moment kann ich nicht auf eine bestimmte Quelle von diesem Punkt. (Aber ich glaube, ich habe einen Beweis, dass irgendwo gesehen.)

Die rekursive Lösung oberhalb von Mehrdad gegeben, wahrscheinlich erreicht auch diese minimale Anzahl von Vergleichen (die letzte Zeile geändert werden muss). Aber mit der gleichen Anzahl von Vergleich eine iterative Lösung wird immer eine rekursive Lösung schlägt aufgrund Overhead in dem Funktionsaufruf, wie er erwähnte. wenn man jedoch nur, kümmert sich min und max von ein paar Zahlen über die Suche nach (als Eric Belair der Fall ist), wird niemand einen Unterschied in der heutigen Computer feststellen, mit einem der Ansätze oben. Für eine große Array, könnte der Unterschied signifikant sein.

Obwohl diese Lösung und die von Matthew Brubaker gegebene Lösung hat O (n) Komplexität in der Praxis sollte man Esel sorgfältig die versteckten Konstanten beteiligt. Die Zahl der Vergleiche in seiner Lösung ist 2n. Die Beschleunigung gewann mit der Lösung mit 3N / 2 Vergleichen im Gegensatz Vergleiche 2n wäre bemerkbar.

Es sei denn, das Array sortiert ist, das ist das Beste, was Sie bekommen werden. Wenn es sortiert wird, nehmen Sie nur die ersten und letzten Elemente.

Natürlich, wenn es nicht sortiert ist, dann erste Sortierung und packt die ersten und letzten garantiert ist weniger effizient als nur einmal durch Looping. Selbst die besten Sortieralgorithmen an jedem Element suchen mehr als einmal (ein Durchschnitt von O (log N) mal für jedes Element. Das ist O (N * Log N) insgesamt. Ein einfacher Scan einmal durch ist nur O (N).

Wenn Sie in einer Datenstruktur schnellen Zugriff auf das größte Elemente fehlen, werfen Sie einen Blick auf Haufen für eine effiziente Art und Weise Objekte, um in irgendeiner Art zu halten.

Sie haben durch die Array-Schleife, keine andere Möglichkeit, alle Elemente zu überprüfen. Nur eine Korrektur für den Code - wenn alle Elemente negativ sind, wird maxValue 0 am Ende sein. Sie sollten es mit dem kleinstmöglichen Wert für integer initialisieren.
Und wenn Sie das Array suchen gehen oft ist es eine gute Idee, es zu sortieren zuerst, als die Suche ist schneller (binäre Suche) und Minimal- und Maximal Elemente sind nur die erste und die letzte.

Abhängig von, was Sie nennen „best.“ Aus theoretischer Sicht das Problem in weniger als O(n) in einer deterministischen Turing-Maschine nicht lösen kann.

Der naive Algorithmus ist zu Schleife und aktualisiert min, max. Allerdings wird eine rekursive Lösung benötigt wenige Vergleiche als naiver Algorithmus, wenn Sie min erhalten möge, max gleichzeitig (es zu Funktionsaufruf Overhead nicht unbedingt schneller zurückzuführen ist). 

struct MinMax{
   public int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   if (start == end)
      return new MinMax { Min = array[start], Max = array[start] };

   if (start == end - 1)
      return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;

   MinMax res1 = FindMinMax(array, start, (start + end)/2);
   MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
   return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}

Die einfachste Lösung wäre, zu sortieren und zu dem ersten und letzten Einzelteil zu erhalten, obwohl es offensichtlich nicht die schnellsten;)

Die beste Lösung, Performance-weise, das Minimum zu finden oder Maximum ist der naive Algorithmus Sie (mit einer einzigen Schleife) geschrieben.

Math.max () ist eigentlich AS3 Code AVM2 Opcodes kompiliert und als solche nicht mehr „native“ als jede andere AS3-Code. Als Folge ist es nicht unbedingt die schnellste Umsetzung.

Eigentlich gegeben, dass es funktioniert auf Array-Typ, ist es langsamer als sorgfältig geschriebener Code usign Vector:

habe ich einen schnellen Benchmark-Vergleich von mehreren naiven Vektor und Array-Implementierungen von Math.max, mit gskinner des Performancetest (Vector und Array mit identischen Zufallszahlen gefüllt ist). Die schnellste Vector Implementierung erschien mit dem letzten AIR SDK / Release-Player (Flash Player WIN 14,0,0,122 RELEASE, zusammengestellt mit AIR SDK 14) mehr als 3x schneller als Math.max zu sein:

Durchschnitt 3,5 ms für 1 Mio. Werte, im Vergleich zu Math.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 durch die Leistung betrifft, Sie Vector über Array überall dort verwenden, sollten Sie sich in erster Linie können und nicht immer darauf verlassen, auf Standardimplementierungen, vor allem, wenn sie die Verwendung von Array erzwingen

PS: gleiche Umsetzung mit einem für jeden () Schleife 12x langsamer ...

!

Dies ist abhängig von der realen Welt Anwendungsanforderungen.

Wenn Ihre Frage rein hypothetisch ist, dann sind die Grundlagen bereits erläutert. Es ist eine typische Suche vs. Art Problem. Es wurde bereits erwähnt, dass algorithmisch Sie nicht für diesen Fall als O (n) zu erreichen, besser werden.

Wenn Sie jedoch bei der praktischen Anwendung suchen, werden die Dinge noch interessanter. Sie würden dann überlegen müssen, wie groß das Array ist, und die beteiligten Prozesse in dem Hinzufügen und aus dem Datensatz zu entfernen. In diesen Fällen kann es am besten sein, die rechnerischen bei Einfügen / Entfernen Zeit ‚Treffer‘ zu nehmen, indem im laufenden Betrieb zu sortieren. Einfügungen in einen vorsortierten Array sind nicht so teuer.

Die schnellste Abfrage Antwort auf die Anfrage Min Max wird immer von einem sortierten Array sein, denn wie andere schon erwähnt haben, nehmen Sie einfach das erste oder letztes Element - gibt Ihnen einen O (1) Kosten

.

Für ein bisschen mehr von einer technischen Erklärung auf die Rechenkosten beteiligt, und Big O-Notation, überprüfen Sie die Wikipedia-Artikel hier .

Nick.

Wenn Sie das Array bauen einmal und will nur einmal das Maximum finden, Iterieren ist das Beste was Sie tun können.

Wenn Sie das Array ändern wollen und gelegentlich das maximale Element wissen, sollten Sie eine Priorität verwenden Warteschlange . Eines der besten Datenstrukturen für das ist ein Fibonacci Heap wenn diese Nutzung eine zu kompliziert Binary Heap , die langsamer, aber immer noch gut ist.

Minimum und Maximum zu finden, nur zwei Haufen bauen und das Vorzeichen der Zahlen in einem von ihnen ändern.

Bitte beachten Sie, dass die Array Sortierung nur schneller sein wird, dass bestimmte Größe des Arrays Looping nach oben. Wenn Ihr Array klein ist (und es wird wie sein, dass jederzeit), dann ist die Lösung völlig in Ordnung. Aber wenn es vielleicht zu groß erhalten Sie eine bedingte verwenden sollten, die Art Ansatz zu verwenden, wenn das Array klein ist, und die normale Iteration, wenn sie zu groß ist

Wenn Sie sowohl die min und max zugleich finden wollen, kann die Schleife 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;
}

Dies sollte erhalten erreichen O (n) Zeitpunkt.

Kürzeste Weg:

Math.min.apply (null, array); // Das wird wieder min Wert von Array
  Math.max.apply (null, array); // dies max Wert von Array zurück

otherway von min & max-Wert von Array bekommen 

 function maxVal(givenArray):Number
    {
    var max = givenArray[0];
    for (var ma:int = 0; ma<givenArray.length; ma++)
    {
    if (givenArray[ma] > max)
    {
    max = givenArray[ma];
    }
    }
    return max;
    }

    function minVal(givenArray):Number
    {
    var min = givenArray[0];
    for (var mi:int = 0; mi<givenArray.length; mi++)
    {
    if (givenArray[mi] < min)
    {
    min = givenArray[mi];
    }
    }
    return min;
    }

Wie Sie sehen können, ist der Code in diesen beiden Funktionen sehr ähnlich. Die Funktion setzt eine Variable - max (oder min) und läuft dann durch das Array mit einer Schleife, die jeweils nächste Element benötigt. Wenn das nächste Element höher als der Strom ist, stellt auf max (oder min). Am Ende kehrt die Nummer ein.

Es gibt eine Reihe von Möglichkeiten, dies getan werden kann.

  1. Brute-Force. Lineare Suche sowohl für min und max getrennt. (2N Vergleiche und 2N Stufen)
  2. Iterate linear und überprüfen Sie jede Zahl für beide min und max. (2N-Vergleiche)
  3. Verwenden Sie Teile und herrsche. (zwischen 2N und 3N / 2 Vergleiche)
  4. Vergleichen von Paaren erklärt unter (3N / 2 Vergleiche)

Wie max zu finden. und min. mit minimalen Vergleichen in Array?

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

Algorithmus MaxMin (erster, letzter, max, min)

// Dieser Algorithmus speichert die höchste und die niedrigste Element

// Werte des globalen Array A in den globalen Variablen max und min

// tmax und tmin sind temporäre globale Variablen 

{
if (first==last) //Sub-array contains single element
 {
    max=A[first];
    min=A[first];
 }
 else if(first+1==last) //Sub-array contains two elements
  {
     if(A[first]<A[Last])
      {
      max=a[last];  //Second element is largest
      min=a[first]; //First element is smallest
      }
   else
   {
     max=a[first]; //First element is Largest 
     min=a[last];  //Second element is smallest
   }
}
else
 //sub-array contains more than two elements
{
 //Hence partition the sub-array into smaller sub-array 
 mid=(first+last)/2;
 //Recursively solve the sub-array
 MaxMin(first,mid,max,min);
 MaxMin(mid+1,last,tmax,tmin);
 if(max<tmax)
  {
     max=tmax;
  }
    if(min>tmin)
  {
   min=tmin;
  }
 }
}

Im Folgenden finden Sie 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);
}

Amazed niemand erwähnte Parallelität hier.

Wenn Sie wirklich eine riesige Auswahl bekommen, können Sie parallel für, auf Teilbereiche. Am Ende vergleicht alle Unterbereiche. Aber Parallelität kommt auch einige Strafe Breite, so würde dies optimieren nicht auf kleine Arrays. Allerdings, wenn Sie große Datenmengen haben es beginnt Sinn zu machen, und Sie eine Zeitteilungs-Reduzierung der Menge an Fäden erhalten kurz vor der Durchführung des Tests.

Finden max Werte aus einem Array Mal sehen, wie min, max Werte zu erhalten, indem ein einzelnes funtion mit 

public void findMaxValue(){
   int[] my_array = {1,2,,6,5,8,3,9,0,23};
   int max = my_array[0];
   for(int i=1; i<my_array.length; i++)
   {
      if(my_array[i] > max)
         max = my_array[i];
   }
   return max; 
}

Gleiche kann für find min-Wert tun

Nach jeder Kommentare lesen (vielen Dank für Ihr Interesse), fand ich, dass die „beste“ Weg (geringste Menge an Code, leistungsfähigste), dies zu tun einfach das Array sortieren sollte, und greifen dann den ersten Wert in der 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];

Das funktioniert auch für ein Array von Objekten - Sie einfach die 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, das jemand anderes irgendwann hilft!

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top