Esiste un buon algoritmo per verificare le modifiche nei dati in un periodo di tempo specificato?

Question

Abbiamo circa 7.000 prodotti finanziari i cui prezzi di chiusura dovrebbero teoricamente salire e scendere entro un certo intervallo percentuale durante un periodo di tempo definito (ad esempio una settimana o un mese).

Ho accesso a un sistema interno che memorizza questi prezzi storici (non un database relazionale!).Vorrei produrre un report che elenchi tutti i prodotti il ​​cui prezzo non è cambiato affatto o meno del 10% nel periodo di tempo.

Non posso semplicemente confrontare il primo valore (giorno 1) con il valore alla fine (giorno n), poiché il prezzo potrebbe potenzialmente essere tornato al livello dell'ultimo giorno, il che porterebbe a un falso positivo mentre il prezzo del prodotto ovviamente avrebbe potuto avere un picco nel mezzo.

Esistono algoritmi consolidati per eseguire questa operazione in tempi di calcolo ragionevoli?

Answer 1

Se è necessario controllarlo spesso (per un numero elevato di intervalli, ad esempio quotidianamente per l'ultimo anno e per lo stesso insieme di prodotti), è possibile memorizzare i valori massimo e minimo di ciascun articolo per settimana/mese.Combinando i giusti limiti settimanali e/o mensili con alcuni dati grezzi ai bordi dell'intervallo è possibile ottenere il valore minimo e massimo nell'intervallo.

Answer 2

Non c'è modo di farlo senza guardare ogni singolo giorno.

Supponiamo che i dati siano tali:

oooo0oooo

Con quel picco di un giorno nel mezzo.Non lo noterai a meno che non controlli il giorno in cui si verifica il picco: in altre parole, devi controllare ogni singolo giorno.

Answer 3

Se puoi aggiungere dati a kdb (ad es.non sei limitato all'accesso in lettura) potresti prendere in considerazione l'aggiunta del "numero di giorni dall'ultima variazione di prezzo" come nuovo insieme di dati (ad es.un numero per strumento finanziario).Un'attività quotidiana recupererebbe quindi il punteggio di oggi e quello di ieri e aggiornerebbe i numeri memorizzati.Allo stesso modo potresti mantenere i massimi e i minimi recenti (ultimo mese, ultimo anno) in kdb.Inizialmente dovresti eseguire un lavoro sul set di dati più grande per innescare i valori, ma poi i tuoi aggiornamenti giornalieri coinvolgeranno molti meno dati.

Consiglia se adotti qualcosa del genere di avere un modo per rieseguire tutto o parte del set di dati (ad esempio per aggiungere un nuovo prodotto).

Infine: lo storico è normalizzato rispetto ai prezzi attuali?(cioè.vengono prese in considerazione rivalutazioni per frazionamenti azionari o simili).In caso contrario, dovresti rilevare queste discontinuità e suddividerle.

MODIFICARE

Indagherei usando kdb+/Q per implementare l'elaborazione del segnale, anziché estrarre i dati grezzi in un'applicazione Java.Come dici tu, è altamente performante.

Answer 4

Puoi farlo se riesci a tenere traccia del valore minimo e massimo del prezzo durante l'intervallo di tempo: ciò presuppone che l'intervallo di tempo non venga modificato costantemente.Un modo per tenere traccia dei valori minimo e massimo di un insieme di articoli che cambia è con due heap posizionati "schiena contro schiena": potresti memorizzare questo e alcuni puntatori necessari per trovare e rimuovere vecchi articoli in uno o due array nel tuo negozio .L'idea di mettere due mucchi uno dopo l'altro si trova in Art of Computer Programming Vol 3 di Knuth come Esercizio 31, sezione 5.2.3.Knuth chiama questo tipo di bestia una Dequeue Prioritaria, e sembra che sia possibile effettuare ricerche.Min e max sono disponibili a costo costante.Il costo per modificarlo quando arriva un nuovo prezzo è log n, dove n è il numero di articoli archiviati.