Calculate distance between every pair of points in 2D using parallel processing

user_13326823 0
Viewed 210

In my problem, there are multiple sets of points in the 2D space.
i.e.) 10 points in group 1, 10 points in group 2, 10 points in group 3.

I need to calculate all distances between the points in every group. i.e.)

distance (1,2,1,1): the distance between point 1 in group 1 and point 1 in group 2

distance (1,2,1,2): the distance between point 1 in group 1 and point 2 in group 2

distance (1,2,1,3): the distance between point 1 in group 1 and point 3 in group 2

....

distance (2,3,10,10): the distance between point 10 in group 2 and point 10 in group 3

The distance covers all points in all groups.
Currently, I used 4-four loops as below but it takes too much time.

distt = [[] for i in range(ball_number)]
for m in range(group_number-1):
    for n in range(m+1, group_number):
        for i in range(ball_number):
            for j in range(ball_number):
                    distt[i].insert(j, distance between point[i] and point[j])

One guy advised me something like...."use multiple threads (same numbers of the group) and class, and calculate all distances of a single group with one thread" but I cannot figure out how to do that.

Does anybody can help me for the fast calculation method with multithreading or any advise?

distance concurrency multithreading python loops
1 Answers

Assuming there are just 3 sets of points, you can create 3 processes.

These 3 processes will compute the distance between every pair of points betwen sets (1,2), (2,3) and (1,3) respectively.

In general, if there are n sets, then we can spawn a process pool with min(num_processor, n*(n-1) / 2) child processes to get maximum parallelism, where num_processor is the number of physical cores in the computer.

Not that we need multiprocessing rather than multithreading as this is a CPU bound operation and not an IO-bound one.

user_19253880
Related