8
\$\begingroup\$

This is a continued discussion from here, and I use new a approach (bounding box/or envelop algorithm) to improve the algorithm efficiency. Any code bugs, algorithm time complexity improvement or general code advice is highly appreciated.

Major structure of my code:

  1. assign_box is used to build the bounding box or envelop
  2. find_min is finding min points among all candidate points for a given target point. It first uses a bounding box/envelop solution. If it cannot find an answer, it will use a brute force solution
  3. bruce_force is a brute force solution which is used to check the correctness of find_min
  4. distance is a utility method used to check the distance between two points

import sys
import random
from collections import defaultdict
def assign_box(box_map, points, k):
    x_min = min([p[0] for p in points])
    x_max = max([p[0] for p in points])
    y_min = min([p[1] for p in points])
    y_max = max([p[1] for p in points])
    x_distance = (x_max - x_min) / k
    y_distance = (y_max - y_min) / k
    for p in points:
        i = (p[0]-x_min)/x_distance
        j = (p[1]-y_min)/y_distance
        box_map[(i,j)].append(p)

    return (x_min, x_distance, y_min, y_distance)

def distance(p1, p2):
    return (p1[0]-p2[0]) ** 2 + (p1[1]-p2[1]) ** 2

def find_min(points, box_map, target_point, x_min, x_distance, y_min, y_distance):
    # try 9 neighbour first
    row = (target_point[0] - x_min) / x_distance
    col = (target_point[1] - y_min) / y_distance
    result = sys.maxint
    result_point = None
    for r in range(row-1, row+2):
        for c in range(col-1, col+2):
            if (r,c) in box_map:
                for p in box_map[(r,c)]:
                    d = distance(p, target_point)
                    if d < result:
                        result = d
                        result_point = p
    if result_point:
        return (result, result_point)
    else:
        # try brute force solution
        result = sys.maxint
        result_point = None
        for p in points:
            d = distance(p, target_point)
            if d < result:
                result = d
                result_point = p
        return (result, result_point)

def bruce_force(points, target_point):
    result = sys.maxint
    result_point = None
    for p in points:
        d = distance(p, target_point)
        if d < result:
            result = d
            result_point = p
    return (result, result_point)

if __name__ == "__main__":
    # key is a tuple, (box row index, box col index)
    # value is a list of points fall into it
    box_map = defaultdict(list)
    points = []
    for i in range(100):
        points.append((random.randint(0,10), random.randint(0,10)))
    x_min, x_distance, y_min, y_distance = assign_box(box_map, points, 5)
    target_point = (random.randint(0,10), random.randint(0,10))
    print 'target point, ', target_point
    print 'find min result, ', find_min(points, box_map, target_point, x_min, x_distance, y_min, y_distance)
    print 'brute force result, ',  bruce_force(points, target_point)
\$\endgroup\$
2
\$\begingroup\$

Mostly this looks good.

  1. assign_box is used to build the bounding box or envelope

I benchmarked the speed of assign_box. Please see https://github.com/jhanley634/testing-tools/blob/master/problem/bench/min_of_copied_list.py#L104..L109 . It turns out one can compute a pair of min's / max's slightly faster:

0.017s  scan_manually_with_if
0.019s  scan_with_two_copies
0.030s  assign_box
0.049s  scan_with_key
0.078s  scan_manually_with_min_max

The first two scan approaches are faster than your code.

  1. find_min

A comment of # try 8 neighbors first would be more natural than 9, since distance won't be less when row & column offsets are zero.

  1. bruce_force

Maybe this is a Bruce Lee joke. I recommend renaming it def brute_force.

  1. distance is a utility method ...

I recommend renaming it def distance_squared, as it clearly does not compute Euclidean distance. It's only used in comparisons, and N^2 is monotonic w.r.t. N, so there's no harm done. But you should say what you mean, and mean what you say.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.