Try to Avoid for-loops for performance

[Phase1997]

Hey everyone! :)

I need some help to boost my performance.

I got a given volume, which is a 3d-matrix out of 0s and 1s, representing the voxels. I also got a List of points. For every voxel in the volume, I would like to know the distance to the closest point contained in the list. The following code can be very time-consuming.

Result_Distances = np.zeros((10,10,10))
Volume = np.ones((10,10,10)) # or any other 3d matrix with 1s or 0s
ListofPoints = [(2,3,2), (2,3,3) ,(2,6,4),(9,6,8)] # or other points

for index, voxel in np.ndenumerate(Volume):

    if voxel == 1:    

            for index2 in ListofPoints:
                distance = np.sqrt((index[0]-index2[0])**2+(index[1]-index2[1])**2+(index[2]-index2[2])**2)
                distances.append(distance)

            Result_Distances[index] = np.amin(distances)

I saved the Distances for each voxel of the Volume in a matrix with the same shape, so the same Indeces point in the two matrixes to the same corresponding point or distance. So in analogy, the expected result would be the Distance_matrix which has for each Voxel(x,y,z) in the Volume on the same element in the Distance-Matrix the Distanz to the closest Point (doesn't matter which point is the closest one)


This takes about 1 Minute to compute because my volume can be very big (>1000 voxels). My ListofPoints is smaller (about 100 points).

Is there a smart way I can avoid the time consuming for loops in this particular case? I also tried the map() function, but couldn't implement it in a way, so there is an improvement.

Thank you for your help!

[DeaD_EyE]

If I run your code, after importing numpy as np and adding distances as empty list, it runs very fast.

I change the code a little bit.

import math
import numpy as np



def calc_dists(volume, list_of_points):
    hypot = math.hypot
    distances = np.zeros(volume.shape)
    for index, voxel in np.ndenumerate(vol):
        if voxel == 1:
            for index2 in list_of_points:
                distance = hypot(
                    index[0] - index2[0],
                    index[1] - index2[1],
                    index[2] - index2[2],
                )
                distances[index] = distance
    return distances

 
shape = (100,100,100)
vol = np.ones(shape)
points = [(2,3,2), (2,3,3) ,(2,6,4),(9,6,8)]
result = calc_dists(vol, points)

print(result)

A shape of 100 x 100 x 100 consists of 1e6 elements.
This code takes also under 10 seconds.

[joe_momma]

@ deadeye ran your example with python 3.73 and got this error:

Traceback (most recent call last):
File "/home/pi/misc/forum_list_points.py", line 24, in <module>
result = calc_dists(vol, points)
File "/home/pi/misc/forum_list_points.py", line 15, in calc_dists
index[2] - index2[2],
TypeError: hypot() takes exactly 2 arguments (3 given)

hypot = math.hypot(x,y,\ ['\' marks the preceding arguments as positional only]
returns the euclidean distance, sqrt(x*x, y*y))

[DeaD_EyE]

Error:
TypeError: hypot() takes exactly 2 arguments (3 given)

The cause is following.
Before: https://docs.python.org/3.7/library/math...math.hypot
After: https://docs.python.org/3/library/math.html#math.hypot

math.hypot takes only two arguments before Python 3.8.
Since 3.8 you can use as much arguments you want.

To get around this problem, you could use hypot twice:

distance1 = hypot(
    index[0] - index2[0],
    index[1] - index2[1],
)
distance2 = hypot(
    distance1,
    index[2] - index2[2],
)

Or upgrade to the current Python verision 3.8.x.

[joe_momma]

@deadeye it's time to change you banner

My code examples are always for Python >=3.6.0

:)