Для каждого элемента списка найдите ближайшую дату из другого списка

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' ]

Правильный способ, по-видимому, заключается в явной итерации параллельно по обоим спискам в обратном порядке, но я надеялся на более "питонное" решение ..

РЕДАКТИРОВАТЬ: я хочу оптимальное решение сложности, которое (если списки отсортированы), я думаю, O (max (len (l1), len (l2))).

Answer 1

Если ваши списки длинные, может быть стоит предварительно обработать l2, чтобы можно было использовать bisect, чтобы найти ближайшую дату. Тогда, нахождение ближайшей даты к дате в l1 будет O (log (len (l2)) вместо O (len (l2)) с min.

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']

Answer 2

Вы можете выполнить сортировку с помощью ключевой функции, которая вычисляет временные разницы между двумя датами.

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']

Обратите внимание, что строка формата даты должна быть %m/%d/%Y для месяца, дня и года соответственно.

Answer 3

Предполагая, что, как в вашем примере, даты расположены в хронологическом порядке, вы можете воспользоваться тем фактом, что ваши списки отсортированы. Например, если вы счастливы использовать стороннюю библиотеку, вы можете использовать NumPy через np.searchsorted, более быструю версию 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']

Answer 4

Вы можете использовать понимание списка в сочетании с методом min, передав lambda выражение .

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']

Если вам нужно более эффективное решение, вы можете написать собственный алгоритм сортировки insert.

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]