python - 在表示数字的字符串集合中查找最接近的匹配项

Question

我有一个文本格式的日期时间排序列表。每个条目的格式是'2009-09-10T12:00:00'。

我想找到最接近目标的条目。条目数比我必须执行的搜索数要多得多。

我可以将每个条目更改为一个数字，然后按数字搜索(例如 these 方法)，但这似乎过于费力。

有没有比这更好的方法:

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

Answer 1

不推荐“复制和粘贴编码”(将 bisect 的源代码放入您的代码中)，因为它会带来各种成本(大量额外的源代码供您测试和维护，难以处理您复制的上游代码的升级等)；重用标准库模块的最佳方式就是导入并使用它们。

但是，将字典转换为有意义的可比较条目的一次遍历是 O(N)，这(即使遍历的每一步都很简单)最终将耗尽搜索本身的 O(log N) 时间。由于 bisect 不能像 sort 那样支持 key= 键提取器，解决这个难题的方法是什么——如何重用 bisect 通过导入和调用，没有初步的 O(N) 步骤...？

引用here ，解决方案是大卫惠勒的名言，“计算机科学中的所有问题都可以通过另一个间接层次来解决”。考虑例如......:

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 个条目的适度任务中，间接方法的性能也比“ key 提取传递”方法好三倍。由于我们比较的是 O(N) 与 O(log N)，间接方法的优势随着 N 的增加而无限制地增长。 (对于非常小的 N，由于间接性导致的更高的乘法常数使 key 提取方法更快，但这很快就被 big-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是十几行；鉴于这个比率，在大多数情况下(即排除绝对瓶颈)，我更喜欢更简单。重要的是要了解这两种方法以及它们之间的权衡，以确保做出明智的选择。