30.000 punti dati, trovare più grande cambiamento di tempo oltre 2 settimane

Question

ho:

- 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 

ho bisogno:

- 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 

chiedo:

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

Nota:

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

Se lo si desidera, è possibile generare dati "fittizi" ed eseguire l'algoritmo proposto come test oppure condividere i dati effettivi.

Non mi interessa molto le prestazioni qui oltre a voler sapere il modo più veloce per farlo, in modo da imparare come applicare la soluzione giusta e l'algoritmo corretto.

Penso di poter "dimostrare" la correttezza anche con il più semplice algoritmo iterativo perché il dataset è piccolo dato ai computer di oggi.

Finora, sto "attraversando e trasportando 14 vettori di 14 misure", se poteste insegnarmi a farlo in modo incrementale con sub-somme, sarebbe molto apprezzato.

Answer 1

Se ho capito, hai:

30.000 valori di dati distinti e ordinati. L'ordine è per data, ma non è rilevante.

All'interno di questo set, ci sono 29.986 sottoinsiemi in cui i contenuti sono una sequenza ordinata che inizia da un punto dati e contiene quel punto iniziale e tredici punti dati seguenti.


Prendendo molto lentamente:

1) leggere i vostri 30.000 punti di dati in una matrice di dimensioni 30.000.

2) allocare una matrice di dimensione 29.986. Chiama questo array "Potential Winners".

3) riempire la matrice dei potenziali vincoli analizzando ciascun sottoinsieme a 14 punti, mantenendo temporaneamente il valore massimo e il valore minimo rilevato nel sottoinsieme. Quando questi due valori sono in mano, salva (Max-Min) nella posizione dell'indice - del punto di partenza-- tra i potenziali vincitori. Non provare alcuna ottimizzazione di Windows scorrevole; vedi sotto.

4) Effettuare una scansione lineare dei potenziali vincitori, salvando il valore e (importante) l'indice al quale si trova.

BTW: cosa fai se non c'è un singolo vincitore? Se tutti i punti di accesso hanno lo stesso valore, otterrai 29.986 vincitori di candidati, tutti con lo stesso valore.

5) Ottimizzazione: non assegnare e riempire potenziali vincitori; inizializza il vincitore corrente con la tupla (valore, indice) come (0, -1). Calcola il valore di ogni sottoinsieme a 14 punti come sopra, ma conserva solo il valore migliore tra {Current Winner, "il valore che ottengo da questo sottoinsieme corrente"}

6) Finestre scorrevoli: non ci ho pensato, ma penso che mantenere una finestra scorrevole sia più lavoro del semplice passaggio lineare descritto sopra.

Il motivo: ok, calcola il valore dei primi 14 punti; ottenere un minimo e un massimo e ottenere l'intervallo tra di loro. Ma aspetta, abbiamo bisogno dei valori minimo e massimo da usare nella finestra successiva. Ora fai scorrere la finestra di una posizione verso l'alto. Il valore all'estremità sinistra è scomparso; ma era il minimo, il massimo o nel mezzo?Supponiamo che fosse il minimo, ed ora non c'è più. Quale valore è il secondo minimo più basso? Non abbiamo queste informazioni.

Per mantenere una finestra scorrevole, è necessario ordinare ciascuna sottosequenza di 14 punti dati e ricordare la posizione dell'indice di tutti i valori. Quindi, quando scorri, puoi sapere se il valore che è caduto a sinistra era il vecchio min o il vecchio massimo, e se il nuovo valore che è entrato a destra è il nuovo min o il nuovo massimo. Ma non ne vale la pena.

(Questa situazione ricorda un po 'l'algoritmo di ricerca della sottostringa veloce di Boyer-Moore. Non ricordo i dettagli, ma implica la pre-elaborazione dell'intero input e la conservazione di una tabella delle posizioni in cui si verifica ogni valore. è il modo off-topic)

Spero che questo aiuti ...

Answer 2

finestre scorrevoli realtà non lavorare qui, tenendo due pile (forse questo è un po 'fuorviante, in quanto questo è probabilmente meglio implementato come doppiamente coda di coda). Mantieni uno stack minstack e uno stack chiamato maxstack. Il nodo dell'algoritmo è che minstack deve essere rigorosamente non decrescente e maxstack deve essere rigorosamente non crescente in tutti i punti della diapositiva. Quindi, come lo facciamo?

Innanzitutto, aggiungi i primi 14 punti a una pila. Definiamo add(point) come:

fare questo per il minstack:

• Mentre il punto è più piccolo l'elemento superiore del minstack, rimuovere l'elemento superiore del minstack.
• Aggiungere il punto a minstack.

Analogamente, per il maxstack:

• Mentre il nuovo punto è più grande l'elemento superiore della maxstack, rimuovere l'elemento superiore della maxstack.
• Aggiungere il punto a maxstack.

A causa della proprietà di cui sopra, il minimo e il massimo dei primi 14 elementi dovrebbero essere gli elementi in basso di minstack e maxstack. Ora fai scorrere la finestra. Dobbiamo semplicemente notare che se il punto di sinistra è ancora "vivo" in uno qualsiasi degli stack, è necessariamente ora il punto in basso. Quindi questo dovrebbe essere facile, è semplicemente:

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

Fallo finché i punti non sono esauriti. L'intervallo che stai cercando è quello in cui bottom(maxstack) - bottom(minstack) era il più grande.

Si noti che qualsiasi punto entra minstack/maxstack al massimo una volta, e ogni punto lascia le pile al massimo una volta, quindi questo fa al massimo 4 operazioni per ogni punto, indipendentemente dalla dimensione dell'intervallo desiderato.

EDIT: Ho appena notato che volevi un'implementazione in Python. Non volevo veramente analizzare i dati, quindi la funzione prende un elenco di valori come input e restituisce gli indici (s, e) in quell'array:

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])