Conjuntos y diccionarios ======================== Tipos de datos mutables e inmutables :::::::::::::::::::::::::::::::::::: 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] .. index:: set Conjuntos ::::::::: 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 Ejemplo: conjunto de sumas ~~~~~~~~~~~~~~~~~~~~~~~~~~ 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 Usar un conjunto para eliminar elementos repetidos de una lista ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 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] .. index:: dict Diccionarios :::::::::::: 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 Ejemplo: mínimo común múltiplo ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 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 .. index:: zip Construir diccionarios a partir de listas ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 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} Como funcionan los conjuntos y los diccionarios ::::::::::::::::::::::::::::::::::::::::::::::: .. index:: hash Hash ~~~~ 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' Tabla hash ~~~~~~~~~~ http://es.wikipedia.org/wiki/Tabla_hash .. image:: b2s1_media/350px-Tabla_hash1.png :align: center 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 :math:`2^k` 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.