Algorithmus zur Suche des größten Wertes

[mambokurt]

Faszinierende Idee. Damit werde ich mal rumspielen.


In R.


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.

Mal doof gefragt: was und wie berechnest du denn da? Da möglichst wenig zu berechnen ist ja ok aber hast du evtl die Möglichkeit den Wert erstmal grob zu überschlagen eh du richtig ausrechnest?

 

[BAGZZlash]

was und wie berechnest du denn da?

Das ist nichts Geheimes oder so, aber ich müsste sehr weit ausholen, um das zu beschreiben. Letztlich sind die einzelnen Werte die Ergebnisse einer Score-Funktion, die aus einem aufwendigen Optimierungsprozess zurückgegeben werden. Das kann pro Wert Stunden dauern, deswegen ist ja jede einzelne Iteration so "teuer".

den Wert erstmal grob zu überschlagen eh du richtig ausrechnest?

Nein, keine Chance.

 

[new Account()]

Das kann pro Wert Stunden dauern, deswegen ist ja jede einzelne Iteration so "teuer".

Dann würde sich vielleicht Bayesche Optimierung anbieten. Das ist eine Methode welche auf Basis eines Wahrscheinlichkeitsmodells Vorhersagen darüber trifft, was der wahrscheinlich beste Punkt für die nächste Auswertung ist.
Das Wahrscheinlichkeitsmodell wird auf Basis deines Vorwissens (Ableitung ist monoton fallend, ggf. noch weitere) und deinen bereits ausgewerteten Datenpunkten erstellt.

Für Arrays lohnt sichs nicht, weil der Prozess vergleichsmäßig aufwendig ist, aber bei einer Stunde bestimmt.

Das ist nichts Geheimes oder so, aber ich müsste sehr weit ausholen, um das zu beschreiben.

Interessieren würde es mich allerdings schon

Und schon wird’s logarithmisch.

Die Binärsuche ist schon logarithmisch (Basis 2)

 

[mambokurt]

Das ist nichts Geheimes oder so, aber ich müsste sehr weit ausholen, um das zu beschreiben. Letztlich sind die einzelnen Werte die Ergebnisse einer Score-Funktion, die aus einem aufwendigen Optimierungsprozess zurückgegeben werden. Das kann pro Wert Stunden dauern, deswegen ist ja jede einzelne Iteration so "teuer".

Ah ok. Multithreading machst du?

 

[Faluröd]

Letztlich sind die einzelnen Werte die Ergebnisse einer Score-Funktion, die aus einem aufwendigen Optimierungsprozess zurückgegeben werden. Das kann pro Wert Stunden dauern, deswegen ist ja jede einzelne Iteration so "teuer".

Habe ich das richtig verstanden, dass die Berechnung der Einzelwerte des Arrays, innerhalb dem du das Maximum suchst, etliche Stunden braucht? Denn wenn ja, würde ich gefühlsmäßig sagen, der große Hebel für die Rechenzeit liegt in der Berechnung der Einzelwerte und nicht im Suchalgorithmus für das Maximum.

 

[new Account()]

Denn wenn ja, würde ich gefühlsmäßig sagen, der große Hebel für die Rechenzeit liegt in der Berechnung der Einzelwerte und nicht im Suchalgorithmus für das Maximum.

Ihm gings doch gar nicht darum die Rechenzeit des Suchalgorithmus zu reduzieren, sondern die Anzahl der evaluierten Elemente durch den Suchalgorithmus.

 

[RalphS]

Die Binärsuche ist schon logarithmisch (Basis 2)

Sicher ist sie das. Das “Problem” ist, daß so wie ich den Ansatz überblicke kaum was gespart wird.
50% der Felder angucken zu müssen ist Erwartungswert. Jeder Optimierungsansatz muß das unterbieten, sonst kann man sich den Mehraufwand sparen.
Ich seh 6 aus 16 statt 8 aus 16 und seh auch für größere Längen etwa 50% Anschaubedarf, was wie gesagt schlicht zuviel ist.

log(2)16 wären vier Felder. Gut, da passen 6 Ermittlungen.
Interessanter wird es für 32 oder längere Arrays. 7 oder 12 Berechnungen (32) bzw. 8 vs 30 oder so?

Vielleicht überseh ich was, aber ich seh halt die erwähnte Minimierung der Indexabfragen nicht.

Abgesehen wovon natürlich auch eine evtl mögliche Parallelisierung der Indexberechnungen im Raum steht. Wenn die Stunden dauert und es keine weiteren Abhängigkeiten gibt, dann kann man da ggfs erwartungsgemäss erforderliche Positionen vorausberechnen, während der Rest noch läuft. Im einfachsten Fall hier also 16 Prozesse anstoßen- die dauern dann nich mehr 16x “paar Stunden”, sondern 1x.

 

[BAGZZlash]

Ah ok. Multithreading machst du?

Ja, indirekt. Innerhalb der großen, stundenlang dauernden Berechnungen wird eine Funktion eingesetzt, die prinzipiell selbst parallelisieren kann, wenn man sie anweist, das zu tun. Macht sie auch, aber offenbar können dort nur Teile des Algorithmus parallelisiert werden. Ich denke daher, dass es besser ist, weiter "außen" zu parallelisieren. Ich mache das nun selbst und parallelisiere eben ein paar der großen Berechnungen insgesamt. Im Ergebnis werde ich wohl einen hybriden Ansatz fahren: Ich bleibe bei der Idee mit der Steigung, aber "popularisiere" den Ergebnisvektor in der "Umgebung" des aktuellen "Punktes der Parabel" mit parallel berechneten Ergebnissen.

Interessieren würde es mich allerdings schon

Da der Computer jetzt erstmal rechnet, habe ich Zeit, Deine Neugier zu befriedigen: Ich habe einen Geodatensatz (Rasterdaten) für Deutschland mit den Windgeschwindigkeiten und Windrichtungen an jedem Punkt. Stellt Dir nun vor, Du hast ein Grundstück irgendwo, und es wäre zulässig, dort Windräder (Windkraftanlagen, WKA) zu bauen. Angenommen, es ist ein guter Standort, was die Windverhältnisse angeht, sodass es sich prinzipiell lohnen würde.

Wenn Du genug Kapital von der Bank bekommst (oder selbst hast), kannst Du dort einen Windpark mit mehreren WKA bauen. Die Frage, die sich nun stellt, ist die nach der optimalen Anordnung der WKA innerhalb des Windparks. Dazu gehört, dass die einzelnen WKA gewisse Abstände zueinander einhalten müssen und, je nach Windrichtung, sich mitunter gegenseitig im Wind stehen. Wenn beispielsweise der Wind meist von Osten kommt, wäre es dumm, zwei WKA exakt in Ostwestrichtung zueinander aufzustellen ("nebeneinander"). Besser wäre ein Arrangement in Nordsüdrichtung ("übereinander").

Die erwähnten stundenlangen Berechnungen ermitteln das optimale Arrangement innerhalb des Windparks für eine gegebene Anzahl von WKA. Die Frage nach dem optimalen Arrangement ist aber erst die zweite Frage, die erste Frage ist die nach der optimalen Anzahl der WKA. Dies ermittelt nun die hier diskutierte Suche. Zunächst wird eine Obergrenze festgelegt (Beispiel: Das Areal ist 5 km x 5 km groß. Der gesetzliche Mindestabstand beträgt, sagen wir mal, 500 m. Dann können in eine Richtung maximal 10 WKA aufgestellt werden und in der Fläche maximal 10 x 10 = 100.). Diese wird aber kaum das Optimum in bezug auf die Anzahl der WKA darstellen, weniger WKA erzeugen einen größeren Gewinn, da sie sich weniger gegenseitig im Wind stehen werden und außerdem ja jede Anlage auch Geld kostet.

Daher erzeuge ich ein Array mit den Gewinnen der optimalen Aufstellung für jede zulässige Anzahl an WKA (hier: Zwischen 1 und 100) und rechne dann für diese WKA-Anzahlen jeweils den Gewinn aus einem optimalen Arrangement aus. Der größte Gewinn gibt die optimale Anzahl an WKA an, das dort optimale Arrangement habe ich dann sowieso schon.

 

[mambokurt]

Ja, indirekt. Innerhalb der großen, stundenlang dauernden Berechnungen wird eine Funktion eingesetzt, die prinzipiell selbst parallelisieren kann, wenn man sie anweist, das zu tun. Macht sie auch, aber offenbar können dort nur Teile des Algorithmus parallelisiert werden. Ich denke daher, dass es besser ist, weiter "außen" zu parallelisieren. Ich mache das nun selbst und parallelisiere eben ein paar der großen Berechnungen insgesamt. Im Ergebnis werde ich wohl einen hybriden Ansatz fahren: Ich bleibe bei der Idee mit der Steigung, aber "popularisiere" den Ergebnisvektor in der "Umgebung" des aktuellen "Punktes der Parabel" mit parallel berechneten Ergebnissen.

