Python中最近的时间戳price-ready数据结构？

Question

价格插值。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很棒，你的助手是最好的！在

Answer 1

试试这个来得到最接近的值

l = [ [1427837961000.0, 243.586], [1427962162000.0, 245.674], [1428072262000.0, 254.372], [1428181762000.0, 253.366]]
check_value = 1427854534654
>>>min(l, key=lambda x:abs(x[0]-check_value))[0]
1427837961000.0

Answer 2

这是一个很常见的问题，让您的数据按时间戳值排序，然后对每个可能的查询进行二进制搜索。可以使用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

我们可以这样测试：

^{pr2}$

如果我们有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]

Answer 3

解决了！在

我用了JuniorCompressor's solution和我的bugfix for future约会。在

表演非常精彩：

3000000次通话耗时12.82秒，因此每次通话0.00000427（数据长度=1143）。在

非常感谢！StackOverFlow很棒，你的助手是最好的！在