我有:
- 30,000 data points
- each data point is a measurement of type float
- each measurement is associated with a date
- each date has only one measurement
- no dates are without measurements
- the data comes in the form of a text file: 30,000 lines in this form:
- YYYY-MM-DD I,F (e.g. 1977-02-08 20.74)
- measurement appearing in the source file are already sorted by date
我需要:
- a time-interval T with boundaries (s,e) /* start, end */
- (s - e = 14 days) the time-interval *must* be 2 weeks
- define min as the lowest value in the interval T
- define max as the greatest value in the interval T
- the chosen T needs to have the greatest distance btwn max and min of all possible Ts
- break ties among intervals T by choosing the most recent (with the greatest s value)
- the chosen T must consider all jumps in the 14 days, not just the values @ s and e
- if the overall "variance" in the interval is great but the jump
|max-min| is not the greatest in absolute value, T is not the right choice,
even if it's an "exciting" interval
我在问:
- which algorithm to employ, considering algorithms are not my specialty
- which data structure to use to keep track of the subtotals
注意:
- an answer in pseudo code would be preferred, "prose" is fine if pressured for time
- an answer in Python would be... splendid :)
如果需要,您可以生成"虚拟"数据并将您提出的算法作为测试运行,或者我可以共享实际数据.
除了想要了解最快的方法以便学习如何应用正确的解决方案和正确的算法之外,我并不关心这方面的性能.
我认为即使是最简单的迭代算法也能"证明"正确性,因为今天的计算机数据集很小.
到目前为止,我正在"遍历和携带14个测量的14个向量",如果你可以教我如何用子和递增,这将是非常值得赞赏的.
如果我理解你的话，你有：
30,000 个不同的、有序的数据值。排序恰好是按日期进行的，但这并不相关。
在该集合中，有 29,986 个子集，其中内容是从一个数据点开始并包含该初始点和随后的 13 个数据点的有序序列。
慢慢来：
1）将 30,000 个数据点读入大小为 30,000 的数组中。
2) 分配一个大小为29,986的数组。将此阵列称为“潜在赢家”。
3）通过扫描每个14点子集来填充Potential Winners数组，暂时保存子集中遇到的最大值和最小值。当这两个值在手时，将（最大-最小）保存在潜在获胜者内的索引位置（起点）。不要尝试任何滑动窗口优化；见下文。
4) 对潜在赢家进行线性扫描，保存该值和（重要的是）它所在的索引。
顺便说一句：如果没有唯一的获胜者，你会怎么做？如果所有数据点都具有相同的值，您将获得 29,986 个候选获胜者，全部具有相同的值。
5）优化：不分配和填补Potential Winners；将当前获胜者初始化为元组（值，索引）为（0，-1）。如上所述计算每个 14 点子集的值，但仅保留 {当前获胜者，“我从当前子集获得的值”} 中较好的值
6）滑动窗口：我还没有考虑过这一点，但我认为维护滑动窗口比上述简单的线性传递需要更多工作。
原因：好吧，计算前14个点的值；获取最小值和最大值，并获取它们之间的间隔。但是等等，我们需要在下一个窗口中使用最小值和最大值。现在将窗口向上滑动一个位置。左端的值没有了；但它是最小值、最大值还是介于两者之间？假设这是分钟，现在已经消失了。第二低的最小值是多少？我们没有那个信息。
为了保持滑动窗口，您需要对每个 14 个数据点子序列进行排序并记住所有值的索引位置。然后，当你滑动时，你可以知道左边掉出的值是旧的最小值还是旧的最大值，以及右边进来的新值是新的最小值还是新的最大值。但这不值得付出努力。
（这种情况有点让人想起 Boyer-Moore 快速子串查找算法。我不记得细节了，但它涉及预处理整个输入并保留每个值出现的位置的表格。但这还很遥远。 -话题）
希望这可以帮助...