LAB Tipos abstractos de datos
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()
from local.lib.rlxmoocapi import submit, session
student = session.Session(init.endpoint).login( course_id=init.course_id,
session_id="UDEA",
lab_id="lab_01" )
LAB Tipos abstractos de datos¶
Ejercicio 1: Implementación de una pila¶
Definimos el siguiente TAD, como una estructura de tipo LIFO (Last In First Out)
TAD \(Stack\)
\(\forall S \in Stack, d \in AnyType\)
signatures: $$
$$
axioms:
\(new().len() ::= 0 \)
\(S.put(d).get() ::= d\)
\(S.put(d).len() ::= S.len()+1\)
\(S.get() \;\;and\;\; S.len()==0::=Error\)
\(S.len()=n \;\;and\;\;S.get() \Rightarrow S.len()=n-1\)
## Ejercicio 1
completa la función siguiente para añadir un elemento a una lista
ejecución de ejemplo:
> x = [1,4,3]
> print st.append(x,5)
[1, 4, 3, 5]
def append(l,d):
return ...
verifica manualmente tu código
x = [1,4,3]
append(x,5)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_01");
Ejercicio 2: Eliminación de elementos¶
completa la función siguiente para que, dada una lista, devuelva dos resultados:
el valor del último elemento de la lista
una nueva lista en la que se eliminó el último elemento
si la lista es vacía debe de generar un
AssertionError
Ejemplo de ejecución:
> x = [1,5,6]
> print "initial", x
> for _ in range(len(x)+1):
> v,x = getremove_last(x)
> print "last val", v, ", remaining list", x
initial [1, 5, 6]
last val 6 , remaining list [1, 5]
last val 5 , remaining list [1]
last val 1 , remaining list []
----------------------------------------------------------------------
AssertionError Traceback (most recent call last)
<ipython-input-4-578f9f1609fe> in <module>()
def getremove_last(l):
assert <... TU CODIGO AQUI ...>
val, rest_list = <... TU CODIGO AQUI ...>
return val, rest_list
comprueba manualmente tu código
x = [1,5,6]
print ("initial", x)
for _ in range(len(x)+1):
v,x = getremove_last(x)
print ("last val", v, ", remaining list", x)
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_02");
Ejercicio 3: Implementación de un stack¶
Completa la clase Stack con la semántica del TAD definido anteriormente. Usa las funciones anteriores si lo consideras necesario. Ejemplo de ejecución:
> print "stacking elements"
> s = st.Stack()
> s.put(4).put(2).put("hola")
> print s.len()
> print s.elements
>
> print ("\n--\nunstacking")
> for _ in range(s.len()):
> print s.get()
>
> print "this next call must fail"
> s.get()
stacking elements
3
[4, 2, 'hola']
--
unstacking
hola
2
4
this next call must fail
AssertionErrorTraceback (most recent call last)
<ipython-input-13-749203dd226f> in <module>()
13
14 print "this next call must fail"
---> 15 s.get()
...
def Stack(**kwargs):
def append(l,d):
<... TU CODIGO AQUI DEL EJERCICIO ANTERIOR ...>
def getremove_last(l):
<... TU CODIGO AQUI DEL EJERCICIO ANTERIOR ...>
class Stack__class:
def __init__(self):
self.elements = []
def put(self, d):
<... TU CODIGO AQUI ...>
return self
def get(self):
return <... TU CODIGO AQUI ...>
def len(self):
return <... TU CODIGO AQUI ...>
return Stack__class(**kwargs)
print ("stacking elements")
s = Stack()
s.put(4).put(2).put("hola")
print (s.len())
print (s.elements)
print ("\n--\nunstacking")
for _ in range(s.len()):
print (s.get())
try:
s.get()
print ("*** cuidado! tu código no contiene asserts")
except AssertionError:
print ("*** tu codigo está generando asserts correctos")
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_03");
Implementación de una Cola¶
Definimos el siguiente TAD, como una estructura de tipo FIFO (First In First Out)
TAD \(Queue\)
\(\forall Q \in Queue, d \in AnyType\)
signatures: $$
$$
axioms:
\(new().len() ::= 0 \)
\(Q.get()^n==d_i \iff Q=new().put(d_i)^n\)
\(Q.get(d).len() ::= Q.len()+1\)
\(Q.get() \;\;and\;\; Q.len()==0::=Error\)
\(Q.len()=n \;\;and\;\;Q.get() \Rightarrow Q.len()=n-1\)
y definimos la notación:
\(Q.put(d_i)^n ::= Q.put(d_1).put(d_2)....put(d_n)\)
\(Q.get()^n ::= Q.get()\;,\;... n\; veces\; ...\;,\; Q.get()\) y tomando el resultado del último
## Ejercicio 4
Completa la clase Queue con la semántica que acabamos de definir. Ejemplo de ejecución
> import PS01_04 as st
> reload(st)
>
> print "enqueueing elements"
> q = st.Queue()
> q.put(4).put(2).put("hola")
> print q.len()
> print q.elements
>
> print ("\n--\ndequeueing")
> for _ in range(q.len()):
> print q.get()
>
< print "this next call must fail"
> q.get()
enqueueing elements
3
[4, 2, 'hola']
--
dequeueing
4
2
hola
this next call must fail
AssertionErrorTraceback (most recent call last)
<ipython-input-284-50dc775a67ed> in <module>()
13
14 print "this next call must fail"
---> 15 q.get()
def Queue(**kwargs):
<... INSERTA AQUI LAS FUNCIONES QUE CREES QUE NECESITES ...>
class Queue__class:
def __init__(self):
self.elements = []
def put(self, d):
<... TU CODIGO AQUI ...>
return self
def get(self):
return <... TU CODIGO AQUI ...>
def len(self):
return <... TU CODIGO AQUI ...>
return Queue__class(**kwargs)
print ("enqueueing elements")
q = Queue()
q.put(4).put(2).put("hola")
print (q.len())
print (q.elements)
print ("\n--\ndequeueing")
for _ in range(q.len()):
print (q.get())
print ("this next call must fail")
q.get()
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_04");
Medición de renidimientos y complejidades algorítmicas¶
Ejercicio 5¶
completa la función siguiente que debe de llenar una cola o una pila t, pasada como argumento, con n números enteros aleatorios con valores entre 0 y 9, ambos incluidos. Usa np.random.randint
import numpy as np
def fill(t, n):
return <... TU CODIGO AQUI ...>
comprueba manualmente tu código, cada ejecución ha de generar valores distintos
q = fill(Queue(), 100)
print ("len=",q.len())
for _ in range(q.len()):
print (q.get(), end=" ")
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_05");
Ejercicio 6¶
completa la función siguiente que debe de vaciar una cola o pila t y devolver el conjunto de datos obtenido tras vaciarla.
def empty(t):
return <... TU CODIGO AQUI ...>
a = [1,4,1,10,2,3]
q = Queue()
for i in a:
q.put(i)
k = empty(q)
k
registra tu solución en línea¶
student.submit_task(globals(), task_id="task_06");
Experimento¶
ya acabaste el taller, fíjate ahora como hacemos un experimento con pilas y colas de varios tamaños y comparamos los tiempos de ejecución. Comparamos también con las implementaciones que ya vienen en las librerías estándar de Python: Queue LifoQueue. Observa que queue.Queue es funcionalmente equivalente a nuestro Queue y queue.LifoQueue es equivalente a nuestro Stack.
Hazte las siguientes preguntas:
¿Qué implementaciones son más lentas y más rápidas? ¿Por qué?
¿Qué complejidades tenemos en inserción y recuperación? \(\mathcal{O}(n)\), \(\mathcal{O}(\log n)\), \(\mathcal{O}(c)\) ?
Observa que las métricas de tiempo tienen dos componentes:
El debido a la complejidad intrínseca del algoritmo
El debido a la implementación del mismo
import matplotlib.pyplot as plt
%matplotlib inline
def compare(class_1, class_2, n_powers=5):
global n, class_A, class_B, q
class_A = class_1
class_B = class_2
t1, t2, t3, t4 = [], [], [], []
ns = [int(10**i) for i in range(n_powers)]
for n in ns:
print (n,end=" ")
k = %timeit -o -q fill(class_A(), n)
t1.append(k.best*1000)
k = %timeit -o -q fill(class_B(), n)
t2.append(k.best*1000)
q = fill(class_A(), n)
k = %timeit -o -r 1 -n 1 -q empty(q)
t3.append(k.best*1000)
q = fill(class_B(), n)
k = %timeit -o -r 1 -n 1 -q empty(q)
t4.append(k.best*1000)
plt.figure(figsize=(10,3))
plt.subplot(121)
plt.plot(t1, label=class_A.__name__+" fill")
plt.plot(t2, label=class_B.__name__+" fill")
plt.xticks(range(len(ns)), ns)
plt.xlabel("number of elements")
plt.ylabel("time (ms)")
plt.legend()
plt.subplot(122)
plt.plot(t3, label=class_A.__name__+" empty")
plt.plot(t4, label=class_B.__name__+" empty")
plt.xticks(range(len(ns)), ns)
plt.xlabel("number of elements")
plt.legend()
compare(Queue, Stack);
import queue
class wQueue(queue.Queue):
def len(self):
return self.qsize()
class wLifoQueue(queue.LifoQueue):
def len(self):
return self.qsize()
compare(wQueue, wLifoQueue)