Fast list search method/s?

Xjazz · March 2, 2012, 7:48am

Hi

So, a fast list search method/s is needed.

I try to locate the value’s ‘slot’ in the list. See sample list on below:

a = [-9.0, -5.7, -1.2, 0, 1.7, 5.4, 9.0]

Lets say, the value is 3.5. I can easily see, it’s between 4 an 5 list ‘slots’.

How to do this very fast with python?

Thanks

edit

-------------------------------------------------------------------------------------

You can see on below a speed test code, where I’m comparing a IUS- and i3-functions speed performance.

Both functions are providing a same result from same source data’s.

I try to optimize the i3 function as much as possible. Now it’s about 30 times faster, than IUS function.

Should/can I change the source data structure to be able to create faster function?

Any hints?

BTW
Forget to mention, the IUS-function requires a scipy and numpy installation.


from time import clock as c
from scipy.interpolate import InterpolatedUnivariateSpline

aoa = [-90.0, -45.0, -30.0, -20.0, 0.0, 20.0, 30.0, 45.0, 90.0]
vcl = [0.0,  -0.95,  -0.2,  -1.0,  0.0, 1.0,  0.2,  0.95, 0.0]

def IUS(x, y, v):
    return InterpolatedUnivariateSpline(x, y, k=1)(v)

def i3(x, y, v): 
    for i , val in enumerate(x):
        try:
            if (v &gt;= val) and (v &lt; aoa[i+1]):
                return y[i] + ((v - x[i])*(y[i+1]-y[i])) / (x[i+1]-x[i])
        except IndexError:
            return y[0]

#### -----------------------------
#### sweep test settings
vl = 90.0 # sweep test range -90 to 90 degrees aoa
av = 0.01 # sweep test step 

#### -----------------------------
t0 = c() # start time
v = -vl
while v &lt;= vl:
    IUS(aoa, vcl, v)
    v +=av
val1 =c() - t0 # cal time

#### -----------------------------
t0 = c() # start time
v = -vl
while v &lt;= vl:
    i3(aoa, vcl, v)
    v +=av
val2 = c() - t0 # cal time

#### -----------------------------
#### show results
print 'IUS time:',round(val1,3), 'seconds'
print 'i3 time:',round(val2,3), 'seconds'
print round(val1 / val2,1), 'x speed difference'

#### Test with single values
##v = 90.0
##print i3(aoa, vcl, v)
##print IUS(aoa, vcl, v)

Thanks again

sevi · March 2, 2012, 9:36am

Can you explain a little bit more, what the goal is ? Looks interesting, would like to know more about it.
I’m trying to figure out, what it does…

Monster · March 2, 2012, 10:28am

Quick search:
http://wiki.python.org/moin/PythonSpeed/PerformanceTips

I thought I read that the implementation of the dictionary access is quite efficient. Therefore it is used internal as well (to resolve names etc.).

BTW: a list of 6 values is not really a amount of test data.
Better test with 10000+

Xjazz · March 2, 2012, 11:40am

Hi

Sorry for the blur description. I try to improve a bit.

The IUS- and i3-function’s purpose is to provide a real time lift coefficient value versus dynamically changing angel of attack value.

On the picture on below you can see a coarse lift coefficient curve of wing with symmetrical profile.

On x-axis is the angle of attack in degrees and on y-axis is normalized lift coefficient values.
The x-axis data is stored to the aoa-list and y-axis data to the vcl-list.

The IUS- and i3-functions are making a linear interpolation between two connected points / lines.

Monster,
The test loops are testing each function with 18000 idivudual aoa values (0.01 degrees steps).
That will tell the story about performance in any language.

Thank you for the link.

As said, the example curve/data is pretty simple.
But…
For the simulation the curve could have about 11-17 points per - and + side of the aoa and mostly weighted to the first +30/-30 aoa part, because 99% of flight time, the plane will be inside of the normal flight envelope.

superflip · March 2, 2012, 6:01pm

To: Xjazz

dude your video is impressive…awesome

mb10 · March 3, 2012, 3:50am

It seems that your function is even faster than the scipy linear interpolation, which is the method closest to yours. Not to say about the extremely slow PiecewisePoly method.

Finally, I thought that a further, at least small, improvement could be achieved by precalculating the slopes, but surprisingly this is not the case: compared to your “original” i3 it is almost twice as slow on my PC. I cannot explain this, may be I did something wrong.

Below is a modified version of your code with the above mentioned tests.

