Algorithmus zur Suche des größten Wertes

[BAGZZlash]

Ich habe ein einsbasiertes Array mit Werten. Diese Werte sind in dem Sinne geordnet, dass sie zunächst ansteigen, ab einem bestimmten Punkt aber wieder absteigen. Wo das Maximum liegt und wie viele Werte enthalten sind, kann unterschiedlich sein. Der erste Wert ist immer null.

Beispiel:

Index: 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16
Wert:  0 7 8 9 10 11 12 14 15 34 29 23 21 19 17 16

Ich möchte nun den Index des Maximums ermitteln, aber, ganz wichtig, dabei so wenige Indizes wie möglich "besuchen" müssen. Einfach am Anfang loslaufen und aufhören, wenn die Werte wieder kleiner werden, ist keine Option.

Meine Idee ist durch die Binärsuche inspiriert, aber mit Stack. Der Stack wird mit 1 vorinitialisiert. "CurrentMax" wird mit 0 vorinitialisiert.

In der ersten Iteration umfasst der "Suchast" das gesamte Array, d.h. die linke Grenze ist 1 und die rechte Grenze ist 16. Die Mitte davon ist 8:

Iteration  Left  Right  Middle    Stack
        1     1     16       8        1

Index: 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16
Wert:  0 7 8 9 10 11 12 14 15 34 29 23 21 19 17 16
                         ↑

Der Wert dort ist 14, also größer als CurrentMax, daher wird CurrentMax nun 14 zugewiesen. Was soll ich an dieser Stelle nun machen? Nach rechts gehen oder nach links? Keine Ahnung, aber ich entscheide mich mal für rechts. Middle wird auf den Stack gepusht und Left soll nun gleich Middle sein:

Iteration  Left  Right  Middle    Stack
        2     8     16      12     1; 8

Index: 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16
Wert:  0 7 8 9 10 11 12 14 15 34 29 23 21 19 17 16
                                     ↑

Dort steht 23 > CurrentMax, daher CurrentMax = 23, weiter nach rechts gehen. Also push Middle und Left = Middle:

Iteration  Left  Right  Middle    Stack
        3    12     16      14 1; 8; 12

Index: 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16
Wert:  0 7 8 9 10 11 12 14 15 34 29 23 21 19 17 16
                                           ↑

Dort steht 19 < CurrentMax, das gesuchte Maximum muss nun also sicher weiter links stehen. Es könnte an Position Nr. 13 stehen, daher nun pop Left und Right = Middle:

Iteration  Left  Right  Middle    Stack
        4    12     14      13     1; 8

Index: 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16
Wert:  0 7 8 9 10 11 12 14 15 34 29 23 21 19 17 16
                                        ↑

Hier steht 21, das Maximum ist also nicht getroffen. Das Maximum könnte die 23 bei Position 12 sein, aber es könnte auch noch links von Position 12 stehen. Aktuell sind wir bei 13. 12 und 14 wurden schon besucht, wir müssen also hier raus springen. Aber wohin? Es ist jetzt naheliegend, die 8 vom Stack zu poppen, das aktuelle Left zum neuen Right zu machen und damit fortzufahren:

Iteration  Left  Right  Middle    Stack
        5     8     12      10    1; 10

Index: 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16
Wert:  0 7 8 9 10 11 12 14 15 34 29 23 21 19 17 16
                               ↑

Dort steht 34 > CurrentMax. Nach rechts gehen? Okay, dann:

Iteration  Left  Right  Middle    Stack
        6    10     12      11        1

Index: 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16
Wert:  0 7 8 9 10 11 12 14 15 34 29 23 21 19 17 16
                                  ↑

Dort steht 29 < CurrentMax, also nicht weiter nach rechts gehen. Hm, der gesuchte Wert könnte auch noch an Position 9 stehen. Eigentlich müsste ich jetzt das neue Right durch das alte Left festlegen und für das neue Left die 8 poppen. Aber die ist ja schon nicht mehr auf dem Stack, sie wurde ja schon nach Interation 4 "verbraten".

Angenommen, ich hätte die 8 noch. dann wäre der nächste Schritt:

