Notebook created by Martín Villanueva - martin.villanueva@usm.cl - DI UTFSM - April 2017.
In [1]:
import numba
import numpy as np
import numexpr as ne
import matplotlib.pyplot as plt
En esta actividad implementaremos una conocida métrica para medir disimilitud entre conjuntos: La métrica de Hausdorff. Esta corresponde a un métrica o distancia ocupada para medir cuán disímiles son dos subconjuntos dados.
Esta tiene muchas aplicaciones, en particular para comparar el parecido entre imágenes. En el caso en donde los conjuntos son arreglos bidimensionales, la definición es la siguiente:
Sean $X \in \mathbb{R}^{m \times 3}$ e $Y \in \mathbb{R}^{n \times 3}$ dos matrices, la métrica/distancia de Hausdorff sobre sobre estas como:
$$ d_H(X,Y) = \max \left(\ \max_{i\leq m} \min_{j \leq n} d(X[i],Y[j]), \ \max_{j\leq n} \min_{i \leq m} d(Y[j],X[i]) \ \right) $$donde $d$ es la distancia Euclideana clásica. ($X[i]$ indíca la i-ésima fila de X).
Ilustración unidimensional: Distancia entre funciones.
10 arreglos $X,Y$ aleatorios, con cantidad creciente de filas, y realice análsis de tiempos de ejecuciones de las funciones anteriores sobre estos arreglos.
In [2]:
def metric_python(x, y):
"""
standard Euclidean distance
"""
ret = x-y
ret *= ret
return np.sqrt(ret).sum()
def inf_dist_python(x, Y):
"""
inf distance between row x and array Y
"""
m = Y.shape[0]
inf = np.inf
for i in range(m):
dist = metric_python(x, Y[i])
if dist < inf:
inf = dist
return inf
def hausdorff_python(X, Y):
"""
Hausdorff distance between arrays X and Y
"""
m = X.shape[0]
n = Y.shape[0]
sup1 = -1.
sup2 = -1.
for i in range(m):
inf1 = inf_dist_python(X[i], Y)
if inf1 > sup1:
sup1 = inf1
for i in range(n):
inf2 = inf_dist_python(Y[i], X)
if inf2 > sup2:
sup2 = inf2
return max(sup1, sup2)
In [3]:
@numba.jit('float64 (float64[:], float64[:])')
def metric_numba(x, y):
"""
standard Euclidean distance
"""
ret = x-y
ret *= ret
return np.sqrt(ret).sum()
@numba.jit('float64 (float64[:], float64[:,:])', nopython=True)
def inf_dist_numba(x, Y):
"""
inf distance between row x and array Y
"""
m = Y.shape[0]
inf = np.inf
for i in range(m):
dist = metric_numba(x, Y[i])
if dist < inf:
inf = dist
return inf
@numba.jit('float64 (float64[:,:], float64[:,:])', nopython=True)
def hausdorff_numba(X, Y):
"""
Hausdorff distance between arrays X and Y
"""
m = X.shape[0]
n = Y.shape[0]
sup1 = -1.
sup2 = -1.
for i in range(m):
inf1 = inf_dist_numba(X[i], Y)
if inf1 > sup1:
sup1 = inf1
for i in range(n):
inf2 = inf_dist_numba(Y[i], X)
if inf2 > sup2:
sup2 = inf2
return max(sup1, sup2)
In [4]:
#nrows = [10**n for n in range(10)]
nrows = np.linspace(100,5000,10).astype(int)
for nrow in nrows:
X = np.random.random((nrow,3))
Y = np.random.random((nrow,3))
tp = %timeit -o hausdorff_python(X,Y)
tn = %timeit -o hausdorff_numba(X,Y)
print("Number of rows: {0}".format(nrow))
print("Best time in Python: {0}".format(tp.best))
print("Best time in Numba: {0} \n".format(tn.best))
del X,Y