Sinnvolle Modalwertberechnung

[Nicodius]

Hallo Leute
Mich hat mal wieder seit langem die Programmierlust gepackt und ich habe mich um eine Umsetzung einer grafischen Darstellung von Sortierverfahren bemüht-
Ich würde gerne den Modalwert eines mit Integern gefüllten Arrays ermitteln - wie tue ich das möglichst sinnvoll auch bei einer großen Anzahl von Zahlen. Mir fällt da keine gute Idee ein.


Lg Nico

[alzaimar]

Du kannst es mit einer Hashmap lösen. Mit der Klasse 'TIntegerDictionary' aus dieser Unit geht das so:

Delphi-Quellcode:

Procedure ErmittleModalwert (Const anArray : TIntegerArray; Var Modus, Haeufigkeit : Integer);
Var
  Map : TIntegerDictionary;
  i : Integer;
  pCnt : ^Integer;
  iKey : Integer;

Begin
  Map := TIntegerDictionary.Create;
// Wir verwenden eine HaspMap, die Key/Value-Paare (hier: Value=Pointer) speichert. Da wir die 'Key' zählen wollen,
// definieren wir einen Zähler (Pointer to Integer), den wir als Nutzdatum (Value) zu jedem Schlüssel in der Map
// ablegen.
  Try
//
// 1.Schritt: Alle Elemente zählen
//
    For i:= Low (anArray) To High (anArray) Do Begin
      iKey := anArray[i];                           // Das Element des Arrays ist unser Schlüssel
      If Map.Find (iKey, Pointer (pCnt)) Then       // Wenn dieser Wert schon aufgetreten ist ...
        inc (pCnt^)                                 // den Zähler erhöhen...
      Else Begin
        new(pCnt);                                  // ...ansonsten einen neuen Zähler erstellen
        pCnt^:= 1;                                  // mit 1 initialisieren 
        Map.Add(iKey, Pointer (pCnt));              // und in der Integer-Map ablegen
      End
    End;
//
// 2.Schritt: Den Wertt mit dem höchsten Zähler ermitteln
//  
    Haeufigkeit := 0;
    Modus := -1;
  
    Map.First;          
    While Map.Next (iKey, Pointer (pCnt)) Do Begin  // Hohle nächsten Eintrag aus der Map
      If pCnt^>Haeufigkeit Then Begin               // Höchster Zähler? Wenn ja ...
        Haeufigkeit := pCnt^;                       // Wert merken
        Modus := iKey;
      End;
      Dispose (pCnt);                               // aber in jedem Fall den Speicher aufräumen
    End;
  Finally
    Map.Free;
  End;
End;

Der Aufwand ist O(N). Besser geht es nicht (Aufwandstechnisch)
Das triviale Verfahren, das Array zunächst zu sortieren und dann die längste Sequenz zu ermitteln ist mit O(N log N) vom Aufwand schlechter.

[taaktaak]

Moin, Moin.
Hmmm - hatte zunächst (natürlich) das triviale Verfahren im Sinn. Frage an alzaimar (da ich den geposteten Code auf die Schnelle nicht so wirklich verstehe): Wird hier auch berücksichtigt, dass es mehrere Modalwerte geben kann?

[alzaimar]

Hi, natürlich. Ich kommentiere den Code mal... warte....*werkel*.... fertig.

[taaktaak]

Noch mal hmmmmmmm.
Ich kann das noch nicht erkennen: Nehmen wir das Beispiel-Array

1 1 1 2 3 4 5 5 5 6 7 8

In diesem Fall gibt es zwei Modalwerte: 1 und 5 beide haben die Häufigkeit 3
- die Prozedur gibt aber doch als Ergebnis nur einen Wert zurück, oder?

//edit:

So mal in Ruhe angeschaut: Effiziente Lösung, die in der vorgestellten Form aber keine multimodalen Ergebnisse zulässt. Hierzu muss der Schritt 2 angepasst werden - das sollte aber das Thema von Nicodius sein. Ist doch 'ne gute Gelegenheit sich wieder mit Delphi anzufreunden!

[Nicodius]

Vielen Dank für die schnelle Antwort!
Allerdings stellt sich für mich die Frage ob man so auch mehrere Werte herausbekommen kann,
daran scheitere ich nämlich

lg nico

[taaktaak]

siehe oben: Schritt 2 anpassen!

[Nicodius]

vielen herzlichen dank
ja ein freund von mir hat mich ein java applet für sein handy gezeigt welches er programmiert hat welches bubblesort grafisch darstellt. da hab ich mich dann gleich selber dran gemacht und das ganze optimiert und verbessert.

nochmals danke

[Horst_]

Hallo,

ich habe gerade mal nachgeschaut was überhaupt Modalwert ist:
http://brinkmann-du.de/mathe/gost/bstat_01_06.htm

Gibt es mehrere Werte mit maximaler Häufigkeit, gibt es keinen Modalwert.
"Multimodal" gibt es also nicht

Gruß Horst

[marabu]

Hallo,

auf der Suche nach einer Definition würde ich ein Standardwerk der Statistik bevorzugen. Die Begriffe unimodal und multimodal sind durchaus korrekt. Bei den Grundlagen der deskriptiven Statistik mag auf die Angabe des Modus verzichtet werden, das gilt aber nicht allgemein.

Grüße vom marabu