如何在时间序列数据中找到最大增长率？

Question

我想知道在给定时间段内求最大增长率的算法

假设我们有八（N）个数据点，如下所示

list_x = [84,59,52,71,62,82,45,50]
def find_max(list_x):
   # return the L index, H index, ratio
   # take list_x as an example, L index: 3(52), H index: 6(82), ratio: 82/52 
   # should return (3, 6, 1.57)
   return L,H,dy/dx

一种简单的方法是通过O（N*N），存储比率dicts，然后按比率排序。 有什么有效的算法吗？谢谢

Answer 1

使用Numpy将嵌套循环推送到C

import numpy as np

a = np.array([84,59,52,71,62,82,45,50])

计算每个点与所有其他点之间的差值

b = (a - a[:,None])

计算所有这些差异的dy/dx。这假设x值是连续且均匀分布的

d = np.arange(a.shape[0], dtype=float)
d = d-d[:,None]
d[d==0] = .00001
c  = b / d

找到最大dy/dx的索引，并使用它们来获得产生它的值

max_dydx = np.triu(c).max()
indices = np.where(np.triu(c) == max_dydx)
values = a[np.concatenate(indices)]
print(indices, values)

---

>>>
(array([4], dtype=int64), array([5], dtype=int64)) [62 82]

---

中间数组-值在对角线上反映

>>> print(b.round(1))
[[  0 -25 -32 -13 -22  -2 -39 -34]
 [ 25   0  -7  12   3  23 -14  -9]
 [ 32   7   0  19  10  30  -7  -2]
 [ 13 -12 -19   0  -9  11 -26 -21]
 [ 22  -3 -10   9   0  20 -17 -12]
 [  2 -23 -30 -11 -20   0 -37 -32]
 [ 39  14   7  26  17  37   0   5]
 [ 34   9   2  21  12  32  -5   0]]
>>> print(d.round(1))
[[ 0.  1.  2.  3.  4.  5.  6.  7.]
 [-1.  0.  1.  2.  3.  4.  5.  6.]
 [-2. -1.  0.  1.  2.  3.  4.  5.]
 [-3. -2. -1.  0.  1.  2.  3.  4.]
 [-4. -3. -2. -1.  0.  1.  2.  3.]
 [-5. -4. -3. -2. -1.  0.  1.  2.]
 [-6. -5. -4. -3. -2. -1.  0.  1.]
 [-7. -6. -5. -4. -3. -2. -1.  0.]]
>>> print(c.round(1))
[[  0.  -25.  -16.   -4.3  -5.5  -0.4  -6.5  -4.9]
 [-25.    0.   -7.    6.    1.    5.8  -2.8  -1.5]
 [-16.   -7.    0.   19.    5.   10.   -1.8  -0.4]
 [ -4.3   6.   19.    0.   -9.    5.5  -8.7  -5.2]
 [ -5.5   1.    5.   -9.    0.   20.   -8.5  -4. ]
 [ -0.4   5.8  10.    5.5  20.    0.  -37.  -16. ]
 [ -6.5  -2.8  -1.8  -8.7  -8.5 -37.    0.    5. ]
 [ -4.9  -1.5  -0.4  -5.2  -4.  -16.    5.    0. ]]

Answer 2

正如我在一篇评论中提到的，看起来您是在寻找H/L而不是dy/dh，因为您的预期结果是(3, 6, 1.57)。假设您确实想要执行H/L，那么您可以尝试以下操作：

def max_result(arr):
    max_growth, cur_min, cur_min_idx = float('-inf'), float('inf'), -1
    res_l = res_h = float('-inf')
    for i, val in enumerate(arr):
        if val / cur_min > max_growth:
            max_growth = val / cur_min
            res_l, res_h = cur_min_idx, i
        if val < cur_min:
            cur_min, cur_min_idx = val, i
    return res_l + 1, res_h + 1, round(max_growth, 2)

这里的复杂性是O(N)