K-vector search technique

basado en: "A K-VECTOR APPROACH TO SAMPLING, INTERPOLATION, AND APPROXIMATION" Daniele Mortari and Jonathan Rogers

Primera implentación con una base de datos random



In [2]:

    
#Imports
import numpy as np
import matplotlib.pyplot as plt

Comenzamos con el preprocesamiento



In [3]:

    
n = 10000 #numero de elementos de la base de datos
#prealocamos los vectores
y = np.zeros(n)
s = np.zeros_like(y)
i = np.zeros_like(y)
k = np.zeros_like(y)
y_busqueda = np.zeros_like(y)
#y_busqueda2 = np.zeros_like(y)
vec_aux = np.zeros_like(y)

#epsilon es el numero de precision de la maquina
epsilon = np.finfo(np.float).eps
delta_epsilon = (n - 1) * epsilon

Nuestra base de datos es el vector random $\mathbf{y}$



In [4]:

    
y = np.random.random(n)

#luego lo ordenamos de forma ascendente

#primero obtenemos el vector de indices i del ordenamiento

i = np.argsort(y)

s = y[i]

y_min = s[0]  # primer elemento
y_max = s[-1]  # ultimo elemento

#generamos la recta z(x)=mx+q

m = (y_max - y_min + 2 * delta_epsilon ) / (n-1)
q = y_min - m - delta_epsilon
#funcion anonima para la recta
z = lambda x: (m * x + q)
i = np.arange(n)
z_discreto = z(i)

#generamos el k-vector

k[0] = 0
k[-1] = n

#TODO vectorizar esto:

for aux in xrange(1,n):
    vec_aux = s < z_discreto[aux]
    k[aux] = np.sum(vec_aux)

Supongamos que queremos efectuar una busqueda entre $y_{a}=.3$ e $y_{b}=.7$



In [5]:

    
#Rango de búsqueda
y_a = .3
y_b = .7

Siguiendo los pasos del paper :



In [6]:

    
#%%timeit
j_b = np.floor((y_a - q) / m)
j_t = np.ceil((y_b - q) / m)

k_start = k[j_b] + 1
k_end = k[j_t]

k_busqueda = np.arange(int(k_start),int(k_end))


y_busqueda = s[k_busqueda]

#ahora si la cantidad de elementos de la base de datos es grande en promedio la
#cantidad de elementos que estan fuera del rango e0 =1 entonces esta en algunos
#de los dos extremos

if y_busqueda[0] <= y_a:
    y_busqueda = np.delete(y_busqueda,0)

if y_busqueda[-1] >= y_b:
    y_busqueda = np.delete(y_busqueda,len(y_busqueda) - 1)



In [7]:

    
y_busqueda









    Out[7]:





array([ 0.30013973,  0.30014908,  0.30016499, ...,  0.69937947,
        0.69945416,  0.6998439 ])



In [8]:

    
len(y_busqueda)









    Out[8]:





4006



In [9]:

    
#%%timeit
index1 = np.argwhere(s <= 0.7)
index2 = np.argwhere(s >= 0.3)
y_busqueda2 = s[index2[0]:index1[-1]]



In [10]:

    
y_busqueda2









    Out[10]:





array([ 0.30012065,  0.30013973,  0.30014908, ...,  0.69922712,
        0.69937947,  0.69945416])



In [11]:

    
len(y_busqueda2)









    Out[11]:





4006



In [12]:

    
index1









    Out[12]:





array([[   0],
       [   1],
       [   2],
       ..., 
       [7021],
       [7022],
       [7023]])



In [13]:

    
s[6991]









    Out[13]:





0.69583131926330333



In [14]:

    
epsilon









    Out[14]:





2.2204460492503131e-16



In [15]:

    
s









    Out[15]:





array([  5.38547418e-06,   1.05323082e-04,   1.61032375e-04, ...,
         9.99753467e-01,   9.99970135e-01,   9.99994605e-01])



In [ ]: