Il modo più efficace per trovare i vicini nell'elenco

Question

Ho una lista di lunghezza 2016, ma solo 242 contengono dati, il resto è impostato su Nessuno. Il mio obiettivo è quello di interpolare tra i valori per colmare tutte le lacune con una semplice forma di IDW (ponderazione inversa della distanza). Quindi il compito del mio script è:

• iterare su tutte le voci di myList
• Se il myList contiene un valore (cioè non Nessuno), basta copiarlo
• Se si trova un " Nessuno "nella lista, ottenere la posizione/il valore del vicino sinistro e destro calcolando la distanza da tutti gli elementi in myList
• Calcolare un valore interpolato per il divario da entrambi i vicini (più sono lontani, minore sarà il peso che avranno)

Supponiamo di avere una lista più piccola di soli 14 articoli (5 quelli validi):

myList = [26, None, None, None, 31, None, None, 58, None, 42, None, None, None, 79] 
resultList = [None] * len(myList) 

for i in range(len(myList): 
    if not myList[i] is None: 
     resultList[i] = myList[i] 
    else: 
     distance = [i - j for j in range(len(myList)) if not myList[j] is None] 
     neighbors = min([n for n in dist if n>0]), max([n for n in dist if n<0]) 
     # rest of the interpolation (not important for my question): 
     neighbors_c = [(1/float(n))**2 for n in neighbors] 
     c_sum = sum(neighbors_c) 
     neighbors_c = [n/c_sum for n in neighbors_c] 
     resultList = myList[i-neighbors[0]]*neighbors_c[0] + myList[i-neighbors[1]]*neighbors_c[1] 

che sto facendo che per molti molti insiemi di dati. Ho scoperto che questo metodo richiede circa 0,59 secondi per set di dati. Quello che mi infastidisce è il fatto che la mia lista è tutto in ordine, ma mi basteranno solo 2 valori. Quindi il 99% delle distanze è calcolato per niente. Questo mi ha portato a tentare due: fermare l'iterazione dopo ij diventa negativo, perché poi, ovviamente, ha incontrato i valori più vicini:

così invece della lista di comprensione:

distance = [i - j for j in range(len(myList)) if not myList[j] is None] 

faccio un corretto ciclo for che ho lasciato dopo distanze passano zero e quindi diventano più grandi ancora:

dist = [] 
for j in range(len(myList)): 
    if not myList[j] is None: 
     dist.append(i-j) 
     if i-j < 0: break 

Con questo metodo ho potuto scendere a 0.38sec per set di dati. Quando si itera su tutti gli elementi in myList, questo secondo metodo è rapido all'inizio (l'elemento viene colpito dopo il 2 °, 3 °, 4 ° ... e si chiude immediatamente), ma non c'è alcun miglioramento per gli ultimi elementi, poiché l'iterazione inizia sempre a j = 0.

Mi chiedo se riesci a pensare a un modo più rapido per trovare i due vicini di un numero specifico in un set di dati, senza dover controllare TUTTE le distanze e solo prendendo il più grande negativo e piccolo positivo.

Inoltre, sono abbastanza nuovo per Python, quindi per favore fatemi sapere se trovate altre espressioni non-pythonic nel mio script. Grazie mille!

Answer 1

UPDATE: Ecco come farlo con NumPy interp:

import numpy as np 

myList = [26, None, None, None, 31, None, None, 58, None, 42, None, None, None, 79] 

values = [(i, val) for i, val in enumerate(myList) if val is not None] 

xp, fp = zip(*values) 

print(xp) # (0, 4, 7, 9, 13) 
print(fp) # (26, 31, 58, 42, 79) 

result = np.interp(np.arange(len(myList)), xp, fp) 
print(result) # [ 26. 27.25 28.5 29.75 31. 40. 49. 58. 50. 42. 51.25 60.5 69.75 79. ] 

originale del messaggio:

Come altri hanno già suggerito, il vostro essere meglio fuori con l'utilizzo di alcuni interpolazione già implementato in numpy o in panda.

Tuttavia, per completezza ecco aa soluzione rapida mi si avvicinò con:

myList = [26, None, None, None, 31, None, None, 58, None, 42, None, None, None, 79] 

resultList = [] 

# first lets split the list into sublists that group the numbers 
# and the Nones into groups 
for i, item in enumerate(myList): 
    if i == 0: 
     resultList.append([item]) 
    else: 
     if type(resultList[-1][-1]) == type(item): 
      resultList[-1].append(item) 
     else: 
      resultList.append([item]) 

print(resultList) # [[26], [None, None, None], [31], [None, None], [58], [None], [42], [None, None, None], [79]] 

# now lets interpolate the sublists that contain Nones 
for i, item in enumerate(resultList): 
    if item[0] is not None: 
     continue 

    # this is a bit problematic, what do we do if we have a None at the beginning or at the end? 
    if i == 0 or i + 1 == len(resultList): 
     continue 

    prev_item = resultList[i - 1][-1] 
    next_item = resultList[i + 1][0] 

    difference = next_item - prev_item 
    item_length = len(item) + 1 

    for j, none_item in enumerate(item): 
     item[j] = prev_item + float(j + 1)/item_length * difference 

# flatten the list back 
resultList = [item for sublist in resultList for item in sublist] 

print(resultList) # [26, 27.25, 28.5, 29.75, 31, 40.0, 49.0, 58, 50.0, 42, 51.25, 60.5, 69.75, 79] 

vi suggerisco di utilizzare questo solo per imparare o per i casi semplici in quanto non gestisce i casi in cui si hanno le liste che inizia o termina con None