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

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

import bisect

def mid(res, target):
    keys = [r['dt'] for r in res]
    return res[bisect.bisect_left(keys, target)]

Answer 2

您需要标准库中的bisect module。它将执行二进制搜索，并告诉您新值在已排序列表中的正确插入点。下面的示例将打印列表中插入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]和{}，看哪一个最接近你的{}。在

Answer 3

不建议使用“复制粘贴编码”（将bisect的源代码放入您的代码中），因为这样做会带来各种成本（大量额外的源代码供您测试和维护，在您复制的上游代码中处理升级的困难，等等）；重用标准库模块的最佳方法是简单地导入并使用它们。在

然而，要做一次将字典转换成有意义的可比较条目的步骤是O（N），它（尽管过程的每一步都很简单）最终会淹没搜索的O（logn）时间。既然bisect不能像sort那样支持key=密钥提取器，那么这个难题的解决方案是什么——如何通过导入和调用重用{}，而不需要一个初步的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，两种方式）：

^{pr2}$

正如您所看到的，即使在一个包含145个条目的普通任务中，间接方法的性能也可以比“密钥提取过程”方法好三倍。因为我们比较O（N）和O（logn），所以间接方法的优势随着N的增加而无限制地增长。（对于非常小的N，由于间接寻址而产生的更高的乘法常数使密钥提取的速度更快，但很快就被大O差所超越）。诚然，Indexer类是额外的代码——但是，它可以在所有二进制搜索任务中重用，这些任务是按每个dict中的一个条目排序的dict列表，因此将它放在“container utilities back of tricks”中可以获得很好的投资回报。在

主搜索循环到此为止。对于将两个条目（目标正下方和正上方的条目）和目标转换为秒数的次要任务，请再次考虑更高的重用方法，即：

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更快），但是，无论dict列表中有多少条目，每次搜索只需要执行三次转换，因此还不清楚这个性能问题是否有关联。同时，使用simpler你只需要编写、测试和维护一行简单的代码，而dttosecs就是十几行；鉴于这个比率，在大多数情况下（即排除绝对瓶颈），我更喜欢simpler。重要的是要意识到这两种方法以及它们之间的权衡，以确保做出明智的选择。在