<p>这是一个很常见的问题,让您的数据按时间戳值排序,然后对每个可能的查询进行二进制搜索。可以使用<a href="https://docs.python.org/2/library/bisect.html" rel="nofollow">bisect module</a>执行二进制搜索:</p>
<pre><code>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
</code></pre>
<p>我们可以这样测试:</p>
^{pr2}$
<p>如果我们有<code>n</code>查询和<code>m</code>时间戳值,那么每个查询都需要<code>O(log m)</code>时间。所以需要的总时间是<code>O(n * log m)</code>。在</p>
<p>在上面的算法中,我们在两个索引之间搜索。如果我们只使用时间戳间隔的中点,我们可以更简化并创建更快的搜索:</p>
<pre><code>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]
</code></pre>