对于列表中的每个元素，从另一个列表中找到最接近的日期。

Question

对于列表中的每个元素，从另一个列表中找到最接近的日期。

4

I have 2 lists:

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)))。

- LazyCat

4个回答

3

如果你的列表很长，预处理l2可以值得使用bisect来查找最接近的日期。然后，在l1中查找最接近的日期将是O(log(len(l2)))，而不是使用min的O(len(l2))。

from datetime import datetime
from bisect import bisect

l1 = [ '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 datetime
from itertools import tee, islice, zip_longest

def closest_dates(l1, l2):
    """
    For each date in l1, finds the closest date in l2,
    assuming the lists are already sorted.
    """
    dates1 = (datetime.strptime(d, '%m/%d/%Y') for d in l1)
    dates2 = (datetime.strptime(d, '%m/%d/%Y') for d in l2)
    dinf, dsup = tee(dates2)
    enum_middles = enumerate(d1 + (d2-d1)/2 
                             for d1, d2 in zip_longest(dinf, islice(dsup, 1, None), 
                                                       fillvalue=datetime.max))
    out = []
    index, middle = next(enum_middles)

    for d in dates1:
        while d > middle:
            index, middle = next(enum_middles)
        out.append(l2[index])

    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']  # only one date, it's always the closest
print(closest_dates(l1, l2))
# ['11/11/2018', '11/11/2018', '11/11/2018', '11/11/2018']

- Thierry Lathuille

在我看来，一个排序后的解决方案应该被接受。+1 - jpp

@LazyCat 是的，就是这样。 - Thierry Lathuille

https://dev59.com/JK_la4cB1Zd3GeqPuowb#53121543?noredirect=1#comment93139245_53121091 - LazyCat

谢谢，是的，你的最新版本基本上就是我所拥有的。 - LazyCat

1

假设像你的例子一样，日期是按时间顺序排列的，你可以利用列表已经排序的事实。例如，如果你愿意使用第三方库，你可以通过np.searchsorted使用NumPy，这是标准库中bisect的更快版本：

import numpy as np
from datetime import datetime

l1 = [ '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']

- jpp

0

您可以使用一个关键函数进行排序，该函数计算两个日期之间的时间差。

from datetime import datetime
print([min(l2, key=lambda s: abs((datetime.strptime(s, '%m/%d/%Y') - datetime.strptime(d, '%m/%d/%Y')))) for d in l1])

这将输出:

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

请注意，date format string 应分别为月、日和年，格式应为 %m/%d/%Y。

- blhsing

https://dev59.com/JK_la4cB1Zd3GeqPuowb#dPAkoYgBc1ULPQZFq-70 - LazyCat

你所指的答案比我几乎完全相同的答案早了1分钟发布，但它完全错误地得到了日期格式字符串，然后我在我的注释中指出了这一点。那个答案的作者看到了我的注释并纠正了他的代码。你可以查看它的编辑历史以获取详细信息。 - blhsing

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Mihai Alexandru-Ionut · Accepted Answer

你可以使用lambda表达式和min方法结合使用的列表推导式。

from datetime import datetime
l1 = [ '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']

如果你想要一个更高效的解决方案，你可以编写自己的插入排序算法。

def insertSortIndexItem(lst, item_to_insert):
  index = 0
  while index < len(lst) and item_to_insert > lst[index]:
    index = index + 1
  return lst[index]

l2 = sorted(l2, key=lambda d: datetime.strptime(d, "%m/%d/%Y"))
l1 = [insertSortIndexItem(l2, item) for item in l1]