找到当天结束时触及的第一个价格的算法。搜索算法

Question

我全天都有一系列价格。我需要找到每个时间点的价格在一天结束时是先上涨50%还是下跌50%。

目前我只能考虑暴力破解——将当前价格与下面的每一个价格进行比较，直到满足上述要求或者遍历当天的所有价格。

有什么好的方法可以解决这个问题吗？非常感谢您！

there are six price movements by the end of the day.
price=[1, 1.3, 0.9, 1.5, 0.65, 3]
label=[1, -1, 1, -1, 1]
Explanation:
at t0, the price is 1 and it first goes up to 1.5 rather than down to 0.5, so the label is 1.
at t1, the price is 1.3 and it first drops down to 0.65 rather than up to 1.95, so the label is -1.
at t2, the price is 0.9 and it first goes up to 1.5 (0.9*1.5=1.35) rather than down to 0.45(0.9*0.5), so the label is 1.
at t3, the price is 1.5 and it first drops down to 0.65 (1.5*0.5=0.75) rather than up to 3, so the label is -1.
at t4, the price is 0.65 and it first goes up to 3 (0.65*1.5=0.975) rather than down to 0.325 (0.65*0.5), so the label is 1.
If the price change lies within -50% - +50%, the label will be 0.

Answer 1

我认为你可以比朴素算法做得更好。但是：这在很大程度上取决于您拥有的数据量和实施情况。请记住，使用 O(n * n) 算法的实现可能比使用 O(n) 算法的实现更快，具体取决于输入大小 (n) 和实现中的常数因子。因此，您要做的第一件事就是定义基准。

无论如何，我宁愿反过来处理这个问题。不是依次为每个价格搜索标签，而是将新价格与还没有标签的现有价格结合起来。该算法的大致轮廓如下：

• 从价格序列中获取新价格。
• 将所有未标记的先前价格标记为 -1，其中先前价格至少是该价格的两倍。
• 将所有未标记的先前价格标记为+1，其中先前价格最多为该价格的三分之二。
• 将新价格标记为未标记。
• 重复直到没有新价格可用。
• 用 0 标记所有剩余的未标记价格。

在实现中，将未标记的价格存储在排序的容器中。这使得很容易找到用 -1 或 +1 标记的价格，因为它们位于容器的两端。

将此应用于您的示例数据将如下所示：

• unlabelled=[]
• 句柄1@t0
  • unlabelled=[1@t0]
• 句柄1.3@t1
  • unlabelled=[1@t0, 1.3@t1]
• 处理0.9@t2
  • unlabelled=[0.9@t2, 1@t0, 1.3@t1]
• 处理1.5@t3
  • 标签 0.9@t2 和 +1
  • 标签 1@t0 和 +1
  • unlabelled=[1.3@t1, 1.5@t3]
• 句柄0.65@t4
  • 用 -1 标记 `1.3@t1
  • 标签 1.5@t3 与 -1
  • unlabelled=[0.65@t4]
• 句柄3@t5
  • 标签 0.65@t4 和 +1
  • unlabelled=[3@t5]
• 标签 3@t5 和 0

备注：

• 一般的建议是考虑排序。如果您有可以通过排序改进的算法，请考虑将排序作为前一步。此一般规则不直接适用，只能通过对未标记项目列表进行排序来间接适用。
• 这在很大程度上取决于您用于无标签物品的容器。我会尝试链表、数组和树。此外，一些其他数据结构也可能使用价格是标量这一事实。不过，如前所述，您需要基准测试！