c********r
发帖数: 1422 | 1 【 以下文字转载自 JobHunting 讨论区 】
发信人: challenger (Ray), 信区: JobHunting
标 题: algorithm optimzation problem
发信站: BBS 未名空间站 (Mon Feb 13 14:38:45 2012, 美东)
given a time series A with Y data points, what is the fastest algorithm to
produce another time series B. Each value in B is the highest value of
series A within specified look back period Z.
Thanks. | s***e
发帖数: 267 | 2 Not sure about fastest. How about have a multiple pass, depending on your Z
value.
For instance, if Z=4, then first pass construct a time series A1 which
stores the max in Z/2=2 look back window. The second pass build A2 from A1,
etc, by using gap=1 points.
The base does not need to be 2 (the comparison becomes a little more
expensive then) and the number of pass needed is log(Z). | r***6
发帖数: 401 | 3 Should be able to do it in single pass while keep a sorted structure to
contain window z.
1. Use a sorted map (balanced tree) structure so insertion, deletion, and
retieve largest value cost is log(z)
2. For each item i, insert it into the map, then retrieve the largest item
to construct new time series. Lastly you remove (i-z) th item from the map.
The total cost is n*log(z).
Not sure about fastest. How about have a multiple pass, depending on your Z
value.For in........
★ Sent from iPhone App: iReader Mitbbs 7.39
【在 s***e 的大作中提到】
: Not sure about fastest. How about have a multiple pass, depending on your Z
: value.
: For instance, if Z=4, then first pass construct a time series A1 which
: stores the max in Z/2=2 look back window. The second pass build A2 from A1,
: etc, by using gap=1 points.
: The base does not need to be 2 (the comparison becomes a little more
: expensive then) and the number of pass needed is log(Z).
| l*****y
发帖数: 56 | 4 Not sure if I understand the question correctly. I thought the question asks
for some kind of "moving maximal" for the most recent Z elements.
For example, if a time series has data [1,8,3,7,2], Z=2. Then the lookback
maximals for 2 periods would be 8,8,7,7.
Your algorithm will find the maximal Z elements of the time series.
For the above example, your algorithm will find 8,3, 7,2.
Please correct me if I were wrong.
.
Z
【在 r***6 的大作中提到】
: Should be able to do it in single pass while keep a sorted structure to
: contain window z.
: 1. Use a sorted map (balanced tree) structure so insertion, deletion, and
: retieve largest value cost is log(z)
: 2. For each item i, insert it into the map, then retrieve the largest item
: to construct new time series. Lastly you remove (i-z) th item from the map.
: The total cost is n*log(z).
:
: Not sure about fastest. How about have a multiple pass, depending on your Z
: value.For in........
| G******e
发帖数: 229 | 5 If the window size Z is large, you can use a heap to make the time
complexity O(NlogZ). | m*****y
发帖数: 8 | 6 这个有线性算法。只需用栈要维护一个最大递降序列。
就是下面这个里面的算法：
http://zhiqiang.org/blog/science/computer-science/max-drawdown-
【在 c********r 的大作中提到】
: 【 以下文字转载自 JobHunting 讨论区 】
: 发信人: challenger (Ray), 信区: JobHunting
: 标 题: algorithm optimzation problem
: 发信站: BBS 未名空间站 (Mon Feb 13 14:38:45 2012, 美东)
: given a time series A with Y data points, what is the fastest algorithm to
: produce another time series B. Each value in B is the highest value of
: series A within specified look back period Z.
: Thanks.
| m*****y
发帖数: 8 | | C***m
发帖数: 120 | 8 很赞，感觉有线性算法，又想不清楚。你的blog写得很好啊
【在 m*****y 的大作中提到】
: 这个有线性算法。只需用栈要维护一个最大递降序列。
: 就是下面这个里面的算法：
: http://zhiqiang.org/blog/science/computer-science/max-drawdown-
| s***d
发帖数: 81 | 9 之前就看过zhiqiang的blog，数学金牌+姚期智的博士，确实nb
【在 C***m 的大作中提到】
: 很赞，感觉有线性算法，又想不清楚。你的blog写得很好啊
| c********r
发帖数: 1422 | 10 thanks.
【在 m*****y 的大作中提到】
: 这个有线性算法。只需用栈要维护一个最大递降序列。
: 就是下面这个里面的算法：
: http://zhiqiang.org/blog/science/computer-science/max-drawdown-
|
|