Iteration  Left  Right  Middle    Stack
        7     8     10       9        1

Index: 1 2 3 4  5  6  7  8  9 10 11 12 13 14 15 16
Wert:  0 7 8 9 10 11 12 14 15 34 29 23 21 19 17 16
                            ↑

Damit wäre klar, dass das Maximum an der Stelle 10 liegt. 9 haben wir besucht (< 34) und 11 haben wir auch besucht (< 34), wir wären also fertig und hätten nur 7 von 15 offenen Positionen besuchen müssen.

Aber, wie Ihr seht: Ich bin noch nicht sicher, wie ich das Ganze in einen Algorithmus gießen soll. Könnt Ihr mir helfen?

 

[new Account()]

Der Wert dort ist 14, also größer als CurrentMax, daher wird CurrentMax nun 14 zugewiesen. Was soll ich an dieser Stelle nun machen? Nach rechts gehen oder nach links? Keine Ahnung, aber ich entscheide mich mal für rechts.

Stell dir die werte als Funktion, d.h. Parabel vor.

Mit dieser Interpretation kannst du die Steigung an der spezifischen Stelle auswerten, indem du die benachbarten Werte auswertest:
13, [14], 15 -> Steigung ist positiv, weil der linke Wert kleiner und der rechte Wert größer ist. Folglich muss dein nächster Sprung nach rechts gehen.
15, [14], 13-> Steigung ist negativ, weil der linke Wert größer und der rechte Wert kleiner ist. Folglich muss dein nächster Sprung nach links gehen.

 

[adAstra]

In welcher Programmiersprache arbeitest du?

 

[new Account()]

Ist doch egal, da Algorithmen unabhängig von der konkreten Programmiersprache betrachtet werden können.

 

[adAstra]

Nein, ist es nicht. Je nach Sprache existiert möglicherweise bereits eine hervorragende Implementierung zur Lösung des Problems. Wozu das Rad neu erfinden? Beispiel C: Besser als qsort wird's nicht mehr ...

Wenn es nur um den Algorithmus geht, kannst du dich doch wunderbar an der Bisektion orientieren: Du startest mit dem ersten und letzten Wert, bestimmst den mittleren Index und prüfst ob der dazugehörige Wert größer als der linke oder rechte Wert ist. Die beiden größten Einträge (links und mitte, rechts und Mitte) übernimmst du dann als neue Grenzen und bestimmst wieder die Mitte. Mit jedem Schritt halbierst du so die Größe des Intervalls.

Weitere Inspiration liefern dir Standardwerke wie Numerical Recipes.

 

[BAGZZlash]

Stell dir die werte als Funktion, d.h. Parabel vor.

Mit dieser Interpretation kannst du die Steigung an der spezifischen Stelle auswerten

Faszinierende Idee. Damit werde ich mal rumspielen.

In welcher Programmiersprache arbeitest du?

In R.

Nein, ist es nicht. Je nach Sprache existiert möglicherweise bereits eine hervorragende Implementierung zur Lösung des Problems. Wozu das Rad neu erfinden? Beispiel C: Besser als qsort wird's nicht mehr ...

Ja, das ist natürlich richtig. Die Sache ist aber, dass ich den Suchalgorithmus nicht wirklich von den Daten trennen kann. Das Array mit den Daten wird erst während der Suche erzeugt. Wenn die Suche sagt: "Ich schau mal, was bei Index 12 steht", wird zunächst der Wert für Index 12 berechnet. Und das dauert jeweils ein paar Stunden, daher die Anforderung, möglichst wenige Indizes zu besuchen.

Wenn es nur um den Algorithmus geht, kannst du dich doch wunderbar an der Bisektion orientieren: Du startest mit dem ersten und letzten Wert, bestimmst den mittleren Index und prüfst ob der dazugehörige Wert größer als der linke oder rechte Wert ist. Die beiden größten Einträge (links und mitte, rechts und Mitte) übernimmst du dann als neue Grenzen und bestimmst wieder die Mitte.

So hatte ich mir das eigentlich auch gedacht. Also im ersten Schritt eben die 14 an Position 8. Und nun?

 

[adAstra]

