optimization of filtering a large data array

Question

I am currently trying to improve my python skills by solving some example-problems. One of them is about checking if a gridpoint is located behind a barrier. Output is the number of all gridpoints that are not behind a barrier. The given Hint is to calculate the angle of the direction to the point and compare it with the angle of the left and right side of the barrier. My code works and gives correct results however for large grids (1000x1000) it is very slow, so I was wondering if there are ways to make the code faster.

The part that takes the longest is the checking if a point is behind an Obstacle, so I will only include this part of the Code in here. If you need the rest of the code as well, I am happy to include it :)

import math
import numpy as np


def CheckIfObstacle(point, Obstacle):

    for obs in Obstacle:

        # condition for a point being behind a barrier that is on positive side of Grid
        if obs[0]>0 and point[0] >= obs[0] and (obs[1] >= point[1] >= obs[2]):
                return True

        # condition for a point being behind a barrier that is on negative side of Grid
        elif obs[0]<0 and point[0] <=obs[0] and (obs[1]>= point[1]>= obs[2]):
                return True

    return False    


Obstacle = [] #[(y1,angle_big1,angle_small1),(y2,angle_big2,angle_small2),...]
for i in range(2,nObs+2):
   some code that puts data in Obstacle
    
Grid = calcGrid(S)  # [(y1,angle1),(y2,angle2),...]

count = 0
p=0
for point in Grid:
    if p%10000==0:
        print(round(p/len(Grid)*100,3),'%')
    p+=1
    if CheckIfObstacle(point, Obstacle) ==False:
        count +=1

print(count)

This is the fastes Version of all of my versions. The 1000x1000 Grid takes around 15min I think, but now I have an even bigger Grid, and it ran for an hour and was at 5% or so. If anyone has any ideas on how to improve the code, I would be happy about some feedback.

Thanks in advance!

score 1 · Answer 1 · answered Aug 06 '21 at 07:17

I suggest that you split the equation into 16 different programs that run separately if you are using cloud software. If not, Have the smaller equations run consecutively. That way you don’t have a massive program that has to render all at once.

eroot163pi · Answer 2 · 2021-08-06T07:24:29.897

Using numba, you can compile CheckIfObstacle and make it very fast and memory efficient. In my case you can say I needed 49000x12000 grid. So using numpy with numba was life saver for me and you can see speed comparisons using numba vs best possible using numpy. Or you can use Cython which will be bit complicated and parallelism is difficult compared to numba

Adding numba jit decorator at top of function including proper type specification. This one just an example and not storing calculation, but it is good idea to add numba to your list of optimizations

@nb.njit((nb.float64[:], nb.float64[:, :]), parallel=True)
def CheckIfObstacle(point, Obstacle):

    for i in nb.prange(Obstacle):
        obs = Obstacle[i]
        # condition for a point being behind a barrier that is on positive side of Grid
        if obs[0]>0 and point[0] >= obs[0] and (obs[1] >= point[1] >= obs[2]):
            return True

        # condition for a point being behind a barrier that is on negative side of Grid
        elif obs[0]<0 and point[0] <=obs[0] and (obs[1]>= point[1]>= obs[2]):
            return True

    return False

I had similar problem, look for performance and implementation Why are np.hypot and np.subtract.outer very fast?

optimization of filtering a large data array

2 Answers2