Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

I think what you are asking is given a time series (x_0, x_1... x_n), what is the 6 month high (or low) on day i? In other words you want the max (or min) of the sub series (x_{i-180},x_{i-179}... x_i).

x_0 is obviously the 6 month high at day 0 (since there is no previous data). If x_1 > x_0 then x_1 is the new 6 month high so we can discard x_0 on day 1. If x_1 < x_0 then x_0 is still the 6 month high on day 1, but we cannot discard x_1 because it might become the 6 month high when x_0 expires on day 181. So we need to maintain some sort of data structure of potential 6 month highs such that we can lookup the current high and remove these highs as they expire or get replaced. The easiest way to do this is with a list of pairs [(x_i1, i1), (x_i2, i2)...] sorted by increasing x_i. Because it is sorted, the current high is always found on the element closest to the end of the list. Furthermore when a new element (x_k, k) is added, it replaces all the elements which come before it (thus they can be removed). As a corollary, because the newest element is always added to the back (after removing what's in front of it), the list is also sorted by order of expiry (with the oldest (x_i,i) at the end). Start with an empty list and i = 0

Find the sorted insertion point in the list for (x_i,i).

Remove everything prior to the insertion point.

Insert (x_i, i) at the start of the list.

If the element at the end of the list (x_n, n) is expired (n < i+180) then remove it.

The 6 month high on day i is found in the element at the end of the list. Store this in a new series h_i.

Increment i by 1 and repeat.

This method trivially works for finding the 6 month low as well.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: