如何加快速度：搜索多个日期列表以查找最接近的匹配项。 [Python]

我有一个日期列表，master_time。对于master_time中的每个日期，我在四个其他日期列表中搜索最接近的匹配项; time1,time2,time3和time4。结果将附加到“最近匹配”列表中，稍后将用于连接包含来自不同数据源的时间序列信息的数据帧。（或许有初始问题的一个更好的办法，但是这是我来了这么远）如何加快速度：搜索多个日期列表以查找最接近的匹配项。 [Python]

要通过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一般都很陌生，所以我怀疑有几种方法可以简化它以使其更快。任何建议，非常感谢！

来源

2016-07-29 user5503831

考虑到您正在多次搜索每个时间列表，为什么不排序所有时间列表，然后进行二分搜索？这将显着降低算法的时间复杂度。 – James

@詹姆斯伟大的建议 - 我还没有完全得到它的完整工作，但它已经看起来更快。谢谢！ – user5503831

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 *日志（N）像詹姆斯提案），并采取小于2秒，以匹配1.000.000随机量2所列出数字

来源

2016-07-29 18:51:51 Cabu

如何加快速度：搜索多个日期列表以查找最接近的匹配项。 [Python]

回答

相关问题