Tipos abstractos de datos
Contents
!wget -nc --no-cache -O init.py -q https://raw.githubusercontent.com/rramosp/introalgs.v1/main/content/init.py
import init; init.init(force_download=False);
Tipos abstractos de datos¶
Objetivos del módulo¶
Conocer el concepto de tipos abstractos de datos y aprender a definir, interpretar e implementar estructuras de datos usando esta técnica.
Preguntas básicas¶
¿Qué es una tipo abstracto de datos (TAD)?
¿Qué significa ‘abstracto’?
¿Cómo se define un TAD?
¿Cómo se implementa un TAD?
¿Cómo se mide el rendimiento de una implementación?
Introducción¶
Uno de los temas de mayor importancia en el desarrollo de software es la definición de estructuras de datos en abstracto, es decir, independiente de su representación. Dicha definición conduce hacia la programación orientada a objetos (POO) y a una de sus principales características: el encapsulamiento.
TIPO (type): es un conjunto de valores. P.ej. [
True,False], \(\mathbb{N}\), \(\mathbb{Z}\)TIPO ABSTRACTO DE DATOS (TAD) (abstract data type, ADT): es un tipo de datos, MÁS una definición de conjunto de operaciones sobre este tipo de datos, MÁS un conjunto de axiomas que definen la semántica de las operaciones.
ESTRUCTURA DE DATOS (data structure): es una realización de un TAD en un lenguaje de programación concreto.
es preciso observar que:
Un TAD es una definición abstracta en algún idioma matemático o informal.
Un TAD especifica QUÉ hace una operación, pero no CÓMO.
Los axiomas suelen definir precondiciones y poscondiciones de las operaciones.
Si la definición de un TAD es totalmente matemática podríamos en teoría probar formalmente propiedades y algoritmos (i.e. verificación formal, derivación de programas, reparación de bugs, etc.).
Algunos tipos están ya implementados (built-in) en la base de Java, Python, Haskell, C, …
Un TAD suele imlpementarse como una clase en distintos lenguajes de programación.
referencias:
http://www.cs.fsu.edu/~lacher/lectures/Output/adts/index.html
http://btechsmartclass.com/DS/U1_T1.html
https://ece.uwaterloo.ca/~dwharder/aads/Abstract_data_types/Linear_ordering/Stack/
https://www.geeksforgeeks.org/abstract-data-types/
Ejemplo 1. Números naturales¶
TAD: \(NumeroNatural\)
\(\forall n,m \in NumeroNatural\)
signatures: $$
$$
axioms:
\(esCero(cero()) := \)
True
\(esCero(sucesor(x)) := \)False\(suma(cero(), y) := y\)
\(sum(sucesor(x),y) := sucesor(suma(x,y))\)\(resta(x, cero()) ::= x\)
\(resta(cero(), y) ::= \) if \( esCero(y)\) then \(cero()\) else \(error\)
\(resta(sucesor(x), sucesor(y)):=resta(x,y)\)\(multiplica(x, cero()) ::= cero()\)
\(multiplica(x, sucesor(y)) ::= suma(x, multiplica(x, y))\)\(divide(cero(), y) ::= cero()\)
\(divide(x, cero()) ::= error\)
\(divide(x, y) ::=\) if \(menor(x, y) \) then \( cero()\) else \(sucesor(divide(resta(x, y), y))\)\(igual(Cero(), x) ::= esCero(x)\)
\(igual(sucesor(x), cero()) ::= False\)
\(igual(sucesor(x), sucesor(y)) ::= igual(x, y)\)
Observa que:
En la parte de axiomas se utiliza el símbolo
::=, el cual se lee se define como y se conoce como la notación BNF (Backus Naur Form).En la parte correspondiente a las funciones se definen las operaciones que se pueden realizar, su sintaxis y el resultado que se obtiene al efectuar alguna de ellas.
En la definición de funciones siempre se debe incluir:
Una función que cree la estructura vacía. En nuestro ejemplo es la función \(cero()\) la cual crea la estructura \(NumeroNatural\) vacía.
Una función que genere o que permita incluir los elementos o datos objeto que conformarán la estructura a definir. En nuestro ejemplo es la función \(sucesor()\)
En la parte de axiomas se describe la forma como trabajan las funciones. Se omiten en esta parte las dos funciones básicas, (creación y generación) definidas anteriormente, ya que su forma de operación está implícita en la definición de la función.
La función cero() crea la estructura número natural vacía. sucesor(cero()) generará el primer número natural, el 1. sucesor(sucesor(cero())) representa el número natural 2 y así sucesivamente. En general, si sucesor(x) es un número natural i, entonces x representa el número natural i – 1.
Preguntas
Realiza las siguientes operaciones usando las funciones y axiomas definidos
2+3
5-2
4*5
12/4
12/5
Ejemplo 2: Un diccionario¶
TAD: \(Diccionario\)
\(\forall\; A \in Diccionario \;\;\; i,j,v \in AnyType\)
signatures: $$
$$
axioms:
\(crear().esVacio() := \)
True
\(A.almacena(i,v).esVacio() :=\)False
\(crear().recupera(i) := error\)
\(A.almacenar(i,v).recupera(j) := v\) if \(i==j\) else \(A.recupera(j)\)
Observa:
que siempre tenemos que tener alguna función que nos cree una instancia de un TAD
Python tiene una estructura
dictcon una semántica similar y con las funciones de almacenar y recuperar accesibles indirectamente a través de una sintaxis dedicada.
A = {"uno": "el primer elemento", "zapato": "para el pie", 3: "el numero 3", "dos": 2 }
for k,v in A.items():
print("%10s"%str(k),"::", v)
uno :: el primer elemento
zapato :: para el pie
3 :: el numero 3
dos :: 2
print(A["uno"])
print(A[3])
print(A["dos"])
print(A["zapato"])
el primer elemento
el numero 3
2
para el pie
A["dos"] = "el numero dos"
A["comer"] = "verbo transitivo"
for k,v in A.items():
print("%10s"%str(k),"::", v)
uno :: el primer elemento
zapato :: para el pie
3 :: el numero 3
dos :: el numero dos
comer :: verbo transitivo
A["dos"]
'el numero dos'
Ejemplo 3. Lista Ordenada¶
Definición informal¶
tipo de datos:
los elementos de una lista ordenada son de un determinado tipo (p.ej. \(\mathbb{N}\), o
string) que admite una función de comparación (1 < 2, “albert” < “arbol”).
funciones:
OrderedList(tipo): crea una lista ordenada vacía para elementos de tipo de datostipo. Precondición: El tipo de datos ha de admitir comparación.add(item): añade un nuevo ítem a la lista preservando el orden de la misma. Si el ítem ya existe en la lista la operación no modifica la lista. Precondición: El ítem ha de ser del tipo de la lista.remove(item): elimina un ítem de la lista preservando el orden de la misma. Precondición: El ítem ha de existir en la lista.contains(item): devuelve un booleano indicando si el ítem está en la lista.len(): devuelve un entero con el número de elementos que tiene la lista.first(): devuelve el primer item de la lista y establece un cursor en el primer item. Precondición: la lista no puede estar vacia.next(): mueve el cursor al siguiente item de la lista y devuelve el item en el que inicialmente estaba. Precondición: el cursor no puede estar en el último item.has_more(): devuelve un booleanoTruesi el cursor está en el último item. Si no, devuelveFalse
Definición por axiomas¶
TAD: \(OrderedList\)
\(\forall \mathbb{T} \in Types, L \in OrderedList; a \in \mathbb{T}; k, n\in\mathbb{Z} \)
signatures: $$
$$
definitions:
\(L^n ::= L.first(); \;\;\; L.next() \times (n-1) \;\;with\;\; n\in[1,len(L)]\)
\(k ::= n\) if \(L^n\)
\(L.has\_more() ::= k<len(L)\)
observa que la definición de \(k\) depende de cuantas veces haya llamado el usuario a la función \(next\) después de \(first\).
preconditions
| operación | precondición |
|---|---|
| $OrderedList (\mathbb{T})$ | $\mathbb{T}$ admite comparación |
| $L.add(a)$ | $ a \in \mathbb{T}$ |
| $L.remove(a)$ | $ L.contains(a)$ |
| $L.first()$ | $len(L)>0$ |
| $L^n$ | $n\in[1,len(L)]$ |
axioms (post conditions):
axiom 1: \(len(OrderedList(\mathbb{T}))=0\)
axiom 2: \(L^n < L^{n+1}\)
axiom 3: \(L.contains(a) \iff \exists n \;\;|\;\; a = L^n\)
axiom 4: \(len(L.add(a)) = len(L)+ 1 - L.contains(a)\)
axiom 5: \(len(L.remove(a)) = len(L) - L.contains(a)\)
axiom 6: \(L.add(a) \Rightarrow L.contains(a)\)
axiom 7: \(L.remove(a) \Rightarrow \neg L.contains(a)\)
Dada una implementación concreta, los axiomas nos permiten verificar si la implementación es correcta.
Implementación en Python¶
Observa:
el TAD se implementa como una clase de Python
las precondiciones las implementamos con
assert¿qué tan eficiente es esta implementación?
class OrderedList:
def __init__(self, item_type):
self.item_type = item_type
self.list = []
self.cursor = 0
def add(self, item):
assert type(item)==self.item_type, "must comply with declared type"
self.list = [i for i in self.list if i<item] + [item] + [i for i in self.list if i>item]
return self
def remove(self, item):
assert self.contains(item), "item not in list"
self.list = [i for i in self.list if item!=i]
return self
def contains(self, item):
return item in self.list
def first(self):
self.cursor = 1
return self.list[self.cursor-1]
def __next__(self):
assert self.has_more(), "no more items in list"
self.cursor += 1
return self.list[self.cursor-1]
def has_more(self):
return self.cursor<len(self.list)
def len(self):
return len(self.list)
comprobamos a mano la implementación
k = OrderedList(int)
k.add(10).add(1).add(2)
print(k.list)
k.remove(2)
print(k.list)
[1, 2, 10]
[1, 10]
comprobamos alguna precondición
print(k.first(), k.has_more())
print(next(k), k.has_more())
print(next(k))
1 True
10 False
---------------------------------------------------------------------------
AssertionError Traceback (most recent call last)
<ipython-input-7-ba9de29813c3> in <module>
1 print(k.first(), k.has_more())
2 print(next(k), k.has_more())
----> 3 print(next(k))
<ipython-input-5-5f8717398b95> in __next__(self)
24
25 def __next__(self):
---> 26 assert self.has_more(), "no more items in list"
27 self.cursor += 1
28 return self.list[self.cursor-1]
AssertionError: no more items in list
k.add("ho")
---------------------------------------------------------------------------
AssertionError Traceback (most recent call last)
<ipython-input-8-f961c13bf47b> in <module>
----> 1 k.add("ho")
<ipython-input-5-5f8717398b95> in add(self, item)
7
8 def add(self, item):
----> 9 assert type(item)==self.item_type, "must comply with declared type"
10 self.list = [i for i in self.list if i<item] + [item] + [i for i in self.list if i>item]
11 return self
AssertionError: must comply with declared type
k.remove(2)
---------------------------------------------------------------------------
AssertionError Traceback (most recent call last)
<ipython-input-9-3774a04f67d2> in <module>
----> 1 k.remove(2)
<ipython-input-5-5f8717398b95> in remove(self, item)
12
13 def remove(self, item):
---> 14 assert self.contains(item), "item not in list"
15 self.list = [i for i in self.list if item!=i]
16 return self
AssertionError: item not in list
SUGERENCIA ejecuta el código anterior en Python Tutor
tests unitarios con los axiomas¶
estos tests son independientes de la implementación
axiom 1: \(len(OrderedList(\mathbb{T}))=0\)
def test_axiom1(ordered_list_class):
L = ordered_list_class(int)
print("new list length:", L.len())
assert L.len()==0
test_axiom1(OrderedList)
new list length: 0
axiom 2: \(L^n < L^{n+1}\)
def test_axiom2(ordered_list_class):
import numpy as np
L = ordered_list_class(int)
print("inserting", end=' ')
for i in range(20):
k = np.random.randint(1000)
print(k, end=' ')
L.add(k)
print("\n\ntesting with list", L.list, "\n")
item = L.first()
while L.has_more():
k = next(L)
print(item,"<",k, " ", end=' ')
assert item < k, "wrong list order: %d before %d"%(item,k)
item = k
test_axiom2(OrderedList)
inserting 642 495 683 514 101 989 259 166 493 224 565 847 427 981 430 881 317 759 972 650
testing with list [101, 166, 224, 259, 317, 427, 430, 493, 495, 514, 565, 642, 650, 683, 759, 847, 881, 972, 981, 989]
101 < 166 166 < 224 224 < 259 259 < 317 317 < 427 427 < 430 430 < 493 493 < 495 495 < 514 514 < 565 565 < 642 642 < 650 650 < 683 683 < 759 759 < 847 847 < 881 881 < 972 972 < 981 981 < 989
Otra implementación en Python¶
usamos la librería bisect. observa este ejemplo
import bisect
l = [1,2,10,12,30]
print(bisect.bisect_left(l,11), bisect.bisect_right(l,11))
print(bisect.bisect_left(l,12), bisect.bisect_right(l,12))
bisect.insort_left(l,9)
print(l)
3 3
3 4
[1, 2, 9, 10, 12, 30]
Observa cómo usamos herencia para redefinir sólo los métodos que queremos
class OrderedList_bisect(OrderedList):
def add(self, item):
assert type(item)==self.item_type, "must comply with declared type"
if not self.contains(item):
bisect.insort_left(self.list, item)
return self
def remove(self, item):
k = bisect.bisect_left(self.list, item)
assert k<len(self.list) and self.list[k]==item, "item not in list"
self.list = self.list[:k]+self.list[k+1:]
return self
def contains(self, item):
k = bisect.bisect_left(self.list, item)
return k<len(self.list) and self.list[k]==item
verificamos los axiomas que tenemos implementados¶
test_axiom1(OrderedList)
test_axiom1(OrderedList_bisect)
new list length: 0
new list length: 0
test_axiom2(OrderedList)
inserting 484 210 70 721 896 371 586 943 677 838 833 174 399 331 378 6 543 716 928 810
testing with list [6, 70, 174, 210, 331, 371, 378, 399, 484, 543, 586, 677, 716, 721, 810, 833, 838, 896, 928, 943]
6 < 70 70 < 174 174 < 210 210 < 331 331 < 371 371 < 378 378 < 399 399 < 484 484 < 543 543 < 586 586 < 677 677 < 716 716 < 721 721 < 810 810 < 833 833 < 838 838 < 896 896 < 928 928 < 943
test_axiom2(OrderedList_bisect)
inserting 180 149 839 533 669 274 637 321 583 853 379 752 461 444 351 209 822 933 703 922
testing with list [149, 180, 209, 274, 321, 351, 379, 444, 461, 533, 583, 637, 669, 703, 752, 822, 839, 853, 922, 933]
149 < 180 180 < 209 209 < 274 274 < 321 321 < 351 351 < 379 379 < 444 444 < 461 461 < 533 533 < 583 583 < 637 637 < 669 669 < 703 703 < 752 752 < 822 822 < 839 839 < 853 853 < 922 922 < 933
medimos rendimiento de ambas implementaciones¶
import numpy as np
l = np.random.randint(100000,size=1000)
print(len(l), len(np.unique(l)))
1000 997
para la operación de add
L1 = OrderedList(np.int64)
L2 = OrderedList_bisect(np.int64)
%%timeit
for i in l:
L1.add(i)
146 ms ± 9.04 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%%timeit
for i in l:
L2.add(i)
1.55 ms ± 37 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
para la operación contains
L1 = OrderedList(np.int64)
L2 = OrderedList_bisect(np.int64)
for i in l:
L1.add(i)
L2.add(i)
print(L1.len(), L2.len())
997 997
%%timeit
for i in l:
L1.contains(i)
16.8 ms ± 146 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%%timeit
for i in l:
L2.contains(i)
1.26 ms ± 30.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
Ejercicios propuestos:¶
Complete la estructura númeroNatural incluyendo las operaciones módulo, potencia, factorial, máximo común divisor, mínimo común múltiplo, diferente, mayor, mayor o igual, menor y menor o igual.
Defina estructura númeroEntero incluyendo las mismas operaciones que en la estructura númeroNatural. Defina operaciones que considere necesarias para desarrollar los axiomas de las funciones definidas.
Defina una estructura Conjunto con operaciones Unión, Intersección, Pertenencia y Complemento.
Defina estructura String con operaciones esVacío, longitud, concatenación, subHilera y posición.
Defina estructura Lógico con sus correspondientes funciones y axiomas.