Como vimos, cualquier dato en SAGE tiene un tipo de datos . Los datos de ciertos tipos pueden ser modificados después de ser creados, mientras que otros no. En concreto, no es posible modificar los números (enteros o de coma flotante), los booleanos o las cadenas de caracteres, aunque podemos crear otros números nuevos a partir de los existentes. Las tuplas también son inmutables si los elementos que las componen lo son.
Las listas, sin embargo, son mutables, porque podemos añadir o borrar elementos, y modificar sus elementos.
La distinción es importante: ninguna instrucción, ninguna llamada a una función o un método puede modificar un dato inmutable, mientras que sí pueden modificar un dato mutable (por ejemplo, pueden añadir o quitar elementos de una lista, darle la vuelta u ordenar sus elementos).
sage: #Los elementos de una tupla no se pueden cambiar
sage: #y las tuplas no tienen metodos que permitan añadir
sage: #o quitar elementos
sage: tt = (1,2,3)
sage: tt[0] = 4
Traceback (most recent call last):
...
TypeError: 'tuple' object does not support item assignment
sage: tt.append(4)
Traceback (most recent call last):
...
AttributeError: 'tuple' object has no attribute 'append'
sage: #la suma de tuplas da lugar a una tupla distinta de
sage: #las anteriores, pero deja las tuplas sumadas intactas
sage: tt2 = tt + (1,2)
sage: print tt
(1, 2, 3)
sage: def escribe_al_reves(ls):
... '''Escribe los elementos de una lista en orden inverso
...
... Aviso: altera la lista que se pasa como argumento
... '''
... ls.reverse()
... for k in ls:
... print k
sage: #Una llamada a una funcion puede modificar un dato mutable
sage: lista = [1,2,3,4,5]
sage: print lista
sage: escribe_al_reves(lista)
sage: print lista
[1, 2, 3, 4, 5]
5
4
3
2
1
[5, 4, 3, 2, 1]
El conjunto ( set ) es una estructura de datos que permite almacenar datos sin repeticiones.
Las diferencias con una lista son:
- Los elementos de un conjunto no se guardan ordenados y no se puede acceder a ellos con un índice.
- En un conjunto no hay elementos repetidos. Si añadimos un elemento que ya estaba en el conjunto, el conjunto se queda como estaba.
- Los elementos de un conjunto tienen que ser datos inmutables . Los tipos de datos inmutables tienen un número hash que es la base del funcionamiento de los conjuntos.
Podemos crear un conjunto vacío usando el comando
conjunto = set()
o crearlo con los elementos de una lista u otro contenedor de datos:
conjunto = set(contenedor)
Una vez creado, podemos añadir un elemento:
conjunto.add(elemento)
o añadir todos los elementos de otro contenedor:
conjunto.update(contenedor)
o borrar elementos:
conjunto.remove(elemento)
o comprobar si un valor pertenece al conjunto:
elemento in conjunto
A partir de ahí, tenemos a nuestra disposición las siguientes operaciones:
- Unión:
conjunto1 | conjunto2
- Intersección:
conjunto1 & conjunto2
- Diferencia:
conjunto1 - conjunto2
sage: conjunto1 = set([])
sage: conjunto1.add(1)
sage: conjunto1.update([1,2,6,7])
sage: conjunto1.remove(7)
sage: conjunto2 = set([1,2,3,4,1])
sage: #Observamos que el segundo conjunto tiene 4 elementos
sage: #aunque la lista original tuviera 5
sage: print len(conjunto1), len(conjunto2)
3 4
sage: conjunto1 | conjunto2
set([1, 2, 3, 4, 6])
sage: conjunto1 & conjunto2
set([1, 2])
sage: conjunto1 - conjunto2
set([6])
sage: conjunto2 - conjunto1
set([3, 4])
sage: 6 in conjunto2 - conjunto1
False
sage: 7 in conjunto2 - conjunto1
False
No podemos añadir a un conjunto un elemento mutable, como una lista o un conjunto:
sage: conjunto1.add([1,2])
Traceback (most recent call last):
...
TypeError: unhashable type: 'list'
sage: conjunto1.add(conjunto2)
Traceback (most recent call last):
...
TypeError: unhashable type: 'set'
También podemos comprobar si un conjunto es un subconjunto de otro:
conjunto1 <= conjunto2
sage: conjunto1 <= conjunto1 | conjunto2
True
Los elementos del conjunto no están ordenados, de modo que no tiene sentido extraer el elemento i-ésimo de la lista:
sage: conjunto1[2]
Traceback (most recent call last):
...
TypeError: 'set' object does not support indexing
Sin embargo, podemos iterar los elementos del conjunto, aunque no podemos predecir el orden en que aparecerán:
for elemento in conjunto:
operaciones...
sage: conjunto3 = set(('ab','a','b'))
sage: print 'Elementos del conjunto: ',
sage: for numero in conjunto3:
... print numero,
Elementos del conjunto: a ab b
Queremos calcular cuántos números distintos obtenemos al hacer todas las posibles sumas a+b , donde a y b pertenecen a una lista de números. Es fácil almacenar las posibles sumas en una lista, pero entonces estaríamos contando algunos números varias veces:
sumas = []
for k in lista:
for j in lista:
sumas.append(k+j)
Al usar un conjunto, cada posible suma queda en el conjunto final una sola vez .
sage: def sumas(ls):
... '''Devuelve la cantidad de sumas distintas que se pueden obtener
... sumando dos elementos de una lista
... '''
... sumas_posibles = set()
... for a in ls:
... for b in ls:
... sumas_posibles.add(a+b)
... return len(sumas_posibles)
sage: print sumas([1,2,3,4])
sage: print sumas([1,3,5,7])
sage: print sumas([1,2,4,8])
7
7
10
De hecho, usar un conjunto es una forma sencilla de eliminar repeticiones en una lista de elementos:
sage: lista = [3, 3, 2, 1, 1, 6, 1, 2, 3, 3, 7, 3, 7]
sage: conjunto = set(lista)
sage: lista_sin_repeticiones = list(conjunto)
sage: print lista_sin_repeticiones
[1, 2, 3, 6, 7]
Un diccionario es una colección de pares clave-valor. Si una lista es una colección de objetos indexada por números enteros consecutivos, un diccionario permite como clave cualquier tipo de datos inmutable, y los valores pueden ser totalmente arbitrarios.
Los diccionarios ( dict ) tienen una sintaxis especial en python usando las llaves {}.
diccionario = {clave1: valor1, clave2:valor2 ...}
Una vez definido el diccionario, podemos incluir nuevos elementos, borrar y modificar elementos existentes con una sintaxis similar a la que usamos con listas:
diccionario[clave]=valor
del diccionario[otra_clave]
sage: #Asociamos a unas palabras su numero de vocales
sage: diccionario = {'cabeza':3, 'nariz':2, 'mano':4}
sage: print diccionario
sage: #corregimos un error
sage: diccionario['mano']=2
sage: #incluimos un nuevo elemento
sage: diccionario['pie']=2
sage: print diccionario
sage: #Eliminamos un elemento
sage: del diccionario['nariz']
sage: print diccionario
{'mano': 4, 'cabeza': 3, 'nariz': 2}
{'mano': 2, 'pie': 2, 'cabeza': 3, 'nariz': 2}
{'mano': 2, 'pie': 2, 'cabeza': 3}
Si necesitamos sólo las claves, o los valores podemos usar los métodos:
diccionario.keys()
diccionario.values()
sage: print diccionario.keys()
sage: print diccionario.values()
['mano', 'pie', 'cabeza']
[2, 2, 3]
El operador in comprueba si un objeto es una clave del diccionario, pero no si es uno de los valores.
sage: print 'mano' in diccionario
sage: print 'nariz' in diccionario
sage: print 2 in diccionario
True
False
False
Para recorrer los elementos del diccionario, podemos usar un bucle for, que recorre las claves del diccionario, sin seguir ningún orden en particular:
for clave in diccionario:
instrucciones...
sage: for palabra in diccionario:
... print 'La palabra %s tiene %d vocales'%(palabra,diccionario[palabra])
La palabra mano tiene 2 vocales
La palabra pie tiene 2 vocales
La palabra cabeza tiene 3 vocales
A modo de ejemplo, calculamos el mínimo común múltiplo de una lista de números usando su factorización: el mínimo común múltiplo es el producto de todos los primos que aparecen en cualquiera de los números de la lista con el mayor de los exponentes.
sage: def mcm(ls):
... #Primera parte: recopilar los factores
... factores = {}
... for numero in ls:
... for par in list(factor(numero)):
... primo, exponente = par
... if primo not in factores:
... factores[primo] = exponente
... else:
... factores[primo] = max(factores[primo], exponente)
... #Segunda parte: multiplicarlos
... resultado = 1
... for primo in factores:
... resultado = resultado*primo^factores[primo]
... return resultado
sage: #Comparamos con lcm (least common multiple) de SAGE:
sage: print mcm([12,15,15,18])
sage: print lcm([12,15,15,18])
180
180
Podemos construir un diccionario a partir de una lista de tuplas usando el constructor de diccionarios dict . Cada tupla de la lista se incluirá en el diccionario como un par (clave, valor).
sage: lista = [('a',1), ('b',2), ('c',3)]
sage: diccionario = dict(lista)
Si tenemos una lista con las claves y otra con los valores (ambas de igual longitud), podemos construir una lista de tuplas que podemos pasar al constructor dict usando la función zip especialmente diseñada para ese propósito:
sage: lista1 = [(2,3),(2,4),(2,5),(3,4),(3,5),(4,5)]
sage: lista2 = [6, 8, 10, 12, 15, 20]
sage: print lista1
sage: print lista2
sage: lista12 = zip(lista1, lista2)
sage: print lista12
sage: diccionario = dict(lista12)
sage: print diccionario
[(2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
[6, 8, 10, 12, 15, 20]
[((2, 3), 6), ((2, 4), 8), ((2, 5), 10), ((3, 4), 12), ((3, 5), 15), ((4, 5), 20)]
{(4, 5): 20, (2, 3): 6, (2, 5): 10, (3, 4): 12, (2, 4): 8, (3, 5): 15}
Los objetos inmutables tienen un hash: un número entero que representa al objeto, de modo que dos objetos distintos tengan distintos hash, al menos con probabilidad alta.
sage: print hash(0)
sage: print hash(1)
sage: print hash(2)
0
1
2
sage: print hash('a')
sage: print hash('b')
sage: print hash('ab')
12416037344
12544037731
12416074593111939
sage: print hash((0,0))
sage: print hash((0,1))
sage: print hash((0,2))
sage: print hash((1,0))
3713080549408328131
3713080549409410656
3713080549410493181
3713081631936575706
sage: print hash('ab')
sage: print hash((0,2))
12416074593111939
3713080549410493181
Por supuesto que puede haber dos datos distintos con el mismo hash, pero es muy improbable. Exceptuando a los números enteros, el hash tiene una apariencia bastante aleatoria.
sage: N = hash((0,2))
sage: print hash(N)
sage: print hash((0,2))
sage: #Aunque N y (0,2) tengan el mismo hash, los datos siguen siendo distintos
sage: N == (0,2)
1107710717
3713080549410493181
False
Las listas son mutables, y no tienen hash.
sage: print hash([1,])
Traceback (most recent call last):
...
TypeError: unhashable type: 'list'
http://es.wikipedia.org/wiki/Tabla_hash
Los conjuntos y los diccionarios se basan en una tabla de hash , una lista en la que guardamos los elementos usando su hash (o más bien parte del hash) como índice, en vez de insertarlos por orden de llegada.
En python, el índice usado para indexar un elemento en una tabla de tamaño 
son los k últimos bits del hash del elemento. Naturalmente, es posible que dos elementos distintos tengan números hash cuyos k últimos bits coincidan. Cuando introducimos dos elementos en la tabla a los que corresponde el mismo índice, decimos que ha ocurrido una colisión . Sin entrar en detalles sobre cómo se gestionan las colisiones, digamos que cuantas menos colisiones ocurran mejor . Un buen algoritmo de hash tiene dos propiedades básicas: tarda poco tiempo, y produce pocas colisiones.