Coding style
Your code is difficult to read because it is written very condensed.
There is a well-established coding style for Python, the
PEP8 coding style,
and conformance to that style can be checked online at
PEP8 online.
In your case it reports “missing space around operator” in almost every
code line, also “line too long” and “multiple statements on one line”
violations. As an example,
elif len(points)==3: return min(dist(points[0],points[1]),dist(points[0],points[2]),dist(points[1],points[2]))
is better written as
elif len(points) == 3:
return min(dist(points[0], points[1]),
dist(points[0], points[2]),
dist(points[1], points[2]))
Variable naming
Another aspect which makes the code difficult to understand is the
naming of variables. Here are some examples:
points_y = sorted(points, key= lambda z:z[1])
points.sort(key=lambda g:g[0])
The parameter names z
and g
seem to be arbitrary. Why are they different
at all if they both refer to a point? Similarly at
yleft = [t for t in points_y if t[0]<=points[ave-1][0]]
yright = [q for q in points_y if q[0]>=points[ave][0]]
Why t
and q
? I'd suggest point
or p
in all those places.
def min_dist(points,points_y):
Both parameters contain all points, just sorted differently (by x and y,
respectively). Why the asymmetry in the parameter names? I'd suggest
def min_dist(points_x, points_y):
here, plus a doc comment explaining the meaning of the parameters.
ave = (len(points)+1)//2
makes one think of “average” but is just half of the list length.
Some simplifications
import sys
is not needed. The inner parentheses in
return math.hypot((b[0]-a[0]),(b[1]-a[1]))
are not needed. The elif
in
elif len(points)==3:
can be replaced by an if
. The slicing in
d1 = min_dist(points[0:ave],yleft)
d2 = min_dist(points[ave:len(points)],yright)
can be simplified to
d1 = min_dist(points[:ave], yleft)
d2 = min_dist(points[ave:], yright)
Validate the input
The program aborts with RecursionError
or IndexError
if zero or
one point are passed to the function. You should validate the input
and throw an appropriate exception in those cases.
A possible problem
If points[ave-1][0] == points[ave][0]
(which means that more than one point
lies on the dividing vertical line) then elements from the point_y
list are assigned to both yleft
and yright
:
yleft = [t for t in points_y if t[0]<=points[ave-1][0]]
yright = [q for q in points_y if q[0]>=points[ave][0]]
which means that in the recursive calls
d1 = min_dist(points[0:ave],yleft)
d2 = min_dist(points[ave:len(points)],yright)
the second list is not necessarily a rearrangement of the first list anymore.
I haven't found an example where this leads to a wrong result, but it could
be an performance problem because “too large” lists are passed down the
recursion. As an extremal case, if all points have the same x-coordinate
then yleft
and yright
will always be the complete initial points_y
list.
Performance improvements
points[ave][0]]
is accessed multiple times, it might be advantageous to
assign that value to a variable once.
The initial value
d_=2*(10**18)
is a bit arbitrary, but actually not needed: In the following loop we are
only interested in points having a distance less than the previously
computed minimum distance in the left and right half:
d = min(d1, d2)
# ...
for i in range(len(arr_split) - 1):
for j in range(i+1, min(len(arr_split), i + 7)):
temp = dist(arr_split[i], arr_split[j])
if temp < d:
d = temp
return d
And while it is true that pairs of points having a distance less than d
are at most seven (or six?) indices apart, it seems to be more efficient
to leave the inner loop if the y-coordinates differ by d
or more:
for i in range(len(arr_split) - 1):
for j in range(i + 1, len(arr_split)):
if arr_split[j][1] - arr_split[i][1] >= d:
break
temp = dist(arr_split[i], arr_split[j])
if temp < d:
d = temp
return d
Further suggestions
Instead of storing the point coordinates a a tuple you could define a
custom class
class Point:
__slots__ = ('x', 'y')
def __init__(self, x, y):
self.x = x
self.y = y
so that you can access the x- and y-coordinates of a point with p.x
and p.y
instead of subscripting.