Bester Algorithmus zur Bestimmung von hoch und niedrig in einer Reihe von Zahlen?

Question

Ich benutze Pseudo-Code hier, aber das ist in JavaScript. Mit dem möglichst effizienten Algorithmus versuche ich, die Höhe und den Tiefpunkt bei einer Reihe positiver Ganzzahlen zu finden. Das ist es, was ich mir ausgedacht habe, aber ich denke nicht, dass es das beste ist, und ich habe mich nur gefragt, ob jemand andere Vorschläge hat.

var low = 1; 
var high = 1; 
for (loop numbers) { 
    if (number > high) { 
     high = number; 
    } 
    if (low == 1) { 
     low = high; 
    } 
    if (number < low) { 
     low = number; 
    } 
} 

Answer 1

initialisieren Sie die hohen und niedrigen, um das erste Element zu sein. macht viel mehr Sinn, als eine willkürlich "hohe" oder "niedrige" Zahl auszuwählen.

var myArray = [...], 
    low = myArray[0], 
    high = myArray[0] 
; 
// start looping at index 1 
for (var i = 1, l = myArray.length; i < l; ++i) { 
    if (myArray[i] > high) { 
     high = myArray[i]; 
    } else if (myArray[i] < low) { 
     low = myArray[i]; 
    } 
} 

oder die Notwendigkeit, die Vermeidung der Array mehrere Male Nachschlag:

for (var i = 1, val; (val = myArray[i]) !== undefined; ++i) { 
    if (val > high) { 
     high = val; 
    } else if (val < low) { 
     low = val; 
    } 
} 

Answer 2

In Python:

>>> seq = [1, 2, 3, 4, 5, 6, 7] 
>>> max(seq) 
7 
>>> min(seq) 
1 

Answer 3

Sie haben es in O(n) Zeit zu tun, weil Sie eine Schleife durch alle brauchen (n) der Elemente, sie zu überprüfen, weil jeder eines der Elemente der sein kann, min oder max. (Es sei denn, sie sind bereits sortiert.)

Mit anderen Worten, Sie müssen alle Elemente durchlaufen und die Max- und Min-Überprüfung wie Sie haben.

Sortierung ist in der Regel bestenfalls O(n*log(n)). Somit ist es langsamer als ein einzelner Durchlauf (O(n)).

Answer 4

Angenommen, die Liste ist nicht bereits sortiert, das ist das Beste, was Sie tun können. Sie können sich selbst einen Vergleich speichern die folgenden (in Pseudo-Code), indem Sie:

low = +INFINITY 
high = -INFINITY 
for each n in numbers: 
    if n < low: 
     low = n 
    if n > high: 
     high = n 

Dies ist ein O (n) -Operation, die im Grunde ist das Beste, was Sie tun können.

Answer 5

Ihr Beispiel ist so ziemlich das effizienteste Algorithmus, aber offensichtlich wird es nicht funktionieren, wenn alle die Zahlen weniger sind

var low = numbers[0]; // first number in array 
var high = numbers[0]; // first number in array 
for (loop numbers) { 
    if (number > high) { 
     high = number; 
    } 
    if (number < low) { 
     low = number; 
    } 
} 

Answer 6