# MODIFIED FROM Xjazz ORIGINAL CODE, march 3, 2012

from time import clock as c
from scipy.interpolate import InterpolatedUnivariateSpline
from scipy.interpolate.interpolate_wrapper import linear
from scipy.interpolate import PiecewisePolynomial
from numpy import zeros

aoa = [-90.0, -45.0, -30.0, -20.0, 0.0, 20.0, 30.0, 45.0, 90.0]
vcl = [0.0,  -0.95,  -0.2,  -1.0,  0.0, 1.0,  0.2,  0.95, 0.0]
ratios = zeros(len(vcl))

for i in range(len(vcl)-1):
    ratios[i] = (vcl[i+1]-vcl[i]) / (aoa[i+1]-aoa[i])

# piecewise polynomial:
vclL = [[0.0],  [-0.95],  [-0.2],  [-1.0],  [0.0], [1.0],  [0.2],  [0.95], [0.0]]
P = PiecewisePolynomial(aoa, vclL)

def IUS(x, y, v):
    return InterpolatedUnivariateSpline(x, y, k=1)(v)

##def interp1D(x, y, v):
##    return InterpolatedUnivariateSpline(x, y, k=1)(v)

def i3(x, y, v):
    for i , val in enumerate(x):
        try:
            if (v &gt;= val) and (v &lt; aoa[i+1]):
                return y[i] + ((v - x[i])*(y[i+1]-y[i])) / (x[i+1]-x[i])
        except IndexError:
            return y[0]

def i3_prestored(x, y, ratios, v):
    for i , val in enumerate(x):
        try:
            if (v &gt;= val) and (v &lt; aoa[i+1]):
                return y[i] + ratios[i]*(v - x[i])
        except IndexError:
            return y[0]

#### -----------------------------
#### sweep test settings
vl = 90.0 # sweep test range -90 to 90 degrees aoa
av = 0.01 # sweep test step

#### -----------------------------
t0 = c() # start time
v = -vl
while v &lt;= vl:
    IUS(aoa, vcl, v)
    v +=av
val1 =c() - t0 # cal time
print('IUS interp: ', IUS(aoa, vcl, v))
#### -----------------------------
t0 = c() # start time
v = -vl
while v &lt;= vl:
    i3(aoa, vcl, v)
    v +=av
val2 = c() - t0 # cal time
print('i3 interp:', i3(aoa, vcl, v))

#### -----------------------------
t0 = c() # start time
v = -vl
while v &lt;= vl:
    linear(aoa, vcl, v)
    v +=av
val3 = c() - t0 # cal time

#### -----------------------------

t0 = c() # start time
v = -vl
while v &lt;= vl:
    i3_prestored(aoa, vcl, ratios, v)
    v +=av
val4 = c() - t0 # cal time
#### -----------------------------

t0 = c() # start time
v = -vl
while v &lt;= vl:
    P(v)
    v +=av
val5 = c() - t0 # cal time
#### -----------------------------

print()
#### show results
print('Scipy IUS time:',round(val1,3), 'seconds')
print('i3 time:',round(val2,3), 'seconds')
print('Scipy linear time:',round(val3,3), 'seconds')
print('i3_prestored time:',round(val4,3), 'seconds')
print('Scipy pwPoly time:',round(val5,3), 'seconds')

print(round(val1 / val2,1), 'IUS/i3 speed ratio')

Moguri · March 3, 2012, 9:35am

You could try a list comprehension or map(), which would move the loop iteration to C.

Xjazz · March 5, 2012, 9:03am

Hi

Thank you for your feedback.

Moguri,
I’m don’t know I could use A list comprehension or map() methods in this case. Not experienced with those yet.

I made another version, which it a bit more simple and very slightly faster:


d_aoa = [0.0, 20.0, 30.0, 45.0, 90.0,-90.0, -45.0, -30.0, -20.0, 0.0, 0.0] # note extra zero
d_clp = [0.0, 1.0,  0.2,  0.95, 0.0,  0.0,  -0.95, -0.2,  -1.0,  0.0, 0.0]# note extra zero

def i4(x, y, v): # Linear interpolation. x & y dataset and v
    for i , val in enumerate(x):
        if (v &gt;= val) and (v &lt; x[i+1]):
            return y[i] + ((v - x[i])*(y[i+1]-y[i])) / (x[i+1]-x[i])

aoa = 4.345

print i4(d_aoa, d_clp, aoa)