Как ускорить это: поиск по нескольким спискам дат для поиска ближайшего соответствия. [Python]

Question

У меня есть один список дат, master_time. Для каждой даты в master_time, я ищу ближайший матч в четырех других списках дат; time1, time2, time3, и time4. Результаты добавляются в списки «closestmatch», которые позже будут использоваться для объединения данных, содержащих информацию о таймсерах из разных источников данных. (Может быть, есть лучший подход к исходной задаче, но это то, что я придумал до сих пор)

Для поиска в 4 списков, я создал следующий (довольно громоздкий) цикл:

master_time = [some list of dates...] 
time1 = [some other list of dates...] 
time2 = [some other list of dates...] 
time3 = [some other list of dates...] 
time4 = [some other list of dates...] 

closest2=[];closest4=[];closest5=[];closest6=[] 

for i in master_time: 
    index_time=i 
    closestTimestamp1=min(time1, key=lambda d: abs(d - index_time)) 
    closestTimestamp2=min(time2, key=lambda d: abs(d - index_time)) 
    closestTimestamp3=min(time3, key=lambda d: abs(d - index_time)) 
    closestTimestamp4=min(time4, key=lambda d: abs(d - index_time)) 
    closest1.append(str(closestTimestamp1)) 
    closest2.append(str(closestTimestamp2)) 
    closest3.append(str(closestTimestamp3)) 
    closest4.append(str(closestTimestamp4)) 
    print str(i) 

Этот цикл занимает ~ 5 секунд на итерацию (т.е. слишком медленный). Я довольно новичок в Python в целом, поэтому я подозреваю, что есть несколько способов упростить это, чтобы сделать его быстрее. Любые предложения приветствуются!

Answer 1

import random 

def find_best_match(master_list, secondary_list): 
    master_list.sort() 
    secondary_list.sort() 

    secondary_len = len(secondary_list) - 1 
    secondary_index = 0 

    closests = [] 
    for master_value in master_list: 
     while True: 
      delta_current = abs(master_value - secondary_list[secondary_index]) 
      if secondary_index == secondary_len: 
       break 
      delta_next = abs(master_value - secondary_list[secondary_index+1]) 
      if delta_current < delta_next: 
       break 
      secondary_index += 1 

     closests.append(secondary_list[secondary_index]) 

    return closests 


master_list = [random.random() * 10000 for _ in range(1000000)] 
list_1 = [random.random() * 10000 for _ in range(1000000)] 
list_2 = [random.random() * 10000 for _ in range(1000000)] 

closests_1 = find_best_match(master_list, list_1) 
closests_2 = find_best_match(master_list, list_2) 

Этот алгоритм имеет бегущую сложность N (а не N^2, как ваш алгоритм или N * Log (N), как Джеймс предложения) и занимает менее 2 секунд, чтобы соответствовать 2 списков 1.000.000 Randoms numbers