Ich hätte folgendes vorgeschlagen: du parallelisierst nicht die Scoringfunktion sondern die Suche. Wenn du 10 Threads hast dann kannst du an 5 Stellen parallel die Steigung berechnen, dann suchst du die erste fallende Steigung die du gefunden hast und hast und machst das selbe wieder links davon. In deinem Beispiel mit den 30 Indices bist du da zwangsläufig nach 2(!) Durchläufen fertig, also in der selben Zeit in der du sonst seriell nur einen einzelnen Anstieg ausgerechnet hättest (bzw zwei Indices).

 

[BAGZZlash]

Ja, so ähnlich meinte ich das auch mit meinem hybriden Ansatz. Momentan bin ich noch etwas am Tüfteln, wie ich die Threads stets gut auslaste. Das sind jetzt aber Details.

 

[mambokurt]

Ja, so ähnlich meinte ich das auch mit meinem hybriden Ansatz. Momentan bin ich noch etwas am Tüfteln, wie ich die Threads stets gut auslaste. Das sind jetzt aber Details.

shrug ich hätte jetzt einfach die 5 Steigungen berechnet und wenn alle fertig sind die nächsten 5, man muss es ja nicht komplizierter machen als es ist

 

[BAGZZlash]

Ja, auf sowas läuft es hinaus. Oder eben (maximal) so viele Threads, wie auf der Maschine Cores da sind.

 

[T_55]

Wenn es immer eine simple Parabel ist dann wäre das Stichwort "Parabolic Interpolation search".
Es gibt wohl auch Sachen wie Brent's method, Golden Section Search, Newton’s method, etc
http://www.it.uom.gr/teaching/linearalgebra/NumericalRecipiesInC/c10-2.pdf
http://csg.sph.umich.edu/abecasis/class/2006/615.16.pdf
http://fourier.eng.hmc.edu/e176/lectures/NM/node25.html
https://link.springer.com/chapter/10.1007/978-3-662-36470-3_5

Mit OpenMP könnte man sowas iterativ parallelisieren auf Ebene von Schleifen wenn die Funktionen so viel kosten.

ps: R hat auch optimize() aber wohl nur per Stepsize ist wohl zu unschlau
https://www.rdocumentation.org/packages/stats/versions/3.6.2/topics/optimize

 

[LencoX2]

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.

Falsch. Ein Algorithmus ist die theoretische Idee. Diese kann in Sprache x als Programm eine technische Umsetzung finden.
Zur Laufzeit:
Unter der Annahme dass das Array Duplikate enthalten kann ist nur lineare Suche mit O(n) Laufzeit drin.
Unter der Annahme dass keine Duplikate enthalten sind aber keine Zahl vorkommt, die kleiner als der Vorgänger ist, ist auch nur O(n) drin.
Das ist hier aber nicht dein Problem.
So wie ich es verstehe kann der Anruf der naechtsen Scoreberechnung abgebrochen werden, wenn der vorletzte berechnete Wert höher ist als der letzte

 

[new Account()]

Unter der Annahme dass keine Duplikate enthalten sind aber keine Zahl vorkommt, die kleiner als der Vorgänger ist, ist auch nur O(n) drin.

Wir sind doch jetzt schon bei O(log(n/#Cores))

 

[adAstra]

Falsch. Ein Algorithmus ist die theoretische Idee. Diese kann in Sprache x als Programm eine technische Umsetzung finden.

Sag mal, hast du überhaupt gelesen was ich geschrieben habe oder wurdest du beim Skimmen einfach nur getriggert? An welcher Stelle bitteschön definiere ich einen Algorithmus? Ich stelle lediglich klar, dass moderne Hochsprachen in der Regel bereits fertige Lösungen für das Problem besitzen.

 

[LencoX2]

Wir sind doch jetzt schon bei O(log(n/#Cores))

??

Multithreading verringert nicht die Laufzeit des ALG.
Binäre Suche mit O(log(n)) geht nur bei aufsteigend sortierten Arrays.
Viele Spass noch