Vermeiden von Big Database-Aufruf auf einem laufenden Median

Question

Nicht wirklich eine Codierung Frage, mehr wie kann ich diese Frage tun, also kein Code-Snippet.

In meiner Datenbank stellen Sie sich eine lange Liste unsortierter Nummern vor.

nums = [9, 12, 15, 18, 22, 100, 1, 4, 3, 2]
Das gibt mir einen Median von 10,5

Aber jetzt meine Liste vorstellen, viel länger ist, [ 9, 12, 15, 18, 22, 100, 1, 4, 3, 2, ......] Und jeden Tag führe ich eine neue Nummer in diese Liste x ein. Die Liste wird in einer Datenbank gespeichert, und ich möchte vermeiden, dass die Datenbank getroffen wird, um alle diese Daten zu erhalten und dann den Median zu berechnen.

Gibt es irgendwelche Tricks, bei denen ich nicht jeden Tag alle Daten aufrufen muss, um den Median für heute zu berechnen, nachdem eine neue Nummer eingeführt wurde?

Danke für jede Idee!

Answer 1

Sie benötigen nicht alle individuellen Werte für die Berechnung eines Medians. Wenn Sie eine erste Schätzung für ein Intervall, wo der Median liegen sollte (beispielsweise zwischen 5 und 20), können Sie die Werte aufgeteilt:

• LOW: die Werte unter dem Intervall zählen (x < = 5), mit eine Zählung von 4.
• CENTER: die Werte innerhalb des Intervalls abzufragen (5 < x < 20), mit 9, 12, 15, 18
• HIGH: die Werte oberhalb der Intervallzählung (x> = 20) mit einer Zählung von 2.

Wie die niedrige Zählung ist zwei mehr, dass die HOHE coun t, löschen Sie die beiden höchsten Werte von CENTER und berechnen Sie den Median der verbleibenden Werte.

Wenn die Zähldifferenz keine Zahlen in CENTER enthält, müssen Sie das Intervall ändern und es erneut versuchen.

Bei korrekter Indexierung der Datenbankspalte sollten die drei Abfragen relativ schnell sein und die resultierende Datenmenge sollte nicht zu viel Datenverkehr zwischen Datenbank und Clientsoftware verursachen.

Eine Variante, die keine anfängliche Schätzung benötigt, könnte darin bestehen, die Werte nach Bins von z. 5 (trunc (x/5)), mit:

• 0 ... 4: count = 4
• 5 ... 9: count = 1
• 10 ... 14: count = 1
• 15 ... 19: count = 2
• 20 ... 24: count = 1
• 100 ... 104: count = 1

Wenn der mittlere Zählwert innerhalb erreicht ist ein Bin, Sie fragen die Zahlen aus diesem Fach und berechnen th Eir Median. Aber in unserem Beispiel ist es nur zwischen dem 5 ... 9 und dem 10 ... 14 Bin, also müssen beide Bins abgefragt werden (5 < = x < = 14) und der Median aus den (zwei) resultierenden Werten 9 und 12, geben 10.5.