在表示数字的字符串集合中找到最接近的匹配
我有一个按时间顺序排列的日期时间列表，格式是'2009-09-10T12:00:00'。
我想找到一个最接近目标时间的条目。这个列表里的条目比我需要查找的次数要多得多。
我可以把每个条目转换成数字，然后用数字来查找（比如这些方法），但这样做似乎有点麻烦。
有没有比这样做更好的方法呢：
def mid(res, target):
#res is a list of entries, sorted by dt (dateTtime)
#each entry is a dict with a dt and some other info
n = len(res)
low = 0
high = n-1
# find the first res greater than target
while low < high:
mid = (low + high)/2
t = res[int(mid)]['dt']
if t < target:
low = mid + 1
else:
high = mid
# check if the prior value is closer
i = max(0, int(low)-1)
a = dttosecs(res[i]['dt'])
b = dttosecs(res[int(low)]['dt'])
t = dttosecs(target)
if abs(a-t) < abs(b-t):
return int(low-1)
else:
return int(low)
import time
def dttosecs(dt):
# string to seconds since the beginning
date,tim = dt.split('T')
y,m,d = date.split('-')
h,mn,s = tim.split(':')
y = int(y)
m = int(m)
d = int(d)
h = int(h)
mn = int(mn)
s = min(59,int(float(s)+0.5)) # round to neatest second
s = int(s)
secs = time.mktime((y,m,d,h,mn,s,0,0,-1))
return secs
4 个回答
你需要用到标准库里的 bisect模块。这个模块可以进行二分查找，帮你找到一个新值在已经排好序的列表中应该插入的位置。下面是一个例子，它会打印出 target 应该插入的地方：
from bisect import bisect
dates = ['2009-09-10T12:00:00', '2009-09-11T12:32:00', '2009-09-11T12:43:00']
target = '2009-09-11T12:40:00'
print bisect(dates, target)
接下来，你只需要比较插入点前后的两个元素，也就是 dates[i-1] 和 dates[i]，看看哪个更接近你的 target。
“复制粘贴代码”（把bisect的源代码直接放到你的代码里）是不推荐的，因为这样会带来很多后续问题（你需要测试和维护大量额外的源代码，处理你复制的上游代码的升级时会遇到困难等等）。最好的方法是直接导入标准库模块并使用它们。
不过，把字典转换成可以比较的条目需要O(N)的时间，虽然每一步都很简单，但最终会拖慢真正搜索的O(log N)时间。由于bisect不支持像sort那样的key=关键提取器，那么这个难题的解决方案是什么呢——如何通过导入和调用来重用bisect，而不需要一个前期的O(N)步骤呢……？
正如在这里引用的，解决方案在于大卫·惠勒的名言：“计算机科学中的所有问题都可以通过另一个间接层来解决”。比如考虑……：
import bisect
listofdicts = [
{'dt': '2009-%2.2d-%2.2dT12:00:00' % (m,d) }
for m in range(4,9) for d in range(1,30)
]
class Indexer(object):
def __init__(self, lod, key):
self.lod = lod
self.key = key
def __len__(self):
return len(self.lod)
def __getitem__(self, idx):
return self.lod[idx][self.key]
lookfor = listofdicts[len(listofdicts)//2]['dt']
def mid(res=listofdicts, target=lookfor):
keys = [r['dt'] for r in res]
return res[bisect.bisect_left(keys, target)]
def midi(res=listofdicts, target=lookfor):
wrap = Indexer(res, 'dt')
return res[bisect.bisect_left(wrap, target)]
if __name__ == '__main__':
print '%d dicts on the list' % len(listofdicts)
print 'Looking for', lookfor
print mid(), midi()
assert mid() == midi()
输出（先运行这个indexer.py来检查，然后用timeit测试两种方法）：
$ python indexer.py
145 dicts on the list
Looking for 2009-06-15T12:00:00
{'dt': '2009-06-15T12:00:00'} {'dt': '2009-06-15T12:00:00'}
$ python -mtimeit -s'import indexer' 'indexer.mid()'
10000 loops, best of 3: 27.2 usec per loop
$ python -mtimeit -s'import indexer' 'indexer.midi()'
100000 loops, best of 3: 9.43 usec per loop
如你所见，即使在一个只有145个条目的简单任务中，间接方法的性能也比“关键提取步骤”好三倍。因为我们在比较O(N)和O(log N)，随着N的增加，间接方法的优势会不断扩大。（对于非常小的N，由于间接方法的高倍常数，关键提取方法会更快，但很快就会被大O差异超越）。诚然，Indexer类是额外的代码——不过，它可以在所有按字典中某个条目排序的列表进行二分搜索的任务中重用，所以把它放在你的“工具箱”里，能带来不错的回报。
关于主要搜索循环就说到这里。对于将两个条目（目标下方和上方的条目）和目标转换为秒数的辅助任务，再次考虑一种更高重用的方法，即：
import time
adt = '2009-09-10T12:00:00'
def dttosecs(dt=adt):
# string to seconds since the beginning
date,tim = dt.split('T')
y,m,d = date.split('-')
h,mn,s = tim.split(':')
y = int(y)
m = int(m)
d = int(d)
h = int(h)
mn = int(mn)
s = min(59,int(float(s)+0.5)) # round to neatest second
s = int(s)
secs = time.mktime((y,m,d,h,mn,s,0,0,-1))
return secs
def simpler(dt=adt):
return time.mktime(time.strptime(dt, '%Y-%m-%dT%H:%M:%S'))
if __name__ == '__main__':
print adt, dttosecs(), simpler()
assert dttosecs() == simpler()
在这里，重用方法没有性能优势（实际上，dttosecs更快）——但无论你的字典列表有多少条目，你每次搜索只需要进行三次转换，所以这个性能问题是否重要还不太清楚。同时，使用simpler你只需写、测试和维护一行简单的代码，而dttosecs需要十几行；考虑到这个比例，在大多数情况下（即不考虑绝对瓶颈），我更倾向于使用simpler。重要的是要了解这两种方法及其之间的权衡，以确保做出明智的选择。