Subsecciones


5. Estructuras de datos

Este cap�tulo describe con m�s detalle algunas cosas que ya has visto y a�ade algunas cosas nuevas.


5.1 M�s sobre las listas

El tipo de datos ``lista'' tiene algunos m�todos m�s. �stos son todos los m�todos de los objetos lista:

append(x)
A�adir un elemento al final de una lista; es equivalente a a[len(a):] = [x].

extend(L)
Extender la lista concaten�ndole todos los elementos de la lista indicada; es equivalente a a[len(a):] = L.

insert(i, x)
Inserta un elemento en un posici�n dada. El primer argumento es el �ndice del elemento antes del que se inserta, por lo que a.insert(0, x) inserta al principio de la lista y a.insert(len(a), x) equivale a a.append(x).

remove(x)
Elimina el primer elemento de la lista cuyo valor es x. Provoca un error si no existe tal elemento.

index(x)
Devuelve el �ndice del primer elemento de la lista cuyo valor sea x. Provoca un error si no existe tal elemento.

count(x)
Devuelve el n�mero de veces que aparece x en la lista.

sort()
Ordena ascendentemente los elementos de la propia lista (la lista queda cambiada).

reverse()
Invierte la propia lista (la lista queda cambiada).

Un ejemplo que utiliza varios m�todos de la lista:

>>> a = [66.6, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.6), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.6, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.6, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.6]
>>> a.sort()
>>> a
[-1, 1, 66.6, 333, 333, 1234.5]


5.1.1 C�mo usar las listas como pilas

Los m�todos de las listas facilitan mucho usar una lista como una pila, en donde el �ltimo elemento a�adido es el primer elemento recuperado. (``last-in, first-out'', ``�ltimo en llegar, primero en salir''). Para apilar un elemento, usa append(). Para recuperar el elemento superior de la pila, usa pop() sin un �ndice expl�cito. Por ejemplo:

>>> pila = [3, 4, 5]
>>> pila.append(6)
>>> pila.append(7)
>>> pila
[3, 4, 5, 6, 7]
>>> pila.pop()
7
>>> pila
[3, 4, 5, 6]
>>> pila.pop()
6
>>> pila.pop()
5
>>> pila
[3, 4]


5.1.2 C�mo usar las listas como colas

Tambi�n es muy pr�ctico usar una lista como cola, donde el primer elemento que se a�ade a la cola es el primero en salir (``first-in, first-out'', ``primero en llegar, �ltimo en salir''). Para a�adir un elemento al final de una cola, usa append(). Para recuperar el primer elemento de la cola, usa pop() con 0 de �ndice. Por ejemplo:

>>> cola = ["Eric", "John", "Michael"] 
>>> cola.append("Terry")           # llega Terry
>>> cola.append("Graham")          # llega Graham
>>> cola.pop(0)
'Eric'
>>> cola.pop(0)
'John'
>>> cola
['Michael', 'Terry', 'Graham']


5.1.3 Herramientas de programaci�n funcional

Hay tres funciones internas que son muy �tiles al tratar con listas: filter(), map() y reduce().

"filter(funci�n, secuencia)" (filtrar) devuelve una secuencia (del mismo tipo, si es posible) que contiene aquellos elementos de la secuencia para los que funci�n(elemento) resulta verdadero. Por ejemplo, para calcular algunos primos:

>>> def f(x): return x % 2 != 0 and x % 3 != 0
...
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]

"map(funci�n, secuencia)" (transformar) llama a funci�n(elemento) para cada uno de los elementos de la secuencia y devuelve una lista compuesta por los valores resultantes. Por ejemplo, para calcular algunos cubos:

