python - 我可以使用具有已知步骤的排序数组来制作 O(1) 搜索算法吗？

Question

背景

我的软件可视化非常的大型数据集，例如数据是如此之大，我无法在任何时候将所有数据存储在 RAM 中，它需要以页面方式加载。我嵌入了 matplotlib 功能，用于在我的应用程序后端显示和操作绘图。

这些数据集包含我用来可视化的三个内部列表:time、height 和 dataset。我的程序用 time x height 绘制数据，此外，用户可以选择在图形区域周围绘制形状，这些形状可以提取到整个不同的图中。

困难的部分是，当我想从形状中提取数据时，形状顶点是绘图计算的真实坐标，而不是在我的时间<中四舍五入到最近的点 数组。这是一个在我的程序中限制区域的形状示例

虽然根据matplotlib X1可能代表坐标(2007-06-12 03:42:20.070901+00:00, 5.2345)，但最接近的坐标existing time 和 height 可能类似于 (2007-06-12 03:42:20.070801+00:00, 5.219) ，与 matploblib 的坐标只有一点点偏差。

---

问题

因此给定一些任意值，假设 x1 = 732839.154395(以数字格式表示日期)和一个具有常量步长的相似值列表:

732839.154392
732839.154392
732839.154393
732839.154393
732839.154394
732839.154394
732839.154395
732839.154396 
732839.154396
732839.154397
732839.154397
732839.154398
732839.154398
732839.154399
etc...

找到该点最接近表示的最有效方法是什么？我可以简单地遍历列表并获取具有最小差异的值，但是 time 的大小巨大。因为我知道数组是 1. Sorted 和 2. Increments with a constant step ，我在想这个问题应该能够在 O(1) 时间内解决？是否有解决此类问题的已知算法？或者我只需要设计一些自定义算法，这是我目前的思考过程。

grab first and second element of time
subtract second element of time with first, obtain step
subtract bounding x value with first element of time, obtain difference
divide difference by step, obtain index
move time forward to index
check surrounding elements of index to ensure closest representation

Answer 1

您建议的算法似乎很合理并且可以正常工作。

正如您在评论中所说的那样，问题在于您的时间记录过于粗糙。 (这在记录非同步数据时很常见——即数据生成时钟(例如帧速率)与计算机不同步)。

解决此问题的简单方法是读取间隔较长时间的两个点，例如，读取第一个时间值，然后读取第 1000 个时间值。然后在你的计算中一切都保持不变，但通过减去然后除以 1000 得到你的时间步

这是一个使数据与您的相似的测试:

import matplotlib.pyplot as plt

start = 97523.29783
increment = .000378912098
target = 97585.23452

# build a timeline
times = []
time = start
actual_index = None
for i in range(1000000):
    trunc = float(str(time)[:10])  # truncate the time value
    times.append(trunc)
    if actual_index is None and time>target:
        actual_index = i
    time = time + increment

# now test
intervals = [1, 2, 5, 10, 100, 1000, 10000]

for i in intervals:
    dt = (times[i] - times[0])/i
    index = int((target-start)/dt)
    print "    %6i  %8i  %8i  %.10f" % (i, actual_index, index, dt)

结果:

  span    actual     guess  est dt (actual=.000378912098)
     1    163460    154841  0.0004000000
     2    163460    176961  0.0003500000
     5    163460    162991  0.0003800000
    10    163460    162991  0.0003800000
   100    163460    163421  0.0003790000
  1000    163460    163464  0.0003789000
 10000    163460    163460  0.0003789100

也就是说，随着采样点之间的空间越来越大，时间间隔估计越来越准确(与程序中的 increment 比较)并且估计的索引(第 3 列)越来越接近实际索引(第二列)。请注意，dt 估计的准确性基本上与跨度中的位数成正比。你能做的最好的事情就是在起点和终点使用时间，但从你的问题陈述来看，这似乎很困难；但如果不是，它会给出最准确的时间间隔估计。请注意，在这里，为了清楚起见，我通过使我的时间间隔记录非常当然来夸大准确性的缺乏，但一般来说，跨度中的每个 10 的幂都会增加相同数量的准确性。

作为最后一点的示例，如果我通过将路线更改为 trunc = float(str(time)[:12]) 来减少时间值的粗略性，我得到:

  span    actual     guess  est dt (actual=.000378912098)
     1    163460    163853  0.0003780000
    10    163460    163464  0.0003789000
   100    163460    163460  0.0003789100
  1000    163460    163459  0.0003789120
 10000    163460    163459  0.0003789121

因此，如果如您所说，使用 1 的跨度可以让您非常接近，那么使用 100 或 1000 的跨度应该绰绰有余。

总的来说，这在思想上与线性“插值搜索”非常相似。它只是更容易实现，因为它只是根据插值进行一次猜测，所以它只需要一行代码:int((target-start)*i/(times[i] - times[0 ]))