[C++] Funktion um Median zu berechnen?

[RedWing]

Die STL ist ja man eine feine Sache, aber zum sortieren überhaupt nicht geeignet. Viel zu viel Overhead.

Hi, ich würde gerne noch wissen:
1.) Was bedeutet "zuviel Overhead"
2.) Wieso sollte man sie nicht verwenden.
Die Algorithmen der STL wurden speziell auf Effizienz hin entwickelt,
da ham sich die Leute von sgi genug Gedanken drum gemacht, also wieso
sollte man sie dann nicht verwenden wenn man sie angeboten bekommt
, bzw kannst du da alternativen nennen + Argumente welche für die und nicht
für die STL sprechen wenn man das Rad nicht jedesmal wieder neu erfinden
möchte?

Gruß

RedWing

 

[TakaBo]

Hi
@RedWing
Zu 1) Wenn Du nur ein paar Sachen zu sortieren hast, ist die STL super. Feine Container, in die man ein paar Werte schiebt, die man dann sogar sortieren lassen kann. Problematisch wird das ganze nur, wenn man sehr viele Werte hat, die sortiert werden müssen. Jeder Zugriff auf eine Funktion bedeutet Zeit. Und derer gibt es viele in der STL. Allein durch die Benutzung eines Iterators entsteht ein kleiner Zeitverlust, der nicht unbedingt sein muß. Bei vielen zu sortierenden Werten addiert sich der Zeitverlust und kann schon bald unangenehm auffallen. Ein Beispiel aus eigener Erfahrung: Ich sollte für ein Bildverarbeitungsprogramm einen Median-Filter programmieren. Dazu brauchst Du, wie oben schon erwähnt eine Sortierfunktion. Ergebnis: Für 786432 Bildpunkte benötigte STL über 3 Minuten. Meines Wissens benutzt STL sogar den Quicksort-Algorithmus. Das war eindeutig zu lang. BTW: Die Komplexität des Quicksorts liegt meines Wissens nach bei O( n*log). Das gleiche Problem, allerdings "händisch" ohne STL mit einem Bubblesort realisiert (Komplexität O(n^2)! ) knapp 4 Sek. Okay, zugegeben ich hab dabei etwas getrickst, da ich aufgrund der Art der Eingabebilder davon ausgehen konnte, dass das Array häufig bereits sortiert vorliegt. Somit ergab sich dann, dass das Array nur 1xdurchlaufen werden musste.

Das Rad immer neu erfinden muss man auch nicht. Wenn man sich ein paar Includes schreibt mit Templates z.B. zum sortieren usw. erledigt sich das ganze schon fast von alleine ;-) C++ zeichnet sich schliesslich durch "Codereusability" aus.

Zu 2) Siehe 1) Wann man was benutzen sollte hängt meiner Meinung nach vom Fall ab. Zum testen reicht STL sicherlich.

Gruss TB

 

[RedWing]

Die Komplexität des Quicksorts liegt meines Wissens nach bei O( n*log)

Ja im Average case. Im worst case liegt er genau in der selben K-Klasse wie der
Bubble Sort, was auch die Zeit in deinem Fall erklären könnte. Wenn du einen
Optimalen Sortieralgorithmus verwenden willst, nimm den merge oder heap, die
sich im übrigen auch mit der STL realiesieren lassen.

Das gleiche Problem, allerdings "händisch" ohne STL mit einem Bubblesort realisiert (Komplexität O(n^2)! ) knapp 4 Sek. Okay, zugegeben...

Glaub ich dir nicht...Und wenn(wie in deinem Fall) dann ist es kein Bubblesort mehr.
Der Bubblesort besitzt sowohl im Average als auch im worst case O(n*n)...

Das Rad immer neu erfinden muss man auch nicht. Wenn man sich ein paar Includes schreibt mit Templates z.B. zum sortieren usw. erledigt sich das ganze schon fast von alleine C++ zeichnet sich schliesslich durch "Codereusability" aus.

Die Algorithmen der STL sind durch und durch getestet. Sprich die
Anfälligkeit auf einen Bug liegen bei nahezu 0%.
Wenn du Algorithmen jedesmal neu definierst musst du sie auch anständig
durchtesten, wobei wieder Zeit für die Entwicklung drauf geht =>
Die Projektkosten steigen.
Also wieso dann nicht gleich auf hochwertig Qualitative Bibliotheken
zurückgreifen?

In diesem Sinne

Gruß

RedWing

 

[RedWing]

Nachtrag:

Wann man was benutzen sollte hängt meiner Meinung nach vom Fall ab. Zum testen reicht STL sicherlich.

Da hast du schon recht, allerdings is es bei den heutigen Rechnerleistungen
wurscht ob ich nun eine C string Bibliothek hernehme oder eine STL string
Bibliothek. Aber im Punkto qualität und sauberes Programmieren macht sich da die
Verwendung der letzteren viel besser... Ausserdem ist C++ eine Objektorientierte
Sprache und die STL eine Objektorientierte Bibliothek die für C++ öffentlich
anerkannt und standardisiert wurde, also würd ich das so nicht sagen
das die STL zum Testen "reicht".

Gruß

RedWing

 

[Kachelator]

Ich denke, Redwing hat recht, wenn er die STL verteidigt. Unter normalen Umständen sind die Lösungen, die die Lib bietet, nahezu optimal. Wenn es dennoch zu Problemen kommt, kann man immer noch zu spezialisierten und optimierten Lösungen wechseln. Es gibt nichts Schlimmeres (ich übertreibe!) als vorzeitige Optimierung, also verwendet erst mal die STL und optimiert erst dann, wenn es wirklich sein muss!

So, das war mein Wort zum Sonntag.

 

[TakaBo]

Hab ich was anderes gesagt?
Sagen wir doch einfach für Standardaufgaben ist die STL gut geeignet. Heisst ja auch Standard Template Library

Nachtrag @RedWing:
Es ist ein Bubblesort mit der Komplexität O im optimalen Fall. Man kann schließlich im ersten Durchgang testen, ob ein swap nötig war. War keiner notwendig, ist das Array bereits sortiert und es kann beendet werden. Im anderen Fall sind weitere Iterationen nötig.
Es ist also ein Bubblesort mit vorzeitiger Abbruchbedingung. Wie gesagt: Es funktioniert auch nur, weil der Medianfilter auf Eingabebilder angewendet wird, die häufig die gleichen Grauwerte besitzen (grosse gleichfarbige Flächen).=> 9 gleiche Grauwerte = sortiertes Array.

Gruss TB.

 

[Kachelator]

Na ja, du hast Folgendes gesagt:

@Kachelator
Die STL ist ja man eine feine Sache, aber zum sortieren überhaupt nicht geeignet. Viel zu viel Overhead.

Dem kann ich wirklich nicht zustimmen. Sortieren ist schliesslich auch eine Standardaufgabe, die man mit der STL sehr gut lösen kann. Das man häufig auch spezialisierte Lösungen finden kann, die verbesserte Performanz erbringen, schliesse ich damit nicht aus.