>>> def cubo(x): return x*x*x
...
>>> map(cubo, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

Se puede pasar m�s de una secuencia como par�metro. La funci�n debe tener tantos argumentos como secuencias se le pasan y se llama a la funci�n con el valor correspondiente de cada secuencia de entrada (o None si una secuencia es m�s corta que otra). Si se pasa None como funci�n, se utiliza la funci�n identidad, que devuelve sus argumentos.

Combinando estos dos casos especiales vemos que "map(None, lista1, lista2)" es un modo muy c�modo de convertir una pareja de listas en una lista de parejas. Por ejemplo:

>>> secuencia = range(8)
>>> def cuadrado(x): return x*x
...
>>> map(None, secuencia, map(cuadrado, secuencia))
[(0, 0), (1, 1), (2, 4), (3, 9), (4, 16), (5, 25), (6, 36), (7, 49)]

"reduce(func, secuencia)" (reducir) devuelve un valor simple que se construye llamando a la funci�n binaria func con los dos primeros elementos de la secuencia, luego con el resultado y el siguiente elemento y as� sucesivamente. Por ejemplo, para calcular la suma de los n�meros de 1 a 10:

>>> def suma(x,y): return x+y
...
>>> reduce(suma, range(1, 11))
55

Si s�lo hay un elemento en la secuencia, se devuelve su valor; si la secuencia est� vac�a, se lanza una excepci�n.

Se puede pasar un tercer argumento para indicar el valor inicial. En este caso, se devuelve este valor inicial para la secuencia vac�a y la funci�n se aplica al primer elemento, luego al segundo y as� sucesivamente. Por ejemplo,

>>> def sum(secuencia):
...     def suma(x,y): return x+y
...     return reduce(suma, secuencia, 0)
... 
>>> sum(range(1, 11))
55
>>> sum([])
0

5.1.4 LCs

Las LCs proporcionan un modo conciso de crear listas sin recurrir al uso de map(), filter() ni lambda. La definici�n de lista resultante tiende a ser m�s clara que las listas construidas con los m�todos citados. Cada LC consta de de una expresi�n seguida de una cl�usula for y cero o m�s cl�usulas for o if. La lista resultante se obtiene evaluando la expresi�n en el contexto de las cl�usulas for e if que la siguen. Si la expresi�n debe dar como resultado una tupla, hay que encerrarla entre par�ntesis.

>>> frutafresca = ['  pl�tano', '  mora ', 'fruta de la pasi�n  ']
>>> [arma.strip() for arma in frutafresca]
['pl�tano', 'mora', 'fruta de la pasi�n']
>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]
>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]
>>> [{x: x**2} for x in vec]
[{2: 4}, {4: 16}, {6: 36}]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> [x, x**2 for x in vec]  # error - se necesita un par�ntesis en las tuplas
  File "<stdin>", line 1
    [x, x**2 for x in vec]
               ^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]


5.2 La sentencia del

Hay un modo de eliminar un elemento de una lista dado su �ndice en lugar de su valor: la sentencia del. Tambi�n se puede utilizar para eliminar cortes de una lista (lo que hac�amos antes asignando una lista vac�a al corte). Por ejemplo:

>>> a
[-1, 1, 66.6, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.6, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.6, 1234.5]

del se puede utilizar para eliminar variable completas:

>>> del a

Hacer referencia al nombre a a partir de aqu� provoca un error (al menos hasta que se asigne otro valor al nombre). Veremos otros usos de del m�s adelante.


5.3 Tuplas y secuencias

Hemos visto que las listas y las cadenas tienen muchas propiedades en com�n, por ejemplo, el indexado y el corte. Son dos ejemplos de tipos de datos secuenciales. Como Python es un lenguaje en evoluci�n, se pueden a�adir otros tipos de datos de secuencia. Hay otro tipo de datos secuencial: la tupla.

Una tupla consta de cierta cantidad de valores separada por comas, por ejemplo:

>>> t = 12345, 54321, '�hola!'
>>> t[0]
12345
>>> t
(12345, 54321, '�hola!')
>>> # Se pueden anidar tuplas:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, '�hola!'), (1, 2, 3, 4, 5))

