LAB 06 - Árboles
Contents
!wget --no-cache -O init.py -q https://raw.githubusercontent.com/rramosp/20192.L3/master/init.py
import init; init.init(force_download=False); init.get_weblink()
import init
from local.lib.rlxmoocapi import submit, session
import inspect
student = session.Session(init.endpoint).login( course_id=init.course_id,
session_id="UDEA",
lab_id="lab_06" )
LAB 06 - Árboles¶
Heapsort¶
En este taller vamos a implementar el algoritmo de ordenación llamado Heapsort. Consulta Heapsort en Wikipedia. Es un algoritmo que, dado un vector:
Lo interpreta como un árbol binario
Fase 1: Lo convierte en un Heap, es decir, un árbol binario en el que cualquier padre tiene un valor mayor que sus hijos. Esto garantiza que la raíz sea el nodo con mayor valor.
Fase 2: Ordena el Heap de forma que, sucesivamente, va pasando la raíz al final del árbol
Usaremos como base la clase de las notas
Ejercicio 1¶
Implementa el método shift_down para que descienda cualquier elemento hasta un punto en el que sus dos hijos son menores, sin pasarse de la posición end.
Recuerda que:
sefl.ves un vector que almacena todos los elementos del array en un orden predeterminado.self.get_children_positionste da en qué lugar de ese vector están almacenados los hijos de un cierto nodo.startes la posición del nodo que queremos desplazar.endes la posición más alta en la que se puede desplazar el nodo.
Sugerencia de pseudo código:
1. pos_nodo = start
2. mientras pos_nodo tenga hijos y pos_nodo<=end
3. intercambiar el valor del nodo por el mayor de los hijos que no esté más allá de end, si es que alguno de los hijos es mayor.
4. pos_nodo = hijo intercambiado
ejemplo de ejecución:
v = [5,9,4,1,6,2,8,3]
print VBinTree1(v)
print VBinTree1(v).shift_down(0)
print VBinTree1(v).shift_down(1)
print VBinTree1(v).shift_down(3)
salida esperada:
5
9
1
3
6
4
2
8
9
6
1
3
5
4
2
8
5
9
1
3
6
4
2
8
5
9
3
1
6
4
2
8
def VBinTree1(v=None, **kwargs):
import numpy as np
class VBinTree(object):
def __init__(self, v=v,**kwargs):
import numpy as np
self.v = np.r_[[i for i in v]] # copy
def get_height(self):
i,c=0,0
while c<len(self.v):
c += 2**i
i += 1
return i-1
def get_level(self, i):
n = 0
while sum([2**j for j in range(n)])<=i:
n+=1
return n-1
def get_children_positions(self, i):
return (2*i+1 if 2*i+1<len(self.v) else None,\
2*i+2 if 2*i+2<len(self.v) else None)
def get_parent_position(self, i):
assert type(i)==int and i>=0
return (i-1)/2 if i!=0 else None
def get_sibling_position(self, i):
if i==0:
return None
return [k for k in self.get_children_positions(self.get_parent_position(i)) if k!=i][0]
def to_indented_string(self, i, level):
c = self.get_children_positions(i)
s = (" "*2*level + str(self.v[i]) + "\n") if self.v[i] is not None else ""
s += self.to_indented_string(c[0],level+1) if c[0] is not None else ""
s += self.to_indented_string(c[1],level+1) if c[1] is not None else ""
return s
def __repr__(self):
return self.to_indented_string(0,0)
class VBinTree1_class(VBinTree):
def shift_down(self, start, end=None):
<... TU CODIGO AQUI ...>
return self
return VBinTree1_class(**kwargs)
prueba los siguientes valores de i:
0 (==5, el nodo root), fíjate hasta donde se mueve
1 (==9, no se mueve)
3 (==1, se intercambia con el 3)
v = [5,9,4,1,6,2,8,3]
b = VBinTree1(v)
print(b)
i=1
print("shifting down element",i,"whose value is", b.v[i])
b.shift_down(i)
print(b)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_01");
Ejercicio 2¶
tendremos que hacer un recorrido desde el último nodo que sea padre en el árbol, hasta el primero, llamando al método del ejercicio anterior.
para ello, implementaremos primero un método get_past_parent_position que, dado un árbol, encuentre la posición del último padre en el vector (que puede tener uno o dos hijos), pero no ninguno.
def VBinTree2(v=None,**kwargs):
import numpy as np
class VBinTree(object):
def __init__(self, v=v,**kwargs):
import numpy as np
self.v = np.r_[[i for i in v]] # copy
def get_height(self):
i,c=0,0
while c<len(self.v):
c += 2**i
i += 1
return i-1
def get_level(self, i):
n = 0
while sum([2**j for j in range(n)])<=i:
n+=1
return n-1
def get_children_positions(self, i):
return (2*i+1 if 2*i+1<len(self.v) else None,\
2*i+2 if 2*i+2<len(self.v) else None)
def get_parent_position(self, i):
assert type(i)==int and i>=0
return (i-1)/2 if i!=0 else None
def get_sibling_position(self, i):
if i==0:
return None
return [k for k in self.get_children_positions(self.get_parent_position(i)) if k!=i][0]
def to_indented_string(self, i, level):
c = self.get_children_positions(i)
s = (" "*2*level + str(self.v[i]) + "\n") if self.v[i] is not None else ""
s += self.to_indented_string(c[0],level+1) if c[0] is not None else ""
s += self.to_indented_string(c[1],level+1) if c[1] is not None else ""
return s
def __repr__(self):
return self.to_indented_string(0,0)
class VBinTree2_class(VBinTree):
def get_last_parent_position(self):
<... TU CODIGO AQUI ...>
return VBinTree2_class(**kwargs)
ejemplo de ejecución: para los siguientes dos árboles, la posición del último padre ha de ser 4 y 2 respectivamente
for v in [[5,9,0,1,6,2,8,3,4,5], [5,9,0,1,6,2,8]]:
b = VBinTree2(v)
print("\n\ntree:")
print(b)
p = b.get_last_parent_position()
print("last parent position",p, "content", b.v[p])
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_02");
Ejercicio 3¶
complela el método make_heap con un bucle desde el último padre hasta el primer elemento del árbol (su vector) realizando el shift_down de cada elemento. Con esto conseguimos que nuestra lista sea un Heap.
def VBinTree3(v=None,**kwargs):
import numpy as np
class VBinTree(object):
def __init__(self, v=v,**kwargs):
import numpy as np
self.v = np.r_[[i for i in v]] # copy
def get_height(self):
i,c=0,0
while c<len(self.v):
c += 2**i
i += 1
return i-1
def get_level(self, i):
n = 0
while sum([2**j for j in range(n)])<=i:
n+=1
return n-1
def get_children_positions(self, i):
return (2*i+1 if 2*i+1<len(self.v) else None,\
2*i+2 if 2*i+2<len(self.v) else None)
def get_parent_position(self, i):
assert type(i)==int and i>=0
return (i-1)/2 if i!=0 else None
def get_sibling_position(self, i):
if i==0:
return None
return [k for k in self.get_children_positions(self.get_parent_position(i)) if k!=i][0]
def to_indented_string(self, i, level):
c = self.get_children_positions(i)
s = (" "*2*level + str(self.v[i]) + "\n") if self.v[i] is not None else ""
s += self.to_indented_string(c[0],level+1) if c[0] is not None else ""
s += self.to_indented_string(c[1],level+1) if c[1] is not None else ""
return s
def __repr__(self):
return self.to_indented_string(0,0)
class VBinTree3_class(VBinTree):
def shift_down(self, start, end=None):
<... TU CODIGO AQUI ...>
return self
def get_last_parent_position(self):
<... TU CODIGO AQUI ...>
def make_heap(self):
<... TU CODIGO AQUI ...>
return VBinTree3_class(**kwargs)
import numpy as np
v = list(np.random.permutation(100)[:10])
#v = [2,48,65,95,66,42,30,32]
b = VBinTree3(v)
print("-- original tree")
print(b)
print("-- constructed heap")
b.make_heap()
print()
print(b)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_03");
Ejercicio 4¶
Finalmente, sobre el árbol resultado del ejercicio anterior, en un bucle desde el último nodo hasta el primero, intercambiamos la raíz con dicho nodo.
Pseudocódigo sugerido:
1. desde nodo=último nodo hasta el primero
2. intercambia el valor de la raíz del árbol con nodo
3. haz un shift_down de la raíz del árbol hasta nodo-1
def VBinTree4(v=None,**kwargs):
import numpy as np
class VBinTree(object):
def __init__(self, v=v,**kwargs):
import numpy as np
self.v = np.r_[[i for i in v]] # copy
def get_height(self):
i,c=0,0
while c<len(self.v):
c += 2**i
i += 1
return i-1
def get_level(self, i):
n = 0
while sum([2**j for j in range(n)])<=i:
n+=1
return n-1
def get_children_positions(self, i):
return (2*i+1 if 2*i+1<len(self.v) else None,\
2*i+2 if 2*i+2<len(self.v) else None)
def get_parent_position(self, i):
assert type(i)==int and i>=0
return (i-1)/2 if i!=0 else None
def get_sibling_position(self, i):
if i==0:
return None
return [k for k in self.get_children_positions(self.get_parent_position(i)) if k!=i][0]
def to_indented_string(self, i, level):
c = self.get_children_positions(i)
s = (" "*2*level + str(self.v[i]) + "\n") if self.v[i] is not None else ""
s += self.to_indented_string(c[0],level+1) if c[0] is not None else ""
s += self.to_indented_string(c[1],level+1) if c[1] is not None else ""
return s
def __repr__(self):
return self.to_indented_string(0,0)
class VBinTree4_class(VBinTree):
def shift_down(self, start, end=None):
<... TU CODIGO AQUI ...>
return self
def get_last_parent_position(self):
<... TU CODIGO AQUI ...>
def make_heap(self):
<... TU CODIGO AQUI ...>
def sort(self):
<... TU CODIGO AQUI ...>
return VBinTree4_class(**kwargs)
comprueba tu código
import numpy as np
v = list(np.random.permutation(100)[:15])
v = [57,58,73,48,62,75,88,15,29,40,53,61,56,8,1,32,51]
b = VBinTree4(v)
print("-- original tree")
print(b.v)
b.sort()
print("-- sorted tree")
print(b.v)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_04");
Experimentos¶
observa el siguiente TEST UNITARIO. Generamos vectores aleatorios, los ordenamos con el algoritmo recién creado y verificamos que el resultado está en orden.
import numpy as np
r=[]
n=1000
lengths = []
for i in range(n):
v = list(np.random.permutation(1000)[:np.random.randint(300)])
b = VBinTree4(v)
b.sort()
lengths.append(len(v))
a=np.r_[b.v]
r.append(np.alltrue(a[1:]-a[:-1]>0))
print("número total de vectores generados:", n)
print("número total de vectores ordenados:", np.sum(r))
print("avg/std longitud de los vectores: ", np.mean(lengths), "+/- %.1f"%np.std(lengths))
Complejidad computacional¶
Comprobamos experimentalmente que la complejidad computacional es \(\mathcal{O}(n\log n)\). Fíjate que la notación \(\mathcal{O}\) es un orden de magnitud que es independiente sumas y multiplicaciones por una constante. Para ajustar las mediciones del experimento al ideal de \(\mathcal{O}(n\log n)\) tenemos que calcular esa constante. ¿Dónde la calculamos en el código?
def heapsort_experiment(n):
v = list(np.random.permutation(n*5)[:n])
b = VBinTree4(v)
b.sort()
return
n_set = np.arange(0,4100,500)[1:]
s_times = []
for n in n_set:
print (n),
t = %timeit -o -q heapsort_experiment(n)
s_times.append(t.best)
import matplotlib.pyplot as plt
%matplotlib inline
plt.plot(n_set, s_times, label="measured")
plt.scatter(n_set, s_times)
log = n_set*np.log(n_set)
log = log*np.mean(s_times/log)
plt.plot(n_set, log, label="$\mathcal{O} (n\log n)$")
plt.legend()
plt.grid()
plt.xlabel("number of elements")
plt.ylabel("time (secs)");
pero fíjate que en el experimento no tenemos la operación de sort aislada. Verificamos por tanto que el tiempo de creación de un vector aleatorio es despreciable respecto a nuestro experimento
def randomlist_experiment(n):
v = list(np.random.permutation(n*5)[:n])
n_set = np.arange(0,5500,500)[1:]
r_times = []
for n in n_set:
print (n),
t = %timeit -r 10 -n 10 -o -q randomlist_experiment(n)
r_times.append(t.best)
import matplotlib.pyplot as plt
%matplotlib inline
plt.plot(n_set, r_times)
plt.scatter(n_set, r_times)
plt.grid()
plt.xlabel("number of elements")
plt.ylabel("time (secs)");