对于列表的每个元素，从不同的列表中找到最接近的日期

Question

我有 2 个列表：

l1 = [ '09/12/2017', '10/24/2017' ]

l2 = [ '09/15/2017', '10/26/2017', '12/22/2017' ]

对于 l1 中的每个股票代码，我想在它之后从 l2 中找到最接近的元素，所以输出应该是

l3 = [ '09/15/2017', '10/26/2017' ]

正确的方法似乎是以相反的顺序在两个列表上并行迭代，但我希望有一个更“pythonic”的解决方案..

编辑：我确实想要一个最佳复杂度解决方案，它（假设列表已排序），我认为是 O(max(len(l1), len(l2)))。

Answer 1

您可以通过传递表达式将列表理解与min方法结合使用。lambdafrom datetime import datetimel1 = [ '09/12/2017', '10/24/2017' ]l2 = [ '09/15/2017', '10/26/2017', '12/22/2017' ]l1 = [min(l2, key=lambda d: abs(datetime.strptime(d, "%m/%d/%Y") - datetime.strptime(item, "%m/%d/%Y"))) for item in l1]输出['09/15/2017', '10/26/2017']如果您想要更有效的解决方案，您可以编写自己的insert排序算法。def insertSortIndexItem(lst, item_to_insert):&nbsp; index = 0&nbsp; while index < len(lst) and item_to_insert > lst[index]:&nbsp; &nbsp; index = index + 1&nbsp; return lst[index]l2 = sorted(l2, key=lambda d: datetime.strptime(d, "%m/%d/%Y"))l1 = [insertSortIndexItem(l2, item) for item in l1]

Answer 2

如果您的列表很长，则值得进行预处理l2，以便能够使用它bisect来查找最近的日期。然后，找到最接近日期的日期l1将是 O(log(len(l2)) 而不是 O(len(l2)) min。from datetime import datetimefrom bisect import bisectl1 = [ '09/12/2017', '10/24/2017' ]l2 = [ '09/15/2017', '10/26/2017', '12/22/2017' ]dates = sorted(map(lambda d: datetime.strptime(d, '%m/%d/%Y'), l2))middle_dates = [dates[i] + (dates[i+1]-dates[i])/2 for i in range(len(dates)-1)]out = [l2[bisect(middle_dates, datetime.strptime(d,'%m/%d/%Y'))] for d in l1]print(out)# ['09/15/2017', '10/26/2017']为了解决您的最后一条评论，这是使用迭代器和生成器的另一种解决方案，它l1仅在 开始的必要部分结束l2：from datetime import datetimefrom itertools import tee, islice, zip_longestdef closest_dates(l1, l2):&nbsp; &nbsp; """&nbsp; &nbsp; For each date in l1, finds the closest date in l2,&nbsp; &nbsp; assuming the lists are already sorted.&nbsp; &nbsp; """&nbsp; &nbsp; dates1 = (datetime.strptime(d, '%m/%d/%Y') for d in l1)&nbsp; &nbsp; dates2 = (datetime.strptime(d, '%m/%d/%Y') for d in l2)&nbsp; &nbsp; dinf, dsup = tee(dates2)&nbsp; &nbsp; enum_middles = enumerate(d1 + (d2-d1)/2&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;for d1, d2 in zip_longest(dinf, islice(dsup, 1, None),&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;fillvalue=datetime.max))&nbsp; &nbsp; out = []&nbsp; &nbsp; index, middle = next(enum_middles)&nbsp; &nbsp; for d in dates1:&nbsp; &nbsp; &nbsp; &nbsp; while d > middle:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; index, middle = next(enum_middles)&nbsp; &nbsp; &nbsp; &nbsp; out.append(l2[index])&nbsp; &nbsp; return out一些测试：l1 = [ '09/12/2017', '10/24/2017', '12/11/2017', '01/04/2018' ]l2 = [ '09/15/2017', '10/26/2017', '12/22/2017' ]print(closest_dates(l1, l2))# ['09/15/2017', '10/26/2017', '12/22/2017', '12/22/2017']l2 = ['11/11/2018']&nbsp; # only one date, it's always the closestprint(closest_dates(l1, l2))# ['11/11/2018', '11/11/2018', '11/11/2018', '11/11/2018']

Answer 3

假设，如您的示例，日期按时间顺序排列，您可以利用列表已排序的事实。例如，如果您乐于使用 3rd 方库，则可以使用 NumPy via np.searchsorted，这bisect是标准库中更快的版本：import numpy as npfrom datetime import datetimel1 = [ '09/12/2017', '10/24/2017' ]l2 = [ '09/15/2017', '10/26/2017', '12/22/2017' ]l1_dt = [datetime.strptime(i, '%d/%M/%Y') for i in l1]l2_dt = [datetime.strptime(i, '%d/%M/%Y') for i in l2]res = list(map(l2.__getitem__, np.searchsorted(l2_dt, l1_dt)))# ['09/15/2017', '10/26/2017']