Éviter l'appel Big Database sur une médiane en cours d'exécution

Question

Pas vraiment une question de codage, plus d'un comment puis-je faire cette question, donc pas d'extrait de code.

Dans ma base de données, imaginez une longue liste de nombres non triés.

Nums = [9, 12, 15, 18, 22, 100, 1, 4, 3, 2]
Cela me donne une médiane de 10,5

Mais imaginez maintenant ma liste est beaucoup plus longue, [ 9, 12, 15, 18, 22, 100, 1, 4, 3, 2, ......] Et chaque jour, je présente un nouveau numéro à cette liste x. La liste est stockée dans une base de données et je veux éviter de frapper la base de données pour obtenir toutes ces données et ensuite calculer la médiane.

Y at-il des astuces où je n'ai pas besoin d'appeler toutes les données tous les jours pour calculer la médiane d'aujourd'hui après l'introduction d'un nouveau numéro?

Merci pour vos idées!

Answer 1

Vous n'avez pas besoin de toutes les valeurs individuelles pour calculer une médiane. Si vous avez une estimation initiale pour un intervalle où la médiane doit se situer (par exemple entre 5 et 20), vous pouvez diviser les valeurs:

• LOW: compter les valeurs inférieures à l'intervalle (x < = 5), donnant un nombre de 4.
• CENTER: interroger les valeurs dans l'intervalle (5 x < < 20), ce qui donne 9, 12, 15, 18.
• HIGH: compter les valeurs ci-dessus de l'intervalle (x> = 20) , donnant un compte de 2.

Comme le nombre BAS est deux de plus que le haut t, supprime les deux valeurs les plus élevées de CENTER et calcule la médiane des valeurs restantes.

Si la différence de comptage ne laisse aucun chiffre au CENTRE, vous devez modifier l'intervalle et réessayer. Avec une indexation correcte de la colonne de base de données, les trois requêtes devraient être assez rapides, et la quantité de données qui en résulte ne devrait pas créer trop de trafic entre la base de données et le logiciel client. Une variante ne nécessitant pas de supposition initiale pourrait être de compter les valeurs par des cases de, par ex. 5 (trunc (x/5)), ce qui donne:

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

Si le nombre médian est atteint dans une poubelle, vous interrogez les numéros de cette poubelle et calculez leur médiane. Mais dans notre exemple, c'est juste entre les cases 5 ... 9 et 10 ... 14, donc les deux cases doivent être interrogées (5 < = x < = 14) et la médiane tirée des (deux) valeurs résultantes 9 et 12, donnant 10.5.