Czy istnieje dobry algorytm sprawdzania zmian danych w określonym przedziale czasu?

Question

Mamy około 7k produktów finansowych, których ceny zamknięcia powinny teoretycznie przesuwać się w górę i w dół w pewnym zakresie procentowym przez określony czas (powiedzmy na tydzień lub miesiąc).

Mam dostęp do wewnętrznego systemu przechowującego te historyczne ceny (a nie relacyjnej bazy danych!). Chciałbym sporządzić raport zawierający listę wszystkich produktów, których cena nie zmieniła się w ogóle lub w mniejszym stopniu niż 10% w danym okresie.

Nie mogę po prostu porównać pierwszej wartości (dzień 1) z wartością na końcu (dzień n), ponieważ cena potencjalnie mogła powrócić do stanu z ostatniego dnia, który doprowadziłby do fałszywego podczas gdy cena produktu mogła oczywiście wzrosnąć gdzieś pomiędzy.

Czy istnieją jakieś ustalone algorytmy w rozsądnym czasie obliczeń?

Answer 1

Jeśli trzeba często sprawdzać (w przypadku dużej liczby interwałów, podobnie jak codziennie w ciągu ostatniego roku i dla tego samego zestawu produktów), można przechowywać wysokie i niskie wartości każdej pozycji na tydzień/miesiąc . Łącząc właściwe tygodniowe i/lub miesięczne ograniczenia z pewnymi nieprzetworzonymi danymi na krawędziach przedziału, można uzyskać minimalną i maksymalną wartość w danym przedziale.

Answer 2

Nie można tego zrobić bez patrzenia na każdy dzień.

Załóżmy, że dane takie wygląda:

oooo0oooo 

Z tej jednodniowej skok w środku. Nie złapiesz tego, chyba że sprawdzisz dzień, w którym nastąpi kolec - innymi słowy, musisz sprawdzać każdego dnia.

Answer 3

Jeśli możesz dodać dane do kdb (tj. Nie jesteś ograniczony do odczytu), możesz rozważyć dodanie "liczby dni od ostatniej zmiany ceny" jako nowego zestawu danych (tj. Jednej liczby na instrument finansowy) . Codzienne zadanie pobierze dzisiejszy znak i wczoraj, a także zaktualizuje zapisane numery. Podobnie można utrzymać ostatnie (ostatnie miesiące, ostatnie lata) wysokie i niskie wartości w kdb. Trzeba by było uruchomić zadanie nad większym zbiorem danych, aby wstępnie przygotować wartości, ale wtedy codzienne aktualizacje będą wymagać znacznie mniejszej ilości danych.

Zaleca się, że jeśli przyjmiesz coś takiego, masz możliwość ponownego uruchomienia całego lub części zestawu danych (powiedzmy o dodaniu nowego produktu).

Wreszcie - czy historia jest znormalizowana w stosunku do aktualnych cen? (tj. uwzględnia się przeszacowania dla podziału akcji lub podobnych). Jeśli nie, musisz wykryć te nieciągłości i podzielić je.

EDIT

będę badać usng kdb+/Q do realizacji przetwarzania sygnału, zamiast wydobycia surowych danych do aplikacji Java. Jak mówisz, jest to bardzo wydajne.

Answer 4

Możesz to zrobić, jeśli możesz śledzić minimalną i maksymalną wartość ceny w danym przedziale czasu - zakłada to, że przedział czasu nie jest stale zmieniany. Jednym ze sposobów śledzenia minimalnych i maksymalnych wartości zmieniającego się zestawu przedmiotów są dwa stosy umieszczane "od tyłu do tyłu" - możesz przechowywać to i kilka wskazówek niezbędnych do znalezienia i usunięcia starych przedmiotów z jednej lub dwóch tablic w twoim sklepie . Pomysł umieszczenia dwóch stosów z powrotem do tyłu znajduje się w Knuth's Art of Computer Programming Vol 3 jako Exercise 31, rozdział 5.2.3. Knuth nazywa ten rodzaj bestii Dequeue Priority, a to wydaje się być do przeszukiwania.Min. I maks. Są dostępne przy stałym koszcie. Koszt modyfikacji, gdy nadejdzie nowa cena, to log n, gdzie n to liczba przechowywanych przedmiotów.