如何找到 Python 数据集中的最大百分比下降？ （股市）

Question

我目前正在处理股票市场分析，并试图找到一种快速算法，使我能够计算给定数据集中的最大价格跌幅，我认为这是一个值得考虑的好算法问题。因此，输入将是特定时间间隔内股票的股价，输出将是所有价格下跌的最大值。

这是一个可视化的例子，请看图片； （百分比由眼睛决定）

Stock Price Image

我粗略地表示了一些价格下降及其百分比。尽管最后一次降价是其价值的最大值，但降价 %60 的是我想要找到的那个。

提前致谢

Answer 1

解决方案：

您可以通过向后迭代股票价值在线性时间内完成。

您跟踪到目前为止看到的最小元素，因为最大的下降总是会到达仍然位于它之前的最小值。然后你可以计算从每个点到它前面的最小元素的相对下降，并只跟踪你找到的最大下降。

这是 Python 中的一个实现。确保您了解我在做什么以及它为什么有效，以确保它符合您所想的问题。

def getGreatestDrop(stock):
    """Calculates the greatest relative drop of a stock.
    @param stock: 1-D list contianing the values of that stock
    Returns a tuple with the relative drop size, the index of the start and the
    index of the end of that drop.
    """

    min = None # The smallest absolute value seen so far
    minIndex = None  # The index of the smallest absolute value smallest value
    greatestDrop = None # The biggest relative drop seen so far
    greatestDropStart = None # The index of the drop start
    greatestDropEnd = None # The index of the drop end

    # Iterating backwards through the array, starting from the last element
    for index in range(len(stock)-1,-1,-1):
        # Update min
        if min is None or stock[index] < min:
            min = stock[index]
            minIndex = index

        # Calculate relative drop
        drop = 1-min/stock[index]

        # Update greatest drop
        if greatestDrop is None or drop > greatestDrop:
            greatestDrop = drop
            greatestDropStart = index
            greatestDropEnd = minIndex

    # Return values
    return greatestDrop, greatestDropStart, greatestDropEnd

---

示例：

这是一个示例程序，我在 6 只随机生成的股票上使用了这个函数：

#!/usr/bin/env python3

import random
import numpy as np
from matplotlib import pyplot as plt

def generateRandomStock(length, volatility=1, trend=0, scale=100, lowest=500):
    """Generat
    @param stock: 1-D list contianing the values of that stock
    Returns a tuple with the relative drop size, the index of the start and the
    index of the end of that drop.
    """
    out = np.ndarray(length)
    value = 0
    for i in range(length):
        value += volatility*(random.random()-0.5) + trend
        out[i] = value
    out *= scale
    out -= out.min()
    out += lowest
    return out

def getGreatestDrop(stock):
    """Calculates the greatest relative drop of a stock.
    @param stock: 1-D list contianing the values of that stock
    Returns a tuple with the relative drop size, the index of the start and the
    index of the end of that drop.
    """

    min = None # The smallest absolute value seen so far
    minIndex = None  # The index of the smallest absolute value smallest value
    greatestDrop = None # The biggest relative drop seen so far
    greatestDropStart = None # The index of the drop start
    greatestDropEnd = None # The index of the drop end

    # Iterating backwards through the array, starting from the last element
    for index in range(len(stock)-1,-1,-1):
        # Update min
        if min is None or stock[index] < min:
            min = stock[index]
            minIndex = index

        # Calculate relative drop
        drop = 1-min/stock[index]

        # Update greatest drop
        if greatestDrop is None or drop > greatestDrop:
            greatestDrop = drop
            greatestDropStart = index
            greatestDropEnd = minIndex

    # Return values
    return greatestDrop, greatestDropStart, greatestDropEnd

if __name__ == "__main__":

    # Create subplots
    width = 3
    height = 2
    fig, axs = plt.subplots(width, height)

    # Fix random seed to get the same results every time
    random.seed(42)

    # Draw all plots
    for w in range(width):
        for h in range(height):
            # Generate stocks randomly
            stocks = generateRandomStock(1000)
            axs[w][h].plot(stocks)

            # Calculate greatest drop
            drop, dropStart, dropEnd = getGreatestDrop(stocks)
            axs[w][h].plot([dropStart, dropEnd],[stocks[dropStart],stocks[dropEnd]], color="red")

            # Set title
            axs[w][h].set_title("Greatest Drop is {:.1f}% from {} to {}".format(100*drop, dropStart, dropEnd))

    # Show all results
    plt.show()

输出：