Wenn die Liste klein ist (wobei „klein“ ist weniger als ein paar tausend el: als 1 oder größer als 1 Dieser Code in diesen Fällen funktionieren Sie tun es nicht viel (wo "viel" weniger als ein paar tausend Mal ist) spielt keine Rolle. Profilieren Sie Ihren Code zuerst, um den echten Engpass zu finden, bevor Sie sich Gedanken über die Optimierung Ihrer Max/Min-Algorithmen machen.

Nun zur Beantwortung der Frage, die Sie gestellt haben.

Da es keine Möglichkeit gibt, jedes Element der Liste zu betrachten, ist eine lineare Suche der effizienteste Algorithmus. Es dauert N Zeit, wobei N die Anzahl der Elemente in der Liste ist. Alles in einer Schleife zu tun ist effizienter als das Aufrufen von max() und dann min() (was 2 * N Zeit benötigt). Ihr Code ist also grundsätzlich korrekt, auch wenn negative Zahlen nicht berücksichtigt werden. Hier ist es in Perl.

# Initialize max & min 
my $max = $list[0]; 
my $min = $list[0]; 
for my $num (@list) { 
    $max = $num if $num > $max; 
    $min = $num if $num < $min; 
} 

Sortieren und dann greifen das erste und letzte Element ist am wenigsten effizient. Es dauert N * log (N) wobei N die Anzahl der Elemente in der Liste ist.

Der effizienteste Min/Max-Algorithmus ist einer, bei dem min/max jedes Mal neu berechnet wird, wenn ein Element hinzugefügt oder aus der Liste entfernt wird.In der Tat das Ergebnis zwischenspeichern und eine lineare Suche jedes Mal vermeiden. Die dafür benötigte Zeit ist die Anzahl der Änderungen der Liste. Es dauert höchstens M Zeit, wobei M die Anzahl der Änderungen ist, egal wie oft Sie es nennen.

Um dies zu tun, könnten Sie einen Suchbaum betrachten, der seine Elemente in der richtigen Reihenfolge hält. Das Min/Max in dieser Struktur zu erhalten, ist O (1) oder O (log [n]) abhängig davon, welchen Baumstil Sie verwenden.

Answer 7

Die einzige weitere Optimierung, die ich vorschlagen würde, ist die Optimierung der Schleife selbst. Es ist schneller zu zählen als in JavaScript zu zählen.

Answer 8

Obwohl es immer noch ein O (n) -Algorithmus ist, können Sie es 25% schneller machen (das heißt, die Proportionalitätskonstante ist 3/2 vs 2), indem Sie zuerst paarweise paarweise miteinander vergleichen und dann kleiner mit min und größer bis max. Ich weiß nicht, Javascript, aber hier ist es in C++:

std::pair<int, int> minmax(int* a, int n) 
{ 
    int low = std::numeric_limits<int>::max(); 
    int high = std::numeric_limits<int>::min(); 

    for (int i = 0; i < n-1; i += 2) { 
    if (a[i] < a[i+i]) { 
     if (a[i] < low) { 
     low = a[i]; 
     } 
     if (a[i+1] > high) { 
     high = a[i+1]; 
     } 
    } 
    else { 
     if (a[i] > high) { 
     high = a[i]; 
     } 
     if (a[i+1] < low) { 
     low = a[i+1]; 
     } 
    } 
    } 

    // Handle last element if we've got an odd array size 
    if (a[n-1] < low) { 
    low = a[n-1]; 
    } 
    if (a[n-1] > high) { 
    high = a[n-1]; 
    } 

    return std::make_pair(low, high); 
} 

Answer 9

var numbers = [1,2,5,9,16,4,6]; 

var maxNumber = Math.max.apply(null, numbers); 
var minNumber = Math.min.apply(null, numbers); 

Answer 10

Nickf Algorithmus nicht der beste Weg, dies zu tun. Im schlimmsten Fall vergleicht der nickf-Algorithmus 2 Zahlen pro Zahl, für eine Gesamtzahl von 2n - 2.

Wir können ein bisschen besser machen. Wenn Sie zwei Elemente a und b vergleichen, wissen wir, wenn a> b ist, dass a nicht das Min ist und b nicht das Maximum ist. Auf diese Weise nutzen wir alle verfügbaren Informationen, um so viele Elemente wie möglich zu eliminieren. Nehmen Sie zur Vereinfachung an, dass wir eine gerade Anzahl von Elementen haben.

sie in Paare brechen: (a1, a2), (a3, a4) usw.

vergleichen sie, so dass sie in eine Reihe von Gewinnern und Verlierern zu brechen - das dauert n/2 vergleicht, uns zwei geben Sätze der Größe n/2. Finden Sie nun das Maximum der Gewinner und das Minimum der Verlierer.

Von oben, die Suche nach dem Minimum oder Maximum von n Elementen dauert n-1 Vergleiche. Somit ist die Laufzeit: n/2 (für die ersten Vergleiche) + n/2 - 1 (max der Gewinner) + n/2 - 1 (min der Verlierer) = n/2 + n/2 + n/2 -2 = 3N/2 - 2. Wenn n ungerade ist, haben wir ein weiteres Element in jedem der Sätze, so wird die Laufzeit 3N/2

in der Tat, können wir beweisen, dass dies der schnellste, dass Dieses Problem kann möglicherweise durch irgendeinen Algorithmus gelöst werden.

Ein Beispiel:

Angenommen unsere Array 1, 5, 2, 3, 1, 8, 4 Dividieren in Paare: (1,5), (2,3) (1,8), (4, -). Vergleichen. Die Gewinner sind: (5, 3, 8, 4). Die Verlierer sind (1, 2, 1, 4).

die Gewinner Scannen gibt 8. die Verlierer Scannen gibt 1.

Answer 11

diese Schnipsel Ausprobieren für Echt auf V8, Drew Hall-Algorithmus in 2/3 der Zeit von Nickf der läuft, wie vorhergesagt. Wenn Sie die Schleife statt nach oben herunterzählen, wird sie auf etwa 59% der Zeit reduziert (obwohl dies mehr von der Implementierung abhängig ist). Nur leicht getestet:

var A = [ /* 100,000 random integers */]; 

function minmax() { 
    var low = A[A.length-1]; 
    var high = A[A.length-1]; 
    var i, x, y; 
    for (i = A.length - 3; 0 <= i; i -= 2) { 
     y = A[i+1]; 
     x = A[i]; 
     if (x < y) { 
      if (x < low) { 
       low = x; 
      } 
      if (high < y) { 
       high = y; 
      } 
     } else { 
      if (y < low) { 
       low = y; 
      } 
      if (high < x) { 
       high = x; 
      } 
     } 
    } 
    if (i === -1) { 
     x = A[0]; 
     if (high < x) { 
      high = x; 
     } else if (x < low) { 
      low = x; 
     } 
    } 
    return [low, high]; 
} 

for (var i = 0; i < 1000; ++i) { minmax(); } 

Aber Mann, es ist ziemlich hässlich.

Answer 12

Javascript-Arrays haben eine native Sortierfunktion, die eine Funktion für den Vergleich akzeptiert. Sie können die Zahlen sortieren und einfach den Kopf und den Schwanz nehmen, um das Minimum und Maximum zu erhalten.

var sorted = arrayOfNumbers.sort(function(a, b) { return a - b; }), 
    ,min = sorted[0], max = sorted[sorted.length -1]; 

standardmäßig sortiert die Sortiermethode lexikographisch (lexikalische Reihenfolge) ist also, warum Sie in einer Funktion zu übergeben müssen sie numerische Sortierung zu erhalten zu verwenden. Die übergebene Funktion muss 1, -1 oder 0 zurückgeben, um die Sortierreihenfolge zu bestimmen.

Im Fall von Zahlen können Sie lediglich die zweite von der ersten Größe abziehen, um die Reihenfolge zu bestimmen.

var numbers = [5,8,123,1,7,77,3.14,-5]; 

// default lexicographical sort 
numbers.sort() // -5,1,123,3.14,5,7,77,8 

// numerical sort 
numbers.sort(function(a, b) { return a - b; }) // -5,1,123,3.14,5,7,77,8 

Answer 13

dieser Algorithmus für O arbeitet (n) und nicht mehr zusätzlichen Speicher benötigt Elemente speichern ...

enter code here 
int l=0,h=1,index,i=3; 
    if(a[l]>a[h]) 
       swap(&a[l],&a[h]); 
    for(i=2;i<9;i++) 
    { 
           if(a[i]<a[l]) 
           { 
             swap(&a[i],&a[l]); 
           } 
           if(a[i]>a[h]) 
           { 
              swap(&a[i],&a[h]); 
           } 
    } 
    printf("Low: %d High: %d",a[0],a[1]); 

Answer 14

es die ES6 Weise tun mit spread syntax:

var arrNums = [1, 2, 3, 4, 5]; 
Math.max(...arrNums) // 5 
Math.min(...arrNums) // 1