Najbardziej efektywny sposób na znalezienie sąsiadów na liście

Question

Mam listę długości 2016, ale tylko 242 zawiera dane, reszta jest ustawiona na Brak. Moim celem jest interpolacja między wartościami, aby wypełnić wszystkie luki prostą formą IDW (odwrotna ważona odległość). więc zadaniem mojego skryptu jest:

• iteracyjne nad wszystkich elementów myList
• Jeśli myList zawiera wartość (czyli nie None), wystarczy skopiować go
• Jeśli znajdziesz " Brak "w myList, znajdź pozycję/wartość sąsiada lewego i prawego, obliczając odległość do wszystkich elementów w myList
• Oblicz wartość interpolowaną dla luki od obu sąsiadów (im dalej są one oddalone, tym mniejszą wagę będą uzyskiwać)

Załóżmy, że mamy mniejszą listę zaledwie 14 egzemplarze (5 ważnych jedynek):

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] 

robie, że dla wielu, wielu zestawów danych. Okazało się, że ta metoda zajmuje około 0,59 s na zestaw danych. Martwi mnie fakt, że moja lista jest uporządkowana, ale będę potrzebować tylko 2 wartości. Tak więc 99% odległości są obliczane na nic. Które doprowadziły mnie do próby dwa: stop iteracji po ij staje się ujemny, bo wtedy oczywiście to wpadł najbliższych wartości:

Więc zamiast listy zrozumieniem:

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

robię właściwą dla pętli który rzuciłem po odległości przejść do zera, a tym samym stają się większe ponownie:

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

Dzięki tej metodzie udało mi się zejść do 0.38sec na zbiorze danych. Podczas iteracji wszystkich elementów w myList, ta druga metoda jest szybka na początku (element jest trafiony po 2., 3., 4., ... pętli i kończy natychmiast), ale nie ma poprawy dla ostatnich elementów, ponieważ iteracja zawsze się rozpoczyna przy j = 0.

Zastanawiam się, czy można wymyślić jakiś szybszy sposób na znalezienie dwóch sąsiadów określonej liczby w zbiorze danych, bez konieczności sprawdzania WSZYSTKICH odległości i przyjmowania tylko największej liczby ujemnych i małych pozytywnych.

Ponadto, jestem całkiem nowy dla Pythona, więc daj mi znać, jeśli znajdziesz inne nie-pytonowe wyrażenia w moim skrypcie. Dziękuję bardzo!

Answer 1

UPDATE: Oto jak to zrobić z 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. ] 

Original post:

Jak inni już zaproponował swoje najlepiej wyłączyć z pomocą niektórych interpolacji już wdrożonego w numpy lub pandach.

Jednak dla kompletności oto aa szybkie rozwiązanie wymyśliłem:

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] 

Proponuję użyć tego tylko do nauki lub do prostych przypadkach, ponieważ nie obsługuje przypadki, gdy masz list rozpoczynający lub kończący None