价格插值。用于高效未命中搜索的 Python 数据结构?
我有价格数据
[1427837961000.0, 243.586], [1427962162000.0, 245.674], [1428072262000.0, 254.372], [1428181762000.0, 253.366], ...
第一个维度是时间戳,第二个维度是价格。
现在我想知道最接近给定时间戳的价格,例如到 1427854534654。
每秒解决数百或数千次问题的最佳 Python 容器、数据结构或算法是什么?这是一个标准问题,在许多应用中都必须解决,因此应该有现成的优化解决方案。
我用 Google 搜索过,只找到了一些我可以构建的点点滴滴 - 但我想这个问题很常见,整个数据结构应该作为一个模块准备好了吗?
编辑:已解决。
我用了JuniorCompressor's solution和我的 bugfix for future日期。
性能非常棒:
3000000 次调用耗时 12.82 秒,因此每次调用 0.00000427(数据长度 = 1143)。
非常感谢! StackOverFlow 很棒,您是最棒的 helper !
请您参考如下方法:
这种问题很常见,即按时间戳值对数据进行排序,然后对每个可能的查询进行二进制搜索。可以使用 bisect module 执行二进制搜索:
data = [
[1427837961000.0, 243.586],
[1427962162000.0, 245.674],
[1428072262000.0, 254.372],
[1428181762000.0, 253.366]
]
data.sort(key=lambda l: l[0]) # Sort by timestamp
timestamps = [l[0] for l in data] # Extract timestamps
import bisect
def find_closest(t):
idx = bisect.bisect_left(timestamps, t) # Find insertion point
# Check which timestamp with idx or idx - 1 is closer
if idx > 0 and abs(timestamps[idx] - t) > abs(timestamps[idx - 1] - t):
idx -= 1
return data[idx][1] # Return price
我们可以这样测试:
>>> find_closest(1427854534654)
243.586
如果我们有 n 个查询和 m 个时间戳值,那么每个查询需要 O(log m) 时间。所以所需的总时间是 O(n * log m)。
在上面的算法中,我们在两个索引之间进行搜索。如果我们只使用时间戳间隔的中点,我们可以进一步简化并创建更快的搜索:
midpoints = [(a + b) / 2 for a, b in zip(timestamps, timestamps[1:])]
def find_closest_through_midpoints(t):
return data[bisect.bisect_left(midpoints, t)][1]
