For each element of the list find closest date from a different list

Viewed 631

I have 2 lists:

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

For every ticker in l1 I want to find the closest element from l2 after it, so the output should be

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

The right way seems to be to explicitely iterate in parallel over both lists in reverse order, but I was hoping for a more "pythonic" solution..

EDIT: I do want an optimal complexity solution, which (assuming the lists are sorted), I think is O(max(len(l1), len(l2))).

4 Answers

You could use a list comprehension in combination with min method by passing a lambda expression.

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]

Output

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

If you want a more efficient solution you can write your own insert sort algorithm.

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]

If your lists are long, it can be worth pre-processing l2 in order to be able to use bisect to find the closest date. Then, finding the closest date to a date in l1 will be O(log(len(l2)) instead of O(len(l2)) with 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']

To address your last comment, here is another solution using iterators and generators, that goes over l1 and only the necessary part of the start of 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

Some tests:

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

Assuming, as in your example, dates are in chronological order, you can take advantage of the fact your lists are sorted. For example, if you are happy to use a 3rd party library, you can use NumPy via np.searchsorted, a faster version of bisect from the standard library:

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

You can sort with a key function that calculates the time deltas between the two dates.

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

This outputs:

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

Note that the date format string should be %m/%d/%Y, for month, day and year, respectively.

Related