Y at-il un bon algorithme pour vérifier les changements dans les données sur une période de temps?

Question

Nous avons environ 7k produits financiers dont les cours de clôture théoriquement devrait monter et descendre dans une certaine plage de pourcentage pendant une période de temps définie (par exemple une période d'une semaine ou mois).

J'ai accès à un système interne qui stocke ces prix historiques (pas une base de données relationnelle!). Je voudrais produire un rapport répertoriant tous les produits dont le prix n'a pas bougé du tout ou moins dire 10% sur la période.

Je ne peux pas comparer la première valeur (jour 1) à la valeur à la fin (jour n) que le prix pourrait être déplacé à ce qu'elle était le dernier jour, ce qui conduirait à un tout faux positif le prix du produit aurait hérissé quelque part entre bien sûr.

Y a-t-il des algorithmes mis en place pour le faire dans le temps de calcul raisonnable?

Answer 1

Si cela doit être vérifié souvent (pour un grand nombre d'intervalle, comme tous les jours pour l'année dernière, et pour la même série de produits), vous pouvez stocker les valeurs hautes et basses de chaque article par semaine / mois. En combinant les bonnes limites hebdomadaires et / ou mensuelles avec des données brutes sur les bords de l'intervalle, vous pouvez obtenir le minimum et la valeur maximale sur l'intervalle.

Answer 2

Il n'y a aucune façon de le faire sans regarder chaque jour.

Supposons que les données ressemble par exemple:

oooo0oooo

Avec cette pointe d'une journée au milieu. Tu ne vas pas attraper que si vous vérifiez le jour où la pointe se produit -. Autrement dit, vous devez vérifier chaque jour

Answer 3

Si vous pouvez ajouter des données à KDB (vous n'êtes pas limité à l'accès en lecture), vous pouvez envisager d'ajouter le « nombre de jours depuis le dernier changement de prix » comme un nouvel ensemble de données (à savoir un numéro par instrument financier). Une tâche quotidienne alors chercher la marque d'aujourd'hui et d'hier, et mettre à jour les numéros mémorisés. De même, vous pouvez maintenir des hauts et des bas récents (le mois dernier, l'an dernier) à KDB. Il faudrait exécuter un travail sur l'ensemble de données plus pour amorcer les valeurs au départ, mais vos mises à jour quotidiennes implique beaucoup moins de données.

Recommandons que si vous adoptez quelque chose comme cela, vous avez un moyen de ré-exécuter tout ou partie de l'ensemble de données (par exemple pour ajouter un nouveau produit).

Enfin - est l'histoire normalisée par rapport aux prix actuels? (À savoir sont pour réévaluations de division ou similaire pris en compte). Sinon, vous auriez besoin de détecter ces discontinuités et les diviser en.

EDIT

Je KDB + / Q pour mettre en œuvre le traitement du signal, plutôt que l'extraction des données brutes à une application Java. Comme vous le dites, il est très performant.

Answer 4

Vous pouvez le faire si vous pouvez garder une trace de la valeur min et max du prix au cours de l'intervalle de temps - cela suppose que l'intervalle de temps n'est pas constamment changé. Une façon de garder la trace des valeurs min et max d'un ensemble d'éléments changeant est avec deux tas placés « dos à dos » - vous pouvez stocker cela et quelques conseils nécessaires pour trouver et supprimer les anciens éléments dans un ou deux tableaux dans votre magasin . L'idée de mettre deux tas dos à dos est dans l'art de la programmation informatique Knuth Vol 3 en tant que section Exercice 31 5.2.3. Knuth appelle ce genre de bête un Dequeue prioritaire, et cela semble être une recherche. Min et max sont disponibles à coût constant. Le coût de la modifier lorsqu'un nouveau prix est log n où n est le nombre d'éléments stockés.