30000 punktów danych, znajdź największą zmianę czasu, przez 2 tygodnie

Question

mam:

- 30,000 data points 
- each data point is a measurement of type float 
- each measurement is associated with a date 
- each date has only one measurement 
- no dates are without measurements 
- the data comes in the form of a text file: 30,000 lines in this form: 
    - YYYY-MM-DD I,F (e.g. 1977-02-08 20.74) 
- measurement appearing in the source file are already sorted by date 

muszę:

- a time-interval T with boundaries (s,e) /* start, end */ 
- (s - e = 14 days) the time-interval *must* be 2 weeks 
- define min as the lowest value in the interval T 
- define max as the greatest value in the interval T 
- the chosen T needs to have the greatest distance btwn max and min of all possible Ts 
- break ties among intervals T by choosing the most recent (with the greatest s value) 
- the chosen T must consider all jumps in the 14 days, not just the values @ s and e 
- if the overall "variance" in the interval is great but the jump 
    |max-min| is not the greatest in absolute value, T is not the right choice, 
    even if it's an "exciting" interval 

Pytam:

- which algorithm to employ, considering algorithms are not my specialty 
- which data structure to use to keep track of the subtotals 

Uwaga:

- an answer in pseudo code would be preferred, "prose" is fine if pressured for time 
- an answer in Python would be... splendid :) 

Jeśli chcesz, możesz wygenerować "fałszywe" dane i uruchomić proponowany algorytm jako test lub udostępnić rzeczywiste dane.

Tu nie chodzi mi o wydajność, poza tym, że chcę znać najszybszy sposób, aby to zrobić, aby nauczyć się, jak zastosować właściwe rozwiązanie i prawidłowy algorytm.

Myślę, że mogę "udowodnić" poprawność nawet z najprostszym algorytmem iteracyjnym, ponieważ zbiór danych jest niewielki, biorąc pod uwagę dzisiejsze komputery.

Do tej pory "poruszam się i przenoszę 14 wektorów z 14 pomiarów", jeśli mógłbyś nauczyć mnie, jak robić to stopniowo z subsumami, byłoby to naprawdę docenione.

Answer 1

Jeśli Cię rozumiem, masz:

30 000 różnych uporządkowanych wartości danych. Zamawianie odbywa się według daty, ale to nie ma znaczenia.
W tym zestawie znajduje się 29 986 podzbiorów, w których zawartość jest uporządkowaną sekwencją rozpoczynającą się w jednym punkcie danych i zawierającą ten początkowy punkt oraz trzynaście następujących punktów danych.

Powoli:

1) odczytaj 30 000 punktów danych w tablicy o wielkości 30 000.
2) przydzielić tablicę o rozmiarze 29 996. Nazwij tę tablicę "Potencjalni zwycięzcy".
3) wypełnij tablicę potencjalnych zwycięzców, skanując każdy 14-punktowy podzestaw, tymczasowo zatrzymując maksymalną wartość i minimalną wartość napotkaną w podzbiorze. Gdy te dwie wartości są w zasięgu ręki, zapisz (maks. Min.) W lokalizacji indeksu - od punktu początkowego - w ramach Potencjalnych Zwycięzców. Nie próbuj żadnych przesuwających się okien optymalizacyjnych; patrz poniżej.
4) Wykonaj liniowy skan Potencjalnych Zwycięzców, zapisując wartość i (co ważne) indeks, w którym się znajduje.
BTW: co zrobić, gdy nie ma jednego zwycięzcy? Jeśli wszystkie punkty danych będą miały tę samą wartość, otrzymasz 29 986 zwycięzców, wszyscy o tej samej wartości.
5) Optymalizacja: nie należy przydzielać i wypełniać Potencjalnych Zwycięzców; zainicjuj bieżący zwycięzca do krotki (wartość, indeks) jako (0, -1). Oblicz wartość każdego 14-punktowego podzestawu jak powyżej, ale zachowaj tylko lepszą wartość spośród {Bieżący zwycięzca, "wartość, którą otrzymuję z bieżącego podzbioru"}

