# [C++] Funktion um Median zu berechnen?



## Romsl (10. Dezember 2004)

Hi,

gibt es in der C++ Library evtl. schon eine Funktion um den Median (aus 3 Zahlen) heraus zu bekommen? Oder muss ich hier alle Fälle mit einer IF Schleife abfangen?

Gruß

Romsl


----------



## Kachelator (10. Dezember 2004)

Meinst du den Mittelwert? Dazu gibt es in der STL den Algorithmus accumulate im <numeric>-Header. Du müsstet das Resultat dann nur noch durch die Anzahl der aufsummierten Elemente teilen.

Eine andere Möglichkeit wäre es, die Elemente von Hand in einer for-Schleife aufzusummieren und dann zu teilen. Dass meintest du vermutlich mit der IF-Schleife, oder verstehe ich dich falsch?


----------



## Romsl (10. Dezember 2004)

Nein ich meine den Median, so wie ich es geschrieben habe.

Median wird wie folgt berechnet.

Voraussetzung: sortierte Zahlenwerte

1.a) Anzahl aller Elemente ist gerade: Median ist die Zahl an der Stelle ((n / 2) + ((n + 1) / 2) / 2
1.b) Anzahl aller Elemente ist ungerade: Median ist die Zahl an der Stelle (n / 2)

Bei 3 Zahlen wäre der Median die mittlere Zahl.

Bsp:

3, 7, 13 -> Median ist 7.

Trotzdem Danke


----------



## Kachelator (10. Dezember 2004)

Okay, da habe ich dich falsch verstanden. Du kannst aber dennoch die STL-Algorithmen verwenden, um beispielsweise eine Sequenz zu sortieren und dann das "mittlere" Element zu finden.

Würde dir das weiterhelfen? Na ja, so knifflig ist das auch ohne STlL ja nicht.


----------



## Romsl (10. Dezember 2004)

Stimmt schon, dass das nicht knifflig ist.

Es geht aber darum ein Programm zu schreiben das auf verschiedene Arten den QuickSort durchführt. Unter anderem soll er als Pivot den Median nehmen. Mir geht es eben nur darum diese ganzen Vergleiche auf ein minimum zu reduzieren um die WC-Komplexität gering zu halten.


----------



## Thomas Darimont (10. Dezember 2004)

Hallo!

Um den Median einer Zahlenfolge zu bestimmen darf man nicht sortieren...
wir wollen ja gerade den Wert dieser Zahlenfolge der in Ungeordneten Reihenfolge (so wie die Werte eben reingekommen sind) in der "Mitte" im Sinne der Reihenfolge (nicht der Geordneten Reihenfolge) befindet. Den Median erhält man nach dem folgenden Ermittlungsschema:

Bsp. 
Ungerade Anzahl:
Folge A = 4 2 8 7 0 1 3

Hier ist der Median: -> A((n+1) / 2) -> 7 

Gerade Folge:
Folge A = 4 9 8 1 2 2 3 9
Hier ist der Median: -> (A(n/2) + A(n/2+1))/2 -> 1,5

Gruß Tom


----------



## TakaBo (10. Dezember 2004)

Hi

@Tom

Das ist AFAIK nicht korrekt. Der Median bezieht sich auf den mittleren Wert einer sortierten Folge. Er wird nicht nur in der Statistik, sondern auch gern in der Bildvorverarbeitung (BVV) benutzt, da sich mit ihm ein nichtlinearer Filter konstruiren lässt.
Zum Median siehe:

http://de.wikipedia.org/wiki/Median

@Romsel
Den Pivot über den Median zu nehmen ist doppelt gemoppelt, da das Array dazu bereits sortiert ist. Du kannst aber den Pivot bestimmen, in dem du das Array mit den Werten einmal abfährst und den kleinsten Wert raus suchst.
Empfehlen kann ich hierzu "Algorithmen und Datenstrukturen" von Herbert Kopp.
Siehe:
http://gd.tuwien.ac.at/books/skript...grotithmen_und_Datenstrukturen_001_g_198p.pdf

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

Gruss TB


----------



## Kachelator (10. Dezember 2004)

TakaBo hat gesagt.:
			
		

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


Hört, hört...


----------



## Thomas Darimont (10. Dezember 2004)

Hallo!

@Takabo
du hast recht... schande über mein Haupt... aber ansonsten stimmen "meine" Rechenvorschriften ;-)

Gruß Tom


----------



## TakaBo (11. Dezember 2004)

Hi,

@Tom: Jau, sonst stimmts *Kopfnick*   

Gruss TB


----------



## RedWing (11. Dezember 2004)

> 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 (11. Dezember 2004)

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 (11. Dezember 2004)

> 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 (11. Dezember 2004)

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 (12. Dezember 2004)

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 (12. Dezember 2004)

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 (13. Dezember 2004)

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.


----------

