Algoritmo: conta con efficienza le occorrenze recenti

Come fai notare alcuni dei dati di input sono ordinati, che possono essere sfruttati. E come sospetti, sarà utile ordinare l'altro array. Inoltre, come lo hai descritto, l'array di output corrisponde a 1: 1 a uno degli ingressi già ordinati.

Questo suggerisce di iterare su quell'input ordinato per produrre l'output. Quindi, vogliamo fare qualcosa che assomigli più a questo:

define CountEventsWithinInterval(MeasurementDates, EventDates, Interval):
    for i in 0:length(MeasurementDates)
        aMeasurementDate = MeasurementDates [ i ]
        eventCount =  ??? ( aMeasurementDate, EventDates )
        result [ i ] := eventCount
    return result

Ora, abbiamo bisogno di un algoritmo per calcolare il numero di volte in cui una determinata data di misurazione rientra nell'intervallo degli eventi dati. Per fare ciò, se gli eventi fossero anche ordinati, cercheremmo la prima posizione negli eventi che si trovano entro una determinata data di misurazione - intervallo (es. La fine anticipata dell'intervallo dell'intervallo), quindi contiamo il numero di eventi finché non siamo oltre la data di misurazione indicata. Possiamo quindi ignorare il resto degli eventi dati oltre a quello perché si verificano in futuro (relativamente a una determinata data di misurazione di interesse corrente).

La parte costosa qui è la ricerca di trovare la parte bassa della finestra dell'intervallo per quella data gamma di misurazione. La ricerca in media cerca, ad esempio, metà della serie di eventi, e si verifica come un ciclo annidato con le misurazioni, abbiamo ancora un costo O (m * n) qui (beh, * (n / 2) ma questo è tutto nel rumore ).

Tuttavia, sappiamo che possiamo attraversare (sto attraversando nel mio il frammento di cui sopra) le date di misurazione nell'ordine di inoltro, così, una volta trovata la posizione della finestra dell'evento per una determinata iterazione (cioè per una determinata data di misurazione), possiamo usarlo come posizione di partenza per la (successiva iterazione) cercare nell'algoritmo di cui sopra. In questo modo, le ricerche saranno ridotte al minimo e attraverseremo efficacemente (tramite la ricerca) l'array Eventi una sola volta, dall'inizio alla fine. Quindi, la ricerca non sarà nemmeno il costo di un ciclo annidato, che converte il costo in qualcosa come O (m + n) invece di O (m * n) (questo grande O sta ignorando la dimensione dell'intervallo, che si aggiunge al costo, ovviamente, quindi questo è solo m + n per l'intervallo minimo.)

In questo modo marcia in avanti su due matrici di input (e una matrice di output); uno (le date di misurazione) procede linearmente dall'inizio alla fine; le scansioni lineari godono di una buona misura del comportamento del caching dei sistemi (cache della CPU e paging della memoria). Per l'altro (date degli eventi) avanziamo la posizione di ricerca come possiamo e attraversiamo un intervallo degli elementi in una finestra scorrevole. In generale, l'efficacia della cache della CPU dovrebbe essere ancora più elevata nell'usare questo tipo di finestra scorrevole, in quanto una gamma / finestra più piccola viene ripetutamente colpita finché è di dimensioni ragionevoli (anche se a intervalli più grandi supererà la cache e quindi soffrirà tremendamente ).

Archivia questi dati in un database, quindi esegui una query utilizzando un linguaggio di query come SQL.

Ciò renderà i dati molto più facili da archiviare e manipolare e sarai in grado di ottenere la risposta a questa e ad altre domande dai dati in modo molto semplice ed efficiente.

Nel tuo esempio puoi inserire le date di misurazione in una tabella e quindi eseguire una query come questa:

select measurement_date,count(*) 
   from measurement_dates
   join stock_price_data on 
      stock_date between measurement_date - interval days and measurement
   group by measurement_date

Si noti che nella query sopra, non è necessario specificare come ottenere il risultato , solo ciò che si desidera (in termini tecnici SQL è un < a href="https://en.wikipedia.org/wiki/Declarative_programming"> lingua dichiarativa ). Questo è più facile per te e, a causa delle ampie ottimizzazioni per garantire una manipolazione efficiente dei dati, in genere funzionerà molto meglio di qualsiasi algoritmo tu possa scrivere.

L'aggiunta di un database alla tua applicazione potrebbe sembrare scoraggiante se non hai mai lavorato con una di queste versioni, ma a lungo andare sarà davvero redditizia. Dopo il sovraccarico iniziale, renderà tutto ciò che farai più facilmente. Inoltre, esistono numerosi buoni database gratuiti disponibili e tutte le principali lingue hanno strumenti di database prontamente disponibili.

Un approccio leggermente diverso da quello che è stato già fornito.

Si inizia ordinando entrambi i gruppi di input. Quindi prendi la prima data di misurazione e fai una ricerca binaria sulla data dell'evento (cioè un set di dati artificiali di span dalle date dell'evento). Se lo facessi semplicemente, non stai più facendo confronti con M N. Stai facendo M logN confronti.

Ma possiamo fare di meglio. Poiché le tue misurazioni sono ordinate, una volta che conosci il primo evento correlato alle tue misurazioni, puoi impostare l'inizio della ricerca binaria per l'elemento successivo a quell'elemento (suppongo che tu possa avere date di misurazione duplicate). Quindi ogni ricerca è successivamente più veloce.

Ma aspetta, c'è dell'altro! Invece di spostare la seconda misura dopo la prima, andare alla fine e fare una ricerca sull'ultima misurazione. Ora usa quel risultato come nuova estremità della finestra di ricerca. Poi vai al secondo, e poi il penultimo, ecc. Continua a chiudere la finestra mentre arrivi verso il centro delle misure. Ad esempio, se si dispone di dieci elementi si andrebbe in questo ordine, 0,9,1,8,2,7,3,6,4,5, ogni volta che l'aggiornamento della finestra di ricerca inizia o termina.