Welche Statistiken können für eine Menge numerischer Daten ohne Iteration gepflegt werden?

Aktualisieren

Nur zur zukünftigen Referenz lese ich alle mir bekannten Statistiken auf, die in einer rolling collection verwaltet werden können, die bei jedem als O (1) -Operation neu berechnet wird Addition / Entfernung (so hätte ich eigentlich die Frage von Anfang an formulieren sollen):

Offensichtlich

• Zählen
• Summe
• Mein
• Max *
• Min *
• Median **

Weniger offensichtlich

• Abweichung
• Standardabweichung
• Schiefe
• Kurtosis
• Modus ***
• gewichteter Durchschnitt
• gewichteter gleitender Durchschnitt ****

OK, um es genauer zu sagen: Das sind nicht "alle" Statistiken, die mir bekannt sind. Sie sind nur diejenigen, an die ich mich im Augenblick von meinem Kopf erinnern kann.

_{* Kann in O (1) nur für Additionen oder für Additionen und Entfernungen neu berechnet werden, wenn die Auflistung sortiert ist (aber in diesem Fall ist die Einfügung nicht O (1)). Umzüge können möglicherweise eine O (n) Neuberechnung für nicht sortierte Sammlungen zur Folge haben.}

_{** Neu berechnet in O (1) nur für eine sortierte, indizierte Sammlung.}

_{*** Erfordert eine ziemlich komplexe Datenstruktur zur Neuberechnung in O (1).}

_{**** Dies kann sicher in O (1) für Additionen und Entfernungen erreicht werden, wenn die Gewichte linear absteigend zugewiesen werden. In anderen Szenarien bin ich mir nicht sicher.}

Ursprüngliche Frage

Sagen Sie, ich pflege eine Sammlung von numerischen Daten - sagen wir mal, nur ein paar Zahlen. Für diese Daten gibt es viele berechnete Werte, die von Interesse sein könnten. ein Beispiel wäre die Summe. Um die Summe all dieser Daten zu erhalten, könnte ich ...

Option 1: Durchsuche die Sammlung und füge alle Werte hinzu:

Option 2: Pflegen Sie die Summe und eliminieren Sie die Notwendigkeit, immer über die Sammlung zu iterieren, nur um die Summe zu finden:

BEARBEITEN Um diese Frage besser zu verstehen, vergleichen wir die beiden obigen Optionen mit einer (realen) Situation:

Angenommen, ich fange an, Nummern aufzulisten und Sie aufzufordern, sie in Ihrem Kopf zu behalten. Ich fange mit den Worten "11, 16, 13, 12" an. Wenn du dich gerade an die Zahlen selbst und nicht mehr erinnert hast und dann sage: "Was ist die Summe?", Musst du dir überlegen: "OK, was ist 11 + 16 + 13 + 12?" bevor er antwortet, "52." Hättest du andererseits die Summe selbst im Auge behalten, während ich die Zahlen auflistete (dh als ich "11" sagte, dachtest du "11", als ich "16" sagte "Sie dachten," 27, "und so weiter), Sie könnten" 52 "sofort antworten. Dann, wenn ich sage, "OK, vergessen Sie jetzt die Nummer 16", wenn Sie die Summe in Ihrem Kopf im Auge behalten haben, können Sie einfach 16 von 52 nehmen und wissen, dass die neue Summe 36 ist, anstatt 16 zu nehmen die Liste und sie summieren sich 11 + 13 + 12.

Meine Frage ist also, welche anderen Berechnungen, außer den offensichtlichen wie Summe und Durchschnitt, so sind?

ZWEITE BEARBEITUNG: Als willkürliches Beispiel für eine Statistik, die (ich bin mir fast sicher) macht Iteration erforderlich - und kann daher nicht so einfach wie eine Summe verwaltet werden oder Durchschnitt - bedenken Sie, wenn ich Sie fragte, "wie viele Zahlen in dieser Sammlung sind durch die min teilbar?" Nehmen wir an, die Zahlen sind 5, 15, 19, 20, 21, 25 und 30. Die min dieser Menge ist 5, die sich in 5, 15, 20, 25 und 30 (aber nicht 19 oder 21) teilt Die Antwort ist 5. Wenn ich jetzt 5 aus der Sammlung entferne und dieselbe Frage stelle, lautet die Antwort jetzt 2, da nur 15 und 30 durch die neue Min von 15 teilbar sind; aber soweit ich das beurteilen kann, kannst du das nicht wissen, ohne die Sammlung noch einmal durchzugehen .

Ich denke also, das bringt meine Frage auf den Punkt: Wenn wir Arten von Statistiken in diese Kategorien einteilen können, diejenigen, die wartbar sind (vielleicht mein eigener Begriff) es gibt einen offiziellen Ort irgendwo) im Vergleich zu denen, die Iteration benötigen, um jederzeit zu berechnen, wann eine Sammlung geändert wird, was sind alle wartbaren ?

Was ich frage, ist nicht genau das gleiche wie ein Online-Algorithmus (obwohl ich denen von euch aufrichtig danke, die führte mich zu diesem Konzept). Ein Online-Algorithmus kann mit seiner Arbeit beginnen, ohne dass alle Eingabedaten gesehen sind; Die wartbaren Statistiken , die ich suche, werden sicherlich alle Daten gesehen haben, sie müssen sie nicht immer wieder wiederholen, wenn sie sich ändern.