6) Przesuwane okna: Nie przemyślałem tego, ale myślę, że utrzymanie przesuwanego okna to więcej pracy niż opisane powyżej proste przejście liniowe.
Powód: ok, oblicz wartość pierwszych 14 punktów; uzyskać minimum i maksimum, i uzyskać interwał między nimi. Ale czekaj, potrzebujemy wartości minimalnej i maksymalnej, aby użyć ich w następnym oknie. Teraz przesuń okno o jedną pozycję w górę. Wartość na lewym końcu zniknęła; ale czy było to min, max, czy pomiędzy?Załóżmy, że to była min, a teraz już jej nie ma. Jaka jest wartość drugiej najniższej minuty? Nie mamy tych informacji.
Aby zachować okno przesuwne, należy posortować każdą podsekcję 14-punktową i zapamiętać pozycję indeksu wszystkich wartości. Następnie, po przesunięciu, możesz sprawdzić, czy wartość, która spadła po lewej stronie, to stare min. Lub stare maksimum, oraz to, czy nowa wartość po prawej to nowa min czy nowa maks. Ale nie jest to warte wysiłku.
(Ta sytuacja przypomina trochę algorytm szybkiego poszukiwania Boyer-Moore, nie pamiętam szczegółów, ale wymaga on wstępnego przetworzenia całego wejścia i przechowywania tabeli lokalizacji, w których występuje każda wartość. jest sposobem off-topic)

Nadzieja to pomaga ...

Answer 2

przesuwne okna faktycznie tu pracować, utrzymując dwa stosy (być może jest to trochę mylące, ponieważ jest to prawdopodobnie najlepiej realizowane jako podwójnie -nowa kolejka). Zachowaj stos minstack i stos o nazwie maxstack. Istotą algorytmu jest to, że minstack powinien być ściśle zgodny z niezmniejszającym się, a maxstack powinien być ściśle nie rosnący we wszystkich punktach slajdu. Jak to robimy?

Najpierw dodaj pierwsze 14 punktów do stosu. Zdefiniujmy add(point) jak:

Czy to dla minstack:

• Podczas gdy punkt jest mniejszy niż początkowy element minstack, zdjąć górną element minstack.
• Dodaj punkt do minstack.

Podobnie dla maxstack:

• Gdy nowa wartość jest większa niż górny element maxstack, zdejmowania elementu maxstack.
• Dodaj punkt do maxstack.

Ze względu na powyższą właściwość, min i max pierwszych 14 elementów powinny być dolnymi elementami minstack i maxstack. Teraz przesuń okno. Po prostu musimy zauważyć, że jeśli lewy punkt jest nadal "żywy" w dowolnym stosie, to jest to teraz punkt końcowy. Dlatego powinno to być łatwe, po prostu:

slide(): 
    add(new_point) 
    if (left_point == bottom(minstack)) remove_bottom(minstack) 
    if (left_point == bottom(maxstack)) remove_bottom(maxstack) 

Powtarzaj tę czynność, dopóki Twoje punkty nie zostaną wyczerpane. Interwał, którego szukasz, to taki, w którym bottom(maxstack) - bottom(minstack) był największy.

Zauważ, że jakikolwiek punkt trafia maksymalnie w minstack/maxstack raz, a każdy punkt również co najwyżej raz opuszcza stosy, dlatego robi to co najwyżej 4 operacje dla każdego punktu, bez względu na rozmiar żądanego przedziału.

EDYCJA: Właśnie zauważyłem, że chciałeś wykonania w Pythonie. Tak naprawdę nie chcę analizować danych, więc funkcja pobiera listę wartości jako dane wejściowe i wyprowadza indeksy (s, e) z tej tablicy:

import collections 

def add(x, minstack, maxstack): 
    while minstack and x < minstack[-1]: minstack.pop() 
    while maxstack and x > maxstack[-1]: maxstack.pop() 
    minstack.append(x) 
    maxstack.append(x) 

def get_largest_interval(points): 
    minstack = collections.deque() 
    maxstack = collections.deque() 

    best_diff = -1 
    best_interval = None 

    for index, elem in enumerate(points): 
     add(elem,minstack,maxstack) 
     if index >= 14: 
      if minstack[0] == points[index-14]: minstack.popleft() 
      if maxstack[0] == points[index-14]: maxstack.popleft() 

     if index >= 13: 
      this_diff = maxstack[0]-minstack[0] 
      if best_diff == -1 or this_diff >= best_diff: 
       best_interval = (index-13, index) 
       best_diff = this_diff 

    return best_interval 


print get_largest_interval([0, 2, 2,2,2,2,2,2,2,2,2,2,2,2,3])