need help optimizing a geo algorithm using a map() operation, lists, floats and some validation.

Question

hi there.

Im doing som route(geo) calculations. I need to sort out some routes going in the "wrong" direction... all rides have "routes" and all routes consist of a lot of steps on the route.... each step has a lat. and a lng. pair. I hope this makes sense?

This is the way i do it now, and it works... however... im performing this operation on many(!) rides..routes...coordinate-pairs, so i could use a little speed-up in my code.

for ride in initial_rides:  
steps = ride.route.steps.all()  
    for step in steps:  
        if lat_min < step.latitude< lat_max and lng_min< step.longitude< lng_max:  
            approved_rides.append(ride)  
            break  

I better admit already that i'm no super programmer :)

i have tried construction something like this(without any luck):

for i in ride:  
    number  = sum(itertools.ifilter(lambda x: lat_min< x.latitude< lat_max and lng_min< x.longitude< lng_max, ride.route.steps.all()))  
    if number >= 1:  
        approved_rides.append(ride)  

tried to combine lambda and ifilter however i get an error saying operator doesn't support types "int" and "step"... Am i doing something wrong?

should i be using list comprehensions?? map()?? or something else?

i have read through http://www.python.org/doc/essays/list2str.html without any luck.

any help is greatly appreciated. thank you, and good day :)

Peter

Answer 1

To speed this up you should probably be using a better algorithm instead of trying all possible solutions. A* is a classic heuristic that could work on your problem.

You can try a comprehension like

approved_rides = [ride for ride in initial_rides if any(
          (lat_min < step.latitude< lat_max and \
           lng_min< step.longitude< lng_max) for step in ride.route.steps.all())]

which is your first code block as a oneliner.

If you can please give me a number how much faster it is, I'm interested :-)

Answer 2

The reason for the error is that you are calling sum on a list of things that you can't sum, namely, ride.route.steps.all(). I assume that gives list of steps; what were you intending to do by summing them?

You can count the number of elements in a list with len.

I think you are trying to do the following:

key = lambda x: lat_min< x.latitude< lat_max and lng_min< x.longitude< lng_max
approved_rides = [ ride for ride in rides if any( map( key, ride.route.steps.all( ) ) ) ]

That will make approved_rides a list of the rides any of whose ride.roude.steps.all( ) satisfies key.