Effektive Ermittlung Min,Max eines Arrays

Hallo zusammen,

ich möchte in einem sehr großen Double-Array das Minimum und Maximum ermitteln. Natürlich könnte ich mit ner for-schleife drüber laufen und mir das ergebnis temporär speichern. Hatte aber mal irgendwo nen Algorithmus gesehen der das etwas effektiver löst, weiß aber leider nicht mehr wo und wie der ging 😄

Danke für eure Hilfe ...

Hallo LuckyStrike,

meintest du diesen Algorithmus?

m0rius

An diesem Algorithmus ist nix effektiver. Das sieht nur so aus. Der "Gewinn" entsteht durch die Scalar-Funktion von Perl.

*edit* Siehe unten. Der Gewinn ist die Vergleichsreduktion, Skalar macht das aber wieder zunichte, weil hier n/2 Kopieroperationen dazukommen.

Hi,

ich hab mir den Algorithmuszwar nicht näher angeguckt, aber dort steht was von "3n/2" Vergleiche. Das ist schon eine Verbesserung gegenüber dem naiven "2n".
Insofern nutzt der dortige Algorithmus wahrscheinlich auch folgende Grundidee:

Nimm zwei benachbarte Elemente. Vergleiche zunächst diese. Und nun vergleiche das kleinere mit dem Minimum und das größere mit dem Maximum.

(Das sind eben für 2 Elemente 3 Vergleiche und nicht 4 wie im naiven Fall)

Allerdings bringt diese Implementierung in C# sicher nicht sonderlich viel.
Entweder man verwendet Zugriffe wie "arr_ > arr[i+1]", dann werden die Range-Checks aber nicht gut wegoptimiert. Oder aber man vermeidet die Array-Zugriffe möglichst häufig und speichert die aktuellen Werte zwischen (a=arr_, b=arr[i+1]), aber C# packt diese Variablen dann meistens wirklich auf den Stack (ohne die Werte ausschließlich im Register zu halten), was auch wieder langsam ist

Bringt also keine Performance. Außer du implementierst das in C/C++ oder C++/CLI.

Eine simple Möglichkeit wäre natürlich das halbieren und das Min-Max-Suchen in 2 Threads.

Aber wie groß ist es denn? Bei mir müsste das Array schon 0.7GB groß sein, damit die Suche länger als eine Sekunde dauert.

beste Grüße
zommi

Hier sind noch zwei Varianten die ohne Scalar arbeiten und wirklich 3/2n machen. Die Idee dahinter ist klar: Wenn etwas als Minimum in Frage kommt, kann es nicht zugleich Maximum sein (außer bei Feld-Länge von 1).

http://stackoverflow.com/questions/217316/best-algorithm-for-determining-the-high-and-low-in-an-array-of-numbers

Hallo,

ich hab jetzt rein von der mathematik nicht soviel Ahnung daher weiß ich auch nicht ob die Idee völliger Murks ist. Der Quicksort ist an und für sich ein Optimierter Algorythmus um groß und kleiner zu Sortieren. (Hoffe das ist richtig ausgedrückt). Natürlich macht eine komplette Sortierung ja keinen Sinn. Aber für den gedanken an und für sich kann man den ersten Durchlauf von dem Quicksort wo normalerweise vorsortiert wird, als Beispiel nehmen wie man gethreaded das ganze optimieren kann. Weil der fängt ja auch an 2 verschiedenen Seiten an. ich würde das als Anlaufpunkt nehmen für ein optimiertes Verfahren nach der Suche nach Min/Max. Aber das ist nur eine Idee kann auch voll murks sein.

Gruß Kaji

Quicksort macht O(n* log2 n), dazu käme dann noch binäre Suche mit O(log2 n). Macht also keinen Sinn. Sortieren um schneller zu suchen macht nur dann Sinn, wenn man viele Suchoperationen nach einem mehr oder weniger einmaligen Aufbauen der Daten machen muss.

Hallo svenson,

ich hab doch gar nicht von Sortieren gesprochen. Kam vielleicht falsch rüber. Es ging um die Technik des durchlaufes. Sodass das ganze auf 2Threads gut aufgeteilt werden kann. Die Variablen sollen an und für sich nicht verschoben sondern auch nur "angeschaut und verglichen" werden.

Gruß Kaji

Ach so. Nun ja, Aufwand hat ja erstmal nix mit der Zahl der Threads zu tun. Aber der 3/2n-Algorithmus läßt sich schon perfekt parallelisieren. Einfach Teile des Feldes von den Threads berechnen lassen, danach die Ergebnisse zusammenführen und nochmal Min/Max bestimmen.

Schneller als O(n) geht's nicht.