python - 最小窗口长度的最大回撤

Question

对于给定的 float 时间序列，很容易在 O(n) 时间内计算无约束的最大回撤，其中最大回撤定义为

\min_{i,j, i<j}(x_j - x_i)

在 python 中，我们的计算是 min(x - numpy.expanding_max(x))，但要获得 O(n) 算法，请显式编写:

def max_drawdown(s):
    drawdn = 0
    m,M = s[0],s[0]
    t1,t2 = 0,0
    T1,T2 = 0,0
    for i,v in enumerate(s):
        if (v < m):
            if (v-m) < drawdn:
                drawdn = v-m
                t2 = i
                T1,T2 = t1,t2
        else:
            m = v
            t1 = i
    return T1,T2,drawdn

是否有 O(n) 算法来限制窗口持续时间 > min_length 的 max_drawdown？在这种情况下，我想要\min_{i,j, (j-i) > min_length}(x_j - x_i)。

请注意，这不是 Compute *rolling* maximum drawdown of pandas Series 中的“滚动缩减”计算。 .

Answer 1

与您的 max_drawdown 函数相比，修改非常小。目前的算法可以写成伪代码

Iterate over list
  if (current_element > maximum)
    maximum = current_element
  if (current element - maximum < drawdn)
    drawdn = current_element-maximum

现在不是在同一索引处搜索 max_drawdown，而是搜索最大值，我们需要与这些索引有 min_length 的距离。在 Python 中，这变成了:

def max_drawdown_min_lenght(s,min_length):
    min_length += 1 #this is for i-j > l (not i-j >= l)
    drawdn = 0
    m = s[0]
    t1 = 0
    T1,T2 = 0,0
    for i in range(len(s)-min_length):
        if (s[i] >= m): #do we have new maximum?
            m = s[i]
            t1 = i
        if (s[i+min_length]-m) < drawdn:#do we have new max drawdown?
            drawdn = s[i+min_length]-m
            T1,T2 = t1,i+min_length
    return T1,T2,drawdn