Die 14 an Position 8 wird nun zur neuen linken Grenze, die rechte Grenze bleibt 16 an Position 16.

Nun wird wieder beim mittleren Index geschaut, also bei der 12. Dort wohnt der Wert 23. Wieder werden nur bei beiden höchst-wertigen Indizes behalten, Mitte bilden, höchstwertige Indizes behalten, und so weiter.

Davon abgesehen sollte eine Sprache wie R natürlich bereits fertige Funktionen dafür haben.

 

[new Account()]

Beispiel C: Besser als qsort wird's nicht mehr ...

Das stimmt gar nicht.
Je nach Anwendungsfall gibts auch schnellere Varianten.
z.B. gibts Sortieralgorithmen die in linearer Zeit sortieren können
Oder die Daten sind nicht 100% zufällig in einer Liste, dann kann ein Algorithmus, der im Schnitt der beste ist, auf einmal deutlich schlechter sein wie andere.

Auch auf die länge des Arrays kommt es an:
Hat man nur 10-100 Elemente, ist vielleicht das Ablaufen des arrays besser als, wenn man binäre Suche verwendet (Cache predictability)

Je nach Sprache existiert möglicherweise bereits eine hervorragende Implementierung zur Lösung des Problems. Wozu das Rad neu erfinden?

Der TE hat nach einem Algorithmus gefragt, nicht nach einer Implementierung

 

[BeBur]

Ich würde Newton-Artig einen linearen Zusammenhang unterstellen, in jedem Schritt aus vier verschiedenen Punkten zwei Geraden bauen und deren Schnittpunkt berechnen und das zurück auf die Array-Indices mappen.
Dann in der Gegend drum herum nach einem Max suchen und wenn keins gefunden wird mit den untersuchten Punkten wieder zwei Geraden bauen.

 

[adAstra]

Der TE hat nach einem Algorithmus gefragt, nicht nach einer Implementierung

Die Antwort "R" sollte eventuell auch dir im Nachhinein rechtfertigen, dass die Frage nach der Sprache sinnvoll gewesen ist ...

Das stimmt gar nicht.
Je nach Anwendungsfall gibts auch schnellere Varianten.

Wir sind hier nicht im Bereich High-Performance-Computing, sondern bei einer ziemlich banalen Suche eines größten Werts in einem Array. Qsort war lediglich ein Beispiel für eine ideale Implementierung eines Sortierverfahrens. Oder um es in deinen Worten zu sagen: Der Threadersteller hat nach einem Algorithmus zur Lokalisierung eines Maximums gefragt, nicht nach einer Aufschlüsselung der Vor- und Nachteile von Sortieralgorithmen ;-)

 

[new Account()]

Wieder werden nur bei beiden höchst-wertigen Indizes behalten, Mitte bilden, höchstwertige Indizes behalten, und so weiter.

Das funktoniert nicht:

Hier wird der grüne Bereich ausgewählt, Obwohl eigentlich der orange ausgewählt werden sollte

Ergänzung (12. Februar 2020)

Die Antwort "R" sollte eventuell auch dir im Nachhinein rechtfertigen, dass die Frage nach der Sprache sinnvoll gewesen ist ...

Nicht wirklich, warum?

 

[BeBur]

Also Gerade durch die Punkte (1,0) und (4,9) und die zweite Gerade durch (16,16) und (13, 23)
Komme ich auf
3x - 3 und
-(5/3)x + 128/3

Die schneiden sich grob bei x = 9.7, gerundet x = 10.
Schaust dir dann die Umgebung x=8,9 und x = 11,12 an
Hier in dem Fall hast du das Max direkt gefunden, sonst wieder zwei Geraden bauen.

Vermutlich kannst du auch Punkte einfach mehrmals verwenden und anstatt x +/- 2 als Umgebung nur x +/- 1
Dann hättest du 3 Auswertungen pro Schritt (außer im ersten Schritt).

 

[adAstra]

Das Problem mit der Null am Start ist in der Tat noch gesondert zu behandeln, guter Punkt. Ich habe mich an den Beispieldaten orientiert und die Struktur nicht allgemein genug betrachtet. Ansonsten klinke ich mich hier aus, dein Diskussionsstil vermiest mir hier gerade gehörig den Spaß.

 

