So beschleunigen Sie das: Suchen Sie in mehreren Datumslisten nach der besten Übereinstimmung. [Python]

Question

Ich habe eine Liste von Daten, master_time. Für jedes Datum in master_time suche ich nach dem nächsten Treffer in vier anderen Datumslisten; time1, time2, time3 und time4. Die Ergebnisse werden an "engmatchmatch" -Listen angefügt, die später verwendet werden, um Datenrahmen zu verbinden, die Zeitreiheninformationen aus verschiedenen Datenquellen enthalten. (Vielleicht gibt es eine bessere Annäherung an das ursprüngliche Problem, aber das ist, was ich mit so weit gekommen sind)

durch die 4-Listen zu suchen, ich habe folgende (ziemlich sperrig) Schleife erstellt:

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) 

Diese Schleife dauert ~ 5 Sekunden pro Iteration (dh viel zu langsam). Ich bin ziemlich neu bei Python im Allgemeinen, also vermute ich, dass es einige Möglichkeiten gibt, wie ich das rationalisieren kann, um es schneller zu machen. Irgendwelche Vorschläge werden sehr geschätzt!

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) 

Dieser Algorithmus hat eine Lauf Komplexität von N (und nicht die N^2 wie Ihr Algorithmus oder N * log (N) wie James Vorschlag) und nehmen weniger als 2 Sekunden 2 Listen von 1.000.000 randoms übereinstimmen Zahlen