Most efficient way to find neighbors in list
Question: I have a list of length 2016, but only 242 contain data, the rest is set to
None. My aim is to interpolate between the values to fill all gaps with a
simple form of IDW (inverse distance weighting). So the task of my script is:

  * Iterate over all items of myList
  * If the myList contains a value (that is **not** None), just copy it
  * If you find a "None" in myList, get position/value of the left and right neighbor by calculating the distance to all items in myList
  * Calculate an interpolated value for the gap from both neighbors (the farer they are away, the less weight they shall get)

Assume we have a smaller list of only 14 items (5 valid ones):

    
    
    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]
    

I am doing that for many many data sets. I found out that this method takes
about 0.59sec per data set. What bothers me is the fact that my list is all
sorted, but I will only need 2 values from it. So 99% of the distances are
calculated for nothing. That led me to attempt two: stop the iteration after
i-j becomes negative, because then obviously it ran into the closest values:

So instead of the list comprehension:

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

I do a proper for-loop which I quit after distances pass zero and thus become
larger again:

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

With this method I was able to get down to 0.38sec per data set. When
iterating over all items in myList, this second method is quick at the
beginning (item is hit after 2nd, 3rd, 4th, ... loop and quit immediately),
but there is no improvement for the last items, since iteration always starts
at j=0.

I wonder if you can think of any quicker way to find the two neighbors of a
specific number in a data set, without having to check ALL distances and only
taking the largest negative and smalles positive one.

Also, I'm quite new to python, so please let me know if you find other un-
pythonic expressions in my script. Thank you guys very much!


Answer: **UPDATE:** Here's how to do it with numpy
[`interp`](http://docs.scipy.org/doc/numpy/reference/generated/numpy.interp.html#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:**

As others have already suggested, your be best off with using some
interpolation already implemented in numpy or pandas.

However for completeness here's a a quick solution I came up with:

    
    
    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]
    

I suggest you use this only for learning or for simple cases as it does not
handle cases where you have lists beginning or ending with `None`

