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

Question

背景

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

这些数据集包含我用形象化三个内部列表:time,height和dataset.我的程序用时间 x 高度绘制数据,另外用户可以选择在图形的区域周围绘制形状,可以提取到整个不同的图.

困难的部分是,当我想从形状中提取数据时,形状顶点是由绘图计算的真实坐标,而不是舍入到我的time数组中的最近点.这是一个在我的程序中绑定区域的形状示例

虽然X1可以代表坐标(2007-06-12 03:42:20.070901+00:00, 5.2345)根据matplotlib,最接近协调现有的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.排序和2.增加一步,我认为这个问题应该能够及时解决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列)更接近实际索引(第2列).请注意,dt估计的准确性基本上与跨度中的位数成正比.你能做的最好的事情就是在起点和终点使用时间,但从你的问题陈述来看,这似乎很难; 但如果不是,它将给出您的时间间隔的最准确估计.请注意,在这里,为了清楚起见,我通过使我的时间间隔记录非常合理来夸大缺乏准确性,但一般来说,你的跨度中的每个10的幂都会使你的准确度增加相同的量.

作为最后一点的一个例子,如果我通过改变coursing线来减少时间值的过程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]))

Answer 2

您所描述的几乎就是插值搜索.它的工作方式与二进制搜索非常相似,但它不是选择中间元素,而是假设分布接近均匀并猜测大致位置.

维基百科链接包含C++实现.