There are a number of approaches to solve this problem.
Yours is one of them, and to obtain the result in the form of tuples it is sufficient to convert the resulting array back to list, with a combination of tuple() and np.ndarray.tolist().
As far as the fastest execution is concerned, it all boils down to the size of the input.
Here I provide some implementations (some similar to the other answers) as well as some timing:
import numpy as np
def p_dist_np(x, y, p=2):
if p % 2:
return np.sum(np.abs(x - y) ** p, axis=-1)
else:
return np.sum((x - y) ** p, axis=-1)
def minmax_dist_np(x0, xs, d_func=p_dist_np):
x0 = np.array(x0)
xs = np.array(xs)
dists = d_func(x0, xs)
min_i = np.argmin(dists)
max_i = np.argmax(dists)
return tuple(xs[min_i].tolist()), tuple(xs[max_i].tolist())
import numpy as np
import numba as nb
@nb.njit
def p_dist_nb(x, y, p=2):
if p % 2:
return np.sum(np.abs(x - y) ** p)
else:
return np.sum((x - y) ** p)
@nb.njit
def _minmax_dist_nb(x0, xs, d_func=p_dist_nb):
min_i = max_i = 0
min_d = max_d = d_func(x0, xs[min_i])
for i, x in enumerate(xs[1:], 1):
d = d_func(x0, x)
if d < min_d:
min_d = d
min_i = i
elif d > max_d:
max_d = d
max_i = i
return min_i, max_i
def minmax_dist_nb(x0, xs, d_func=p_dist_nb):
x0 = np.array(x0)
xs = np.array(xs)
min_i, max_i = _minmax_dist_nb(x0, xs, d_func=d_func)
return tuple(xs[min_i].tolist()), tuple(xs[max_i].tolist())
def p_dist(x, y, p=2):
if p % 2:
return sum(abs(x_i - y_i) ** p for x_i, y_i in zip(x, y))
else:
return sum((x_i - y_i) ** p for x_i, y_i in zip(x, y))
def minmax_dist_loop(x0, xs, d_func=p_dist):
i_xs = iter(xs)
min_i = max_i = 0
min_d = max_d = d_func(x0, next(i_xs))
for i, x in enumerate(i_xs, 1):
d = d_func(x0, x)
if d < min_d:
min_d = d
min_i = i
elif d > max_d:
max_d = d
max_i = i
return xs[min_i], xs[max_i]
def minmax_dist_key(x0, xs, d_func=p_dist):
return (
min(xs, key=lambda x: d_func(x, x0)),
max(xs, key=lambda x: d_func(x, x0)))
And the code to obtain the timings:
x0 = (1, 2)
xs = [(2, 6), (8, 6), (5, 8), (2, 4)]
funcs = minmax_dist_np, minmax_dist_loop, minmax_dist_key, minmax_dist_nb
for n in (1, 10, 100, 1000):
nxs = xs * n
print(f"N = {n * len(xs)}")
base = funcs[0](x0, nxs)
for func in funcs:
res = func(x0, nxs)
print(f"{func.__name__:>24} {base == res}", end=' ')
%timeit -n 50 func(x0, nxs)
# N = 4
# minmax_dist_np True 50 loops, best of 5: 16.2 µs per loop
# minmax_dist_loop True 50 loops, best of 5: 6.11 µs per loop
# minmax_dist_key True 50 loops, best of 5: 11.6 µs per loop
# minmax_dist_nb True 50 loops, best of 5: 18.1 µs per loop
# N = 40
# minmax_dist_np True 50 loops, best of 5: 39.6 µs per loop
# minmax_dist_loop True 50 loops, best of 5: 54.3 µs per loop
# minmax_dist_key True 50 loops, best of 5: 107 µs per loop
# minmax_dist_nb True 50 loops, best of 5: 43.2 µs per loop
# N = 400
# minmax_dist_np True 50 loops, best of 5: 232 µs per loop
# minmax_dist_loop True 50 loops, best of 5: 550 µs per loop
# minmax_dist_key True 50 loops, best of 5: 1.07 ms per loop
# minmax_dist_nb True 50 loops, best of 5: 281 µs per loop
# N = 4000
# minmax_dist_np True 50 loops, best of 5: 2.28 ms per loop
# minmax_dist_loop True 50 loops, best of 5: 5.7 ms per loop
# minmax_dist_key True 50 loops, best of 5: 11.3 ms per loop
# minmax_dist_nb True 50 loops, best of 5: 2.78 ms per loop
indicating that for sufficiently small inputs, minmax_dist_loop() is the fastest, but as soon as the inputs get larger, minmax_dist_np() and minmax_dist_nb() take over by a fair margin.
Conversely, minmax_dist_key() gets progressively to be the slowest, essentially because it needs to compute the expensive distance function twice as much as minmax_dist_loop(). While the looping is computed twice also for minmax_dist_np(), the computation of the distance is done only once (at the cost of creating a potentially large temporary object).