[new Account()]

Hier in dem Fall hast du das Max direkt gefunden, sonst wieder zwei Geraden bauen.

Interessanter Ansatz von dir. Womit würdest du die zweite gerade aber genau bauen?

Ergänzung (12. Februar 2020)

Das Problem mit der Null am Start ist in der Tat noch gesondert zu behandeln. A

Wenn da 0,1 stehen würde, wäre es das selbe Problem.

 

[BeBur]

Interessanter Ansatz von dir. Womit würdest du die zweite gerade aber genau bauen?

Wäre das nicht das Maximum, dann eine Gerade für x = 0 und x = 9 bauen (beide Werte schon bekannt) und die zweite Gerade aus x = 16 und x = 11 (auch beide Werte bekannt)
Dann wieder Schnittpunkte berechnen + Umgebung checken = 3 Auswertungen.

PS.: Ich glaube das funktioniert nicht, man muss die Punkte immer vollständig aus der Umgebung beziehen und aus diesen dann die Geraden bauen.

 

[BAGZZlash]

Okay, mein Prototyp sieht jetzt so aus. Damit werden tatsächlich nur die Indizes 7, 8, 11, 12, 10 und 9 besucht. Sieht ganz gut aus. Vielen Dank an alle für den Schubs in die richtige Richtung bzw. das Wegnehmen des Bretts vor meinem Kopf! 😎

FindMax = function(a)
{
    Middle_a = as.integer(length(a) / 2)
    Upper = length(a)
    Lower = 1
   
    b = rep(NA, Upper)

    while (TRUE)
    {
        Middle_b = Middle_a - 1

        if (!is.na(b[Middle_a]))
        {
            b[is.na(b)] = 0
            return(which(b == max(b)))
        }

        b[Middle_a] = a[Middle_a] # Compute "a" value
        b[Middle_b] = a[Middle_b] # here

        if (b[Middle_a] > b[Middle_b])
        {
            Lower = Middle_a
            Middle_a = as.integer((Upper + Middle_a) / 2)
        } else
        {
            Upper = Middle_a
            Middle_a = as.integer((Lower + Middle_a) / 2)
        }
    }
}

 

[new Account()]

Ein bisschen musst du aufpassen, falls zwei Werte nebeneinander auch den selben Wert haben können.

 

[BAGZZlash]

Danke. Ja, da mach' ich noch ne Abfrage. Ist aber seeeeeehr unwahrscheinlich, dass das bei den echten Daten passiert.

 

[Michael-Menten]

Ist mehr bekannt als streng monoton steigend bis zum peak und ab dann streng monoton fallend? z.B. Waveform, grobe Position des maximums, etc.
So bleibt dir nichts anderes übrig als erstmal zuraten. Ansonsten könnte man Abschätzen wo das Maximum liegt und dann erst die aufwendigen Berechnungen durchführen.

 

[RalphS]

Ich stolpere ein bisschen über das “min Index”. Wenn ich mir das so anschaue, bleibt die Laufzeit doch linear... oder?

Parallel könnte man ggfs nachstampfen Richtung log(n). Wenn ich an Stelle 1 und 2 einen Anstieg >= 0 verzeichne und an Stelle k-1 und k einen <= 0, dann hab ich in diesem Fragment ein lokales Maximum. Also zerlege ich das Array in so viele Fragmente wie ich CPUs hab, mindestens jedoch 3 Elemente per Fragment, prüfe das und kriege hinterher exakt ein Teilfragment, welches mein Maximum hält. Das zerlege ich weiter, wenn es >=6 Elemente hat, ansonsten geh ich suchen mit einem erwarteten Aufwand von <=3 Tests.

Weitergehend muß man natürlich nicht alle Fragmente testen. Wenn element 1 im Fragment 1 größer ist als Element 1 im Fragment 2, dann kann F2 zwar ein lokales Maximum halten, aber kein globales. F2 kann ich also komplett wegwerfen, egal wie groß es ist.

Und schon wird’s logarithmisch.