Como puedes observar, en la salida se encierran las tuplas entre par�ntesis, para que las tuplas anidadas se interpreten correctamente. En la entrada los par�ntesis son opcionales, aunque a menudo son necesarios (si la tupla es parte de una expresi�n m�s compleja).

Las tuplas son muy �tiles: Pares de coordenadas (x,y), registros de empleados de una base de datos, etc. Las tuplas, como las cadenas, son inmutables: No es posible asignar un valor a los elementos individuales de una tupla (se puede simular el mismo efecto mediante corte y concatenaci�n, sin embargo). Tambi�n es posible crear tuplas que contengan objetos mutables, por ejemplo, listas.

Un problema especial es la construcci�n de tuplas de 0 � 1 elementos: La sintaxis tiene trucos para resolver esto. Las tuplas vac�as se construyen mediante un par de par�ntesis vac�o y las tuplas de un solo elemento se construyen mediante el valor del elemento seguido de coma (no vale con encerrar el valor entre par�ntesis). Es feo, pero funciona. Por ejemplo:

>>> vacio = ()
>>> singleton = 'hola',    # <-- Observa la coma final
>>> len(vacio)
0
>>> len(singleton)
1
>>> singleton
('hola',)

La sentencia t = 12345, 54321, '�hola!' es un ejemplo de empaquetado de tuplas: los valores 12345, 54321 y '�hola!' se empaquetan en una tupla. Tambi�n se puede realizar la operaci�n inversa:

>>> x, y, z = t

Esto se llama, por supuesto, desempaquetado de secuencias. El desempaquetado de secuencias requiere que el n�mero de variables sea igual al n�mero de elementos de la secuencia. Observa que la asignaci�n m�ltiple s�lo es un efecto combinado del empaquetado de tuplas y desempaquetado de secuencias.

Esto resulta un poco asim�trico, ya que el empaquetado de varios valores siempre resulta en una tupla, aunque el desempaquetado funciona para cualquier secuencia.


5.4 Diccionarios

Otro tipo de dato interno de Python que resulta �til es el diccionario. Los diccionarios aparecen a veces en otros lenguajes como ``memorias asociativas'' o ``matrices asociativas''. A diferencia de las secuencias, que se indexan mediante un rango de n�meros, los diccionarios se indexan mediante claves, que pueden ser de cualquier tipo inmutable. Siempre se puede utilizar cadenas y n�meros como claves. Las tuplas pueden usarse de claves si s�lo contienen cadenas, n�meros o tuplas. Si una tupla contiene cualquier objeto mutable directa o indirectamente, no se puede usar como clave. No se pueden utilizar las listas como claves, ya que las listas se pueden modificar, por ejemplo, mediante el m�todo append() y su m�todo extend(), adem�s de las asignaciones de corte y asignaciones aumentadas.

Lo mejor es pensar en un diccionario como en un conjunto desordenado de parejas clave: valor, con el requisito de que las claves sean �nicas (dentro del mismo diccionario). Una pareja de llaves crea un diccionario vac�o: {}. Si se coloca una lista de parejas clavevalor entre las llaves se a�aden parejas clavevalor iniciales al diccionario. As� es como se presentan los diccionarios en la salida (hay ejemplos dentro de poco).

Las operaciones principales sobre un diccionario son la de almacenar una valor con una clave dada y la de extraer el valor partiendo de la clave. Tambi�n se puede eliminar una pareja clavevalor con del. Si se introduce una clave que ya existe, el valor anterior se olvida. Intentar extraer un valor utilizando una clave no existente provoca un error.

El m�todo keys() de un objeto de tipo diccionario devuelve todas las claves utilizadas en el diccionario, en orden aleatorio (si deseas ordenarlas, aplica el m�todo sort() a la lista de claves). Para comprobar si una clave existe en el diccionario, utiliza el m�todo has_key() del diccionario.

He aqu� un peque�o ejemplo que utiliza un diccionario:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> tel.keys()
['guido', 'irv', 'jack']
>>> tel.has_key('guido')
1


5.5 M�s sobre las condiciones

Las condiciones utilizadas en construcciones while e if descritas anteriormente pueden contener otros operadores, adem�s de las comparaciones.

Los operadores de comparaci�n in (dentro de) y not in (no est� dentro de) comprueban si un valor est� incluido (o no) en una secuencia. Los operadores is (es) y is not (no es) comparan si dos objetos son en realidad el mismo. Esto s�lo tiene importancia en los objetos mutables, como las listas. Todos los operadores de comparaci�n tienen la misma prioridad, que es menor que la de los operadores num�ricos.

Se pueden encadenar las comparaciones: Por ejemplo, a < b == c comprueba si a es menor que b y adem�s si b es igual a c.

Las comparaciones se pueden combinar mediante los operadores l�gicos and (y) y or (o) y la salida de una comparaci�n (o cualquier otra expresi�n l�gica) se puede negar mediante not (no). Todos �stos tienen menor prioridad que los operadores de comparaci�n. Entre ellos, not tiene la prioridad m�s elevada y or la m�s baja, por lo que A and not B or C equivale a (A and (not B)) or C. Por supuesto, se pueden utilizar par�ntesis para expresar un orden de operaci�n concreto.

Los operadores l�gicos and y or se denominan operadores de atajo: Sus argumentos se eval�an de izquierda a derecha y la evaluaci�n se interrumpe tan pronto como queda determinado el valor de salida. Por ejemplo, si A tiene un valor de verdadero pero B es falso, A and B and C no eval�a el valor de la expresi�n C. En general, el valor devuelto por un operador de atajo, cuando se utiliza como valor en general y no como valor l�gico, es el �ltimo argumento evaluado.

Es posible asignar el resultado de una comparaci�n u otra expresi�n l�gica a una variable. Por ejemplo:

>>> cadena1, cadena2, cadena3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = cadena1 or cadena2 or cadena3
>>> non_null
'Trondheim'

Observa que en Python, al contrario que en C, no puede haber asignaci�n dentro de una expresi�n. Los programadores en C pueden quejarse de esto, pero evita una causa com�n problemas hallados en los programas en C: teclear = en una expresi�n en la que se quer�a decir ==.


5.6 Comparaci�n entre secuencias y otros tipos

Los objetos de secuencia se pueden comparar con otros objetos del mismo tipo de secuencia. La comparaci�n utiliza ordenaci�n lexicogr�fica: Primero se comparan los dos primeros elementos, si estos difieren ya est� determinado el valor de la comparaci�n, si no, se comparan los dos elementos siguientes de cada secuencia y, as� sucesivamente, hasta que se agota alguna de las dos secuencias. Si alguno de los elementos que se compara es �l mismo una secuencia, se lleva a cabo una comparaci�n lexicogr�fica anidada. Si todos los elementos son iguales, se considera que las secuencias son iguales. Si una de las secuencias es igual a la otra truncada a partir de cierto elemento, la secuencia m�s corta de las dos es la menor. La ordenaci�n lexicogr�fica para las cadenas utiliza el orden de los c�digos ASCII de sus caracteres. He aqu� ejemplos de comparaciones entre secuencias del mismo tipo:

(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

Observa que es legal comparar objetos de tipos diferentes. El resultado es determin�stico pero arbitrario: los tipos se ordenan por su nombre. De este modo, una lista siempre es menor que una cadena, una cadena siempre es menor que una tupla, etc. Los valores num�ricos de tipos diferentes se comparan por su valor num�rico, por lo que 0 es igual a 0.0, etc.5.1



Notas al pie

... etc.5.1
Las reglas de comparaci�n entre objetos de tipos diferentes no son fiables. Pueden cambiar en versiones futuras del lenguaje.

Ver Sobre este documento... para obtener informaci�n sobre sugerencias.