Datenstruktur für statistische Werte

[asdfman]

Abend,

ich wollte mir etwas basteln, in das ich Messwerte hineinschieben kann, um am Ende statistische Sachen herauszuziehen. Ich wählte diese Ausdrucksweise, um zu unterstreichen, dass ich professionell mit Informatik wenig zu tun habe.

Ich will die Sache möglichst direkt vernünftig angehen, deshalb stellt sich mir erstmal die Frage, wie man die Messwerte sinnvoll unterbringt. Es sollte möglichst abstrakt gehalten sein. Zum Beispiel können Messwerte ja komplett voneinander unabhängig sein (Würfeln zb?), oder in einem Zusammenhang zueinander stehen (Temperatur zu einem bestimmten Zeitpunkt?). Lässt sich das sinnvoll vereinheitlichen?
Was für eine Datenstruktur bietet sich an, wenn man möglichst schnell z.B. Median, arithmetisches Mittel, Varianz und so herauspopeln will? Wenn ich später Tests machen möchte oder Regression? Wahrscheinlich sind für verschiedene Anwendungsfälle unterschiedliche Datenstrukturen sinnvoll. Welche? Kann man sie leicht ineinander umbauen oder gibt es eine oder wenige, die größtenteils ihre Arbeit vernünftig machen?

Ich erwarte als Antwort weniger Prosa oder Antworten aus dem Ärmel. Frei zugängliche Artikel, die ich verstehen kann, wenn ich vor >10 Jahren Mathe-LK und ein Semester statistische Methoden hatte, wären schön.

Spoiler

Statistische Methoden war eine Klausur, zu der man sich beliebige Literatur mitnehmen konnte und von der ich im Zweifelsfall alles wieder vergessen habe. :/

 

[Miuwa]

Gehts um ein konkretes Programm oder willst du wissen wie du das in einer bestimmten Programmiersprache umsetzt? Oder reden wir von Datenstrukturen in einer Datenbank? Reicht Excel nicht? Hast du Zugriff auf Matlab/Mathematica?

 

[asdfman]

Gehts um ein konkretes Programm

Nein.

oder willst du wissen wie du das in einer bestimmten Programmiersprache umsetzt?

Nein.

Oder reden wir von Datenstrukturen in einer Datenbank?

Nein.

Reicht Excel nicht?

Nein.

Hast du Zugriff auf Matlab/Mathematica?

Nein.

Habe ich mich so unklar ausgedrückt? Eine Datenstruktur ist soetwas wie ein Baum oder eine Tabelle. Mal ein Beispiel mit Anwendung auf meinen Fall:

Ich nehme eine Liste, in die ein Messwert so eingefügt wird, dass die Liste sortiert bleibt. Wenn ich im Moment die Liste (1 2 200 321) habe und als neuen Wert 6.1 bekomme, wird daraus also (1 2 6.1 200 231).
Dann kann ich einen Zeiger verwenden, der am Anfang auf das erste Element zeigt und nach jeder zweiten Einfügung eine Position weiter geschoben wird. So landet er garantiert auf dem Median (oder der Median lässt sich trivial ausrechnen).
Um das arithmetische Mittel zu bekommen müsste ich aber jedes Mal die komplette Liste durchgehen. Also nicht so schön. Mit der Varianz genauso. Eine Liste zu verwenden ist also auf den ersten Blick nicht so optimal.

€inschub-€dit: Merke gerade, dass ich mit meiner tollen Idee in Wirklichkeit gar nicht auf dem Median lande. Also wohl eine doppelt unoptimale Wahl.

Hoffe, das war irgendwie nachvollziehbar.

 

[convexus]

In der Boost-Bibliothek gibt es was ähnliches

http://www.boost.org/doc/libs/1_57_0/doc/html/accumulators.html

Sollte wenigstens als Ideengeber herhalten können.

 

[Miuwa]

Naja, viellleicht bin ich ja schwer von Begriff, aber deine Frage ist schon sehr allgemein gehalten. Wenn ich eine statistische Auswertung von Datenreihen machen muss, dann programmiere ich mir das normalerweise nicht selbst zusammen, sondern nutze Programme, die die entsprechenden Funktionen mitbringen (daher die Frage nach Matlab und Excel). Und je nach Programm / Programmiersprache, Platform (Mikrocontroler vs PC) und Szenario eignen sich verschiedene Datenstrukturen unterschiedlich gut, genauso wie man das Thema generische Datenstrukturen in unterschiedlichen Sprachen unterschiedlich angehen kann.

Aber wenn du einen allgemeinen Ratschlag willst:
Für fast alle Anwendungen ist es das schnellste, alle Messwerte einer Datenreihe in ein simples Array bzw. im Falle von c++ in einen Vektor zu speichern und ganz naiv die Mathematische Formel für die Jeweilige Kenngröße auszurechnen.
Viele Größen wie den Durchschnitt kann man natürlich auch akkumulativ on-the-fly berechnen, ohne die Daten zwischenzuspeichern, aber sofern wir hier nicht von zig Millionen Einträgen oder sehr komplexen Größen sprechen wirst du wohl keinen großen Unterschied spüren.

 

[daemon777]

Leider muss ich zugeben, dass mir der Zweck auch noch nicht so ganz einleuchtet. Bei Verteilungen betrachte ich ja in der Regel unabhängige Ereignisse. Dann ist aber die Frage, um welche Verteilung es sich handelt (Normalverteilung, Gemoetrische Verteilung usw). Das ist dann aber weniger eine Frage der Datenstruktur, sondern der Berechnung von Erwartungswert und co. Hier hätte man also wohl am Liebsten ein Interface für Verteilungen allgemein und dann eine Klasse für jede Art.

Was die Datenstruktur angeht fällt die Antwort wohl gleich unspektakulär aus. In der Regel würde man hier wohl die Daten einfach in ein Array speichern. Statt jetzt aber einfach jeden Messwert neu hinzuzufügen könnte man eine Art zählenden Filter implementieren. Ist die neue Zahl also Beispielsweise x, dann wird data[x]++ gerechnet. Das kann Sortierarbeit sparen und darüberhinaus auch SPeicherplatz, wenn die Anzahl der Messungen größer ist, als die Größe der möglichen Werte.

Bei nicht-unabhängigen Zufallsvariablen wird das Ganze schon etwas schwieriger, denn da muss man dann doch langsam wissen, was man vor hat. Soll das ein Chi-Square-Test werden?

Für eine Regression wird glaube ich ganz mal simuliert, wie zB mit dem simulated annealing. Auch hier gäbe es also weniger die Möglichkeit die Datenstruktur alles machen zu lassen, als Interfaces zu implementieren, die die Benutzung nach Außen hin vereinfachen.

 

[black90]

Wenn die Anzahl der Messdaten bekannt ist, dann definitiv Arrays.
Wenn du speed willst, dann pufferst du Zwischenergebnisse, z.B. jedes mal beim Einfügen aufaddieren.

Brauchst du oft nur bestimmte Bereich, dann bietet sich sowas wie ein Suchbaum an, wo links alles kleiner 20 und rechts alles größer 20 steht. Sowas hat logarithmische Laufzeiten, d.h. der Baum halbiert sich nach jedem passierten Knoten.

Leztendlich musst du selbst wissen was du machen willst und dir eine passende Struktur notfalls selbst ausdenken. Man kann Baumknoten z.B. auch auf Arrays zeigen lassen. Mit sowas könntest du dann Bereiche einteilen, 1-10, 11-20 usw. Oder Matrizen artige Strukturen...

 

[asdfman]

Mahlzeit.

Na, die Antwort war ja weitgehend einstimmig und zum Glück simpel und am Ende irgendwie offensichtlich. Vielen lieben Dank.

 

[Miuwa]

Nur um mal ein Beispiel zu geben:
Um 100 Millionen double-Zufallszahlen in ein simples array zu schreiben und anschließend Durchschnitt und Varianz zu berechnen braucht mein Ivy Bridge auf einem Kern gerade mal 2 Sekunden. Das anschließende Sortieren (und finden des Medians) dauert noch mal knapp 5 Sekunden.

Was ich damit sagen will: Um die Performance von Datenstrukturen würde ich mir erst dann Gedanken machen, wenn du auch wirklich ein Performance Problem hast oder mit ner sehr schwachen CPUs arbeitest (Mikrocontroler).

 

[mambokurt]

+1 für Array. Von der Geschwindigkeit her wirst du für Meridian und Co keine Probleme bekommen. Ich benutze unter Php viel assoziative Arrays, die sind weder fix noch speicherfreundlich, trotzdem lag mein fiesester Fall aus der Praxis bei knapp 200MB und unter 20 Sekunden Laufzeit ( inklusive Datenbankmambojambo und viel Aufbereitung mit relativ großen Datensätzen). Über die Datenstruktur würde ich mir erst Gedanken machen wenn der Ram ausgeht oder es dir zu langsam wird.