确定与输入日期最接近的日期的算法

Question

我有一个Python程序，它使用来自数据库的历史数据，并允许用户选择输入日期。不过，数据库里并不是所有可能的日期都有，因为这些是金融数据。换句话说，如果用户输入“02/03/2014”（这是星期天），他在数据库里找不到任何记录，因为股市那天是关闭的。

这就导致了SQL的问题，因为当找不到记录时，SQL语句就会失败，用户需要不断调整日期，直到找到一个存在的记录。为了避免这种情况，我想建立一个算法，能够自动调整输入的日期，选择离原始输入最近的日期。例如，如果用户输入“02/03/2014”，那么最近的日期就是“03/03/2014”。

我想到了这样的一个思路，其中表MyData只包含日期值（我还在处理正确的语法，但这只是为了展示这个想法）：

con = lite.connect('C:/.../MyDatabase.db')
cur = con.cursor() 
cur.execute('SELECT * from MyDates')
rowsD= cur.fetchall()
data = []
for row in rowsD:
    data.append(rowsD[row])           

>>>data
['01/01/2010', '02/01/2010', .... '31/12/2013']

inputDate = '07/01/2010'
differences = []
for i in range(0, len(data)):
    differences.append(abs(data[i] - inputDate))

接下来，我在想：

• 从差值向量中获取最小值：mV = min(differences)
• 在列表data中找到对应的日期值

然而，这样做让我在内存上付出了两个代价：

1. 我需要加载整个数据库，而这个数据库非常大；
2. 我必须多次迭代（一次构建数据列表，然后是差值列表等等）。

有没有人有更好的主意来解决这个问题，或者知道其他的方法？

Answer 1

我建议你直接从数据库中获取一个日期小于给定日期的最大记录（这可以通过SQL来实现）。如果你在数据库的日期字段上加了索引，那么这个操作的效率可以达到O(log(n))。当然，这并不完全等同于“最接近”，但如果你再结合“一个大于给定日期的最小日期”，就能达到你的目的。

另外，如果你对数据的分布有个大概的了解，比如说每7天内都有一些数据，那么你可以把范围限制在[-3天, +3天]这样的小范围内。

把这两种方法结合起来，应该能让你的性能提升不少。

Answer 2

从数据库中查找比输入日期早的所有日期，然后找出这些日期中最大的一个。这就能得到离输入日期最近的那个早日期。

同样地，你可以查找比输入日期晚的所有日期，找出这些日期中最小的一个，这样就能得到离输入日期最近的晚日期。然后在这两个日期中选择你更喜欢的那个。

这些查询应该是高效的。

SELECT MAX(Date)
FROM MyDates
WHERE Date <= InputDate;