是否有更好的方法来改进我的算法在股票市场中发现下跌？

Question

我正在计算每一只股票的提款。缩编的定义是

提款是指投资、交易账户或基金在某一特定时期内的峰值至低谷下降.

简单地说，减持是指股市从高点跌至谷底的程度。除此之外，当峰值价格在稍后某个时候回升时，就会记录下降情况。

为了计算缩编，我将分解为2点。

1. 找出峰值(哪一种价格大于2天的价格)和低谷(哪一种价格低于相邻2天的价格)
2. 当峰值价格回升时，这个峰值、低谷就变成了下跌。

以下是股票报价的一个例子：

        data class Quote(val price: Int, val date: String)
        ...
        //example of quote     
        Quote(price:1, date:"20080102"),
        Quote(price:2, date:"20080103"),
        Quote(price:3, date:"20080104"),
        Quote(price:1, date:"20080107"),
        Quote(price:2, date:"20080108"),
        Quote(price:3, date:"20080109"),
        Quote(price:2, date:"20080110"),
        Quote(price:4, date:"20080111"),
        Quote(price:5, date:"20080114"),
        Quote(price:6, date:"20080115"),
        Quote(price:7, date:"20080116"),
        Quote(price:8, date:"20080117"),
        Quote(price:9, date:"20080118"),
        Quote(price:7, date:"20080122"),
        Quote(price:6, date:"20080123"),
        Quote(price:8, date:"20080124"),
        Quote(price:11,date:"20080125"),
        
        list of drawdowns by date: 
            (peak: "20080104", trough:"20080107", daysTakenToRecover: 3),
            (peak: "20080109", trough:"20080110", daysTakenToRecover: 2),
            (peak: "20080118", trough:"20080123", daysTakenToRecover: 4),

下面是为测试用例编写的内容：

 class Drawdown {
              var peak: Quote? = null
              var trough: Quote? = null
              var recovered: Quote? = null
              var percentage: Double? = null
              var daysToRecover: String? = null
       }

       data class Quote(
            val price: Double,
            val date: String
       )
      
 class Test {
          private fun findDrawdowns(): List<Drawdown> {
          val list = mutableListOf<Drawdown>()
          var peak: Quote? = null
          var trough: Quote? = null
          var recovered: Quote? = null

    for (quotation in quotations) {
        val currentIdx = quotations.indexOf(quotation)
        if (currentIdx in 1 until quotations.size - 1) {
            val prevClosing = quotations[currentIdx - 1].price
            val nextClosing = quotations[currentIdx + 1].price
            val closing = quotation.price

            recovered = when {
                peak == null -> null
                closing >= peak.price -> {
                    if (peak.date != quotation.date) {
                        //can possibly be new peak
                        Quote(closing, quotation.date)
                    } else null
                }
                else -> null
            }

            peak = if (closing > prevClosing && closing > nextClosing) {
                if ((peak == null || peak.price < closing) && recovered == null) {
                    Quote(closing, quotation.date)
                } else peak
            } else peak

            trough = if (closing < prevClosing && closing < nextClosing) {
                if (trough == null || trough.price > closing) {
                    Quote(closing, quotation.date)
                } else trough
            } else trough


            if (recovered != null) {
                val drawdown = Drawdown()
                val percentage = (peak!!.price - trough!!.price) / peak.price

                drawdown.peak = peak
                drawdown.trough = trough
                drawdown.recovered = recovered
                drawdown.percentage = percentage
                drawdown.daysToRecover =
                    ChronoUnit.DAYS.between(
                        LocalDate.of(
                            peak.date.substring(0, 4).toInt(),
                            peak.date.substring(4, 6).toInt(),
                            peak.date.substring(6, 8).toInt()
                        ),
                        LocalDate.of(
                            recovered.date.substring(0, 4).toInt(),
                            recovered.date.substring(4, 6).toInt(),
                            recovered.date.substring(6, 8).toInt()
                        ).plusDays(1)
                    ).toString()
                list += drawdown
                peak = if (closing > prevClosing && closing > nextClosing) {
                    Quote(recovered.price, recovered.date)
                } else {
                    null
                }
                trough = null
                recovered = null
            }
        }
    }
    val drawdown = Drawdown()
    val percentage = (peak!!.price - trough!!.price) / peak.price

    drawdown.peak = peak
    drawdown.trough = trough
    drawdown.recovered = recovered
    drawdown.percentage = percentage
    list += drawdown
    return list
    }

对于那些想在github中阅读我的代码的人，下面是一个要点：

在科特林找到撤退点，点击我！

我运行了一些测试用例，它没有显示错误。

到目前为止，我相信这需要一个O(n)，但我想使它更有效。

我该如何改进呢？任何意见，想法都欢迎！

谢谢大家，新年快乐。

Answer 1

有两点

1. 不幸的是，当前的复杂性是O(N^2)。

for (quotation in quotations) {
        val currentIdx = quotations.indexOf(quotation)
        ....

您有一个循环遍历所有的引号，在每个引号中您都可以找到它的索引。找到索引是O(N) -看看indexOf文档。因此，总复杂度为O(N^2)。

但您可以轻松地将其修正为O(N)。只需将foreach循环+ indexOf替换为forEachIndexed，例如：

        quotations.forEachIndexed { index, quote ->
            // TODO
        }

1. 我认为它不可能比O(N)更快，因为您需要检查每个报价。