how to think like a computer scientist

LOGO

Juan G. Vélez RodríguezJoane M. De Jesús Dátiz

23 de junio de 2010

How to Think Like a Computer Scientist

Capítulo 6: “Interation”

Multiple Assignment

Podemos asignar distintos valores a una misma variable.

Es legal asignarle el mismo nombre a diferentes variables ya que al hacerlo, la variable deja de hacer referencia al valor anterior (valor original) y comienza a referirse a un nuevo valor.

Ejemplo

bruce = 5print bruce, bruce = 7print bruce

La coma se interpone y toma prioridad ante el “new line” para que los resultados queden uno al lado del otro y no en distintas líneas.

Resultado en la Pantalla:5 7

Diagrama de Estado

bruce 5

7

Deja de ser un 5 para ser un 7.

Es importante recalcar que las igualdades en Matemáticas son conmutativas pero la asignación de variables en Python no lo son.

Por ejemplo, en Matemáticas si a = 7 entonces 7 = a.

En Phyton es legal decir que a = 7 pero decir que 7 = a no lo es.

The While Statement (Mientras)

Las computadoras realizan tareas repetitivas.

Repetir tareas idénticas es una tarea que las computadoras realizan bastante bien, algo que los seres humanos no realizarían muy bien.

Estas repeticiones se conocen como “Iteration”.

Ejemplo de un While

def countdown (n):while n> 0:

print nn = n-1

print “Blastoff!”

Esta función continuará mostrando el valor de n y lo va a reducir de uno en uno hasta llegar a 0 que es cuando el programa termina y muestra la palabra Blastoff!.

Lo que ocurre en el While es lo siguiente:

1. Se evalúa la condición, 0 ó 12. Si la condición es falsa (0), se sale del

While y continúa con el próximo estado.

3. Si la condición es cierta (1), se ejecutan cada uno de los estados en el “body” y se regresa al paso 1.

El “body” o cuerpo consiste de todos los estados bajo el encabezamiento que contienen la misma alineación, “tabs”, dentro del loop.

Loop (Lazo)

Este tipo de estado se conoce también como un “loop” debido a que luego del tercer paso, regresa nuevamente al comienzo de la función.

Notemos que si la condición es falsa desde el comienzo, los estados dentro del lazo no serán ejecutados pues no será necesario.

El cuerpo del lazo debe cambiar el valor de una o más variables para que eventualmente la condición sea falsa y el lazo termine.

Lazo Infinito (Infinite Loop)

Se puede dar el caso en el que un lazo no tenga final y siga repitiéndose para siempre.

Los Científicos de Computadoras comparan esto con las direcciones al usar un “Shampoo”.

Ejemplo: Lavado, enjuague, repetir.

Lazo Infinito (Infinite Loop)

En el caso de la función “countdown”, podemos comprobar que el lazo termina ya que el valor de n es finito, podemos ver que n va decreciendo cada vez que el lazo se ejecuta y eventualemente obtenemos el valor de 0.

Otros casos…

Hay veces que no es tan fácil de mostrar:

def sequence (n):while n != 1:

print n, if n%2 ==0: # n es un número par

n = n/2else: # n es un número

imparn = n*3+1

Cada vez que el programa ejecuta, comprueba si el número es par o impar. Si es par lo divide entre 2. Si es impar, reemplaza el valor por n*3+1.

Debido a que n algunas veces aumenta o disminuye, no hay prueba obvia para decir que n alcanzará el 1 o que el programa termine.

Una de las ventajas que tienen los lazos es que son buenos para generar tablas.

TablasAntes de que existieran las computadoras, las personas tenían que calcular logaritmos, senos, cosenos y otras funciones matemáticas a mano.

Para facilitarse la vida, en los libros de matemáticas se incluían grandes tablas que incluían estos valores.

Crear las tablas era lento y aburrido y podían contener errores.

Ejemplo de Tablas

El siguiente programa muestra una secuencia de valores en la columna de la izquierda y sus logartimos en la columna de la derecha.

x= 1.0while x <10.0:

print x, ‘\t’ , math.log(x)x = x +1.0

Tabla

Si esos valores de la tabla anterior los queremos con un logaritmo de base 2 entonces debemos usar la siguiente fórmula :

Continuación

Si realizamos el siguiente cambio en el código:

print x, ‘/t’, math.log(x)/math.log(2.0)

Obtenemos:

Vimos que los números 1, 2, 4 y 8 son potencias del 2 ya que sus logaritmos de base 2 son números enteros.

Si queremos encontrar otros logaritmos de potencia 2 podemos modificar el programa de ésta manera:

x = 1.0while x < 100.0

print x, ‘/t’, math.log(x)/math.log(2.0)x = x * 2.0

Resultado

Tabla de dos dimensiones

Tabla en la cual se leen los valores en la intersección entre una fila y una columna.

Ejemplo: tabla de multiplicar.

Crearemos una tabla de multiplicar del 1 al 6 utilizando un lazo que imprima los múltiplos de dos en una línea.

i = 1 #counterwhile i <= 6: print 2*1, ‘ ’, i = i + 1print #Resultados: 2, 4, 6, 8, 10, 12

Encapsulación y Generalización

Encapsulación es el proceso de empacar una pieza del código en una función.

Generalización significa tomar algo en específico, como imprimir los múltiplos de 2 y hacerlo más generalizado, como imprimir los múltiplos de cualquier número entero.

Ejemplo

La siguiente función encapsula el lazo anterior y lo generaliza para que imprima los múltiplos de n:

def printMultiples(n):i = 1while I <= 6: print n*i, ‘\t’, i = i + 1

print

Para encapsular, lo que debemos hacer es añadir la primera línea que es la que declara el nombre de la función y la lista de parámetros. Para generalizar, solo reemplazamos el 2 por el parámetro n.

Continuación Encapsulación y Generalización

Si invocamos ésta función con el argumento 2, obtenemos los mismos valores en pantalla. Con el argumento 3 obtenemos:

3, 6, 9, 12, 15, 18 Con el argumento 4 obtenemos:

4, 8, 12, 16, 20, 24

Si invocamos printMultiples en repetidas ocasiones con diferentes argumentos obtenemos una tabla de multiplicar.

Continuación Encapsulación y GeneralizaciónEn ese caso podemos utilizar otro lazo

(Loop):i = 1while i <= 6:

printMultiples(i)i = i + 1

Obtenemos:

Variables Locales

Las variables que han sido definidas dentro de una función no pueden ser accesadas desde afuera de esa función.

Se puede tener múltiples variables con el mismo nombre siempre y cuando no estén dentro de la misma función.

Stack Diagram

Dos variables distintas llamadas i que cambian de valor sin afectarse una con la otra.

Ejemplo de Generalización

Para crear una tabla de multiplicación de cualquier tamaño, sólo hay que añadir un parámetro a printMultTable:

def printMultTable(high):i = 1while i <= high:

printMultiples(i)i = i + 1

Reemplazamos el valor 6 por el de “high”.

Si llamamos “printMultTable ” con el argumento 7 nos muestra:

Funciones

Darle un nombre a una secuencia de estados (statements) hace su programa fácil de leer y de ejecutar.

Dividir un programa en varias funciones nos permite separar el programa en partes, ejecutar ellas por separado y luego adjuntarlas en un solo componente.

Facilitan la recursión y la iteración. (Loops)

Funciones bien diseñadas son útiles para varios programas. Una vez se escribe y se ejecuta alguna, se pueden reusar.

Capítulo 7: “Strings”

Datos

Hasta este punto, hemos visto distintos tipos de datos, por ejemplo, “int”, “float”, “string”.

Los “strings” son cualitativamente distintos de los otros dos tipos de datos ya que estan compuestos de pequeñas piezas– caracteres.

Tipos de datos que contienen piezas pequeñas son conocidos como “compound data types.”

Los corchetes seleccionan un solo caracter del string:>>> fruit = “banana”>>> letter = fruit[1]>>> print letter

La expresión fruit [1] selecciona el caracter en la posición 1 de la palabra fruit.

Cuando “letter” aparece en la pantalla, nos muestra la letra a.

La primera letra de la palabra banana es b, pero esta letra esta en la posición 0 y es por eso que aparece la letra a, que es la que está en la posición 1.

Índice

La expresión que está en corchetes se conoce como índice (index).

Un índice especifica un miembro de un conjunto ordenado, en este caso, el conjunto de caracteres en el string.

El índice indica que caracter es el que queremos, en vez de su nombre. Puede ser un entero.

Length (Longitud)

La función “len” nos devuelve el número de caracteres en un “string”.

>>> fruit = “banana”>>> len(fruit)6

LengthPara obtener el último caracter de un

“string”, debemos restar 1 del “length”

length = len(fruit)last = fruit[length-1]

Si utilizamos índices negativos, contaremos desde el último hasta el primer caracter. Ejemplo: fruit [-1] último caracter, fruit[-2] penúltimo caracter, etc.

Traversal & for Loops

“Traversal” son los recorridos que se hacen a los caracteres de un “string” desde el primero hasta el último, realizando los cambios necesarios a cada uno de los caracteres en ese proceso.

Este proceso es tan común en Python, que existe una alternativa predefinida llamada “for loop”.

Ejemplo de un “for”:for char in fruit:print char

Cada vez que se ejecuta el lazo (loop), el próximo caracter disponible en el “string” es asignado a la variable “char”. El “loop” continúa hasta que no haya mas ningún caracter en el “string”.

String Slices

Un segmento de un “string ” se conoce como un “slice”. Seleccionar un “slice” es similar a seleccionar un caracter.

El operador [n:m] nos devuelve la parte del “string” desde la posición n hasta la posición m.

String SlicesEjemplo:

Si se omite el primer índice, (anterior a la comilla), el “slice” comenzaría al principio del “string”.

>>> fruit = “banana”>>> fruit [:3]‘ban’>>> fruit [3:]‘ana’

Comparación de Strings

Se pueden comparar “strings”. Para hacerlo, veamos el siguiente ejemplo:

if word == “banana”print “Yes, we have bananas!”

Se pueden hacer comparaciones para poner palabras en orden alfabético, pero debemos tener mucho cuidado ya que Python no ve la diferencia entre letras mayúsculas y letras minúsculas. Las letras mayúsculas toman prioridad ante las letras minúsculas.

Immutable Strings

Los “strings” no se pueden modificar luego de ser creados.

Si necesita hacer cambios, lo mejor es crear un nuevo “string” con las variaciones del original.

Función “find”

Es lo contrario del operador [].

En vez de tomar un índice (index) y extraer su correspondiente caracter, lo que hace es tomar el caracter y encuentra el índice donde aparece ese caracter. Si el caracter no aparece, la función nos devuelve un -1.

Conteos (Counter)

Al declararse una variable llamada “count”, ésta se inicializa a 0 y se va incrementando cada vez que se encuentra un ‘a’.

El siguiente programa realiza un conteo dentro de un lazo (loop):

Módulo “String”

Módulo que contiene varias funciones útiles para manipular “strings”.

>>> import string

Incluye una función llamada “find” que hace lo mismo que vimos anteriormente.

Clasificación de Caracteres

Es muy útil examinar un caracter y comprobar si es de letra mayúscula o minúscula, o si es un caracter o un dígito.

El “string” ‘string.lowercase’ contiene todas las letras que el sistema podría considerar letras minúsculas.

El “string” ‘string.uppercase’ contiene todas las letras que el sistema podría considerar letras mayúsculas.

Clasificación de Caracteres

El “string” ‘string.whitespace’ contiene todos los espacios en blanco, incluyendo ‘space’, ‘tab’ (\t) y ‘newline’ (\n).

Capítulo 8: Listas

Listas

Una lista es un conjunto de valores, donde cada valor es identificado por un índice.

Los valores que componen una lista son llamados elementos.

Las listas son similares a los “strings”, que son una cadena de caracteres, a excepción de que los elementos de una lista pueden ser de cualquier tipo.

Las listas y las cadenas de caracteres son llamados secuencias.

8.1 Listas de valores

Hay varias maneras de formar una nueva lista; la forma más simple es encasillar los elementos en unos corchetes ([y]).

Ejemplos: Lista de cuatro enteros [10, 20, 30, 40] Listas de “strings” [“un”, “dos”, ”tres”] Lista dentro de otra lista [“hola”, 2.0, 5, [10,20] ]

Si una lista esta dentro de otra entonces se dice que la lista esta anidada.

Las listas que contienen enteros consecutivos son comunes, por lo que Phyton provee una forma simple para crearlas:

>>> range (1,5)

[1, 2, 3, 4]

La función rango toma dos argumentos y devuelve una lista que contiene todos los enteros desde el primero hasta el segundo, sin incluir el segundo.

Hay dos formas del alcance. Argumento simple: se crea una lista que comienza

en 0.

>>> range(10)[0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Si existe un tercer argumento, este específica el

espacio entre los valores sucesivos, lo que es llamado “step size”.

Ejemplo: Cuenta desde 1 al 10 de 2 en 2.>>>range(1, 10, 2)[1, 3, 5, 7, 9]

Una lista vacía es una lista especial que no contienen elementos.

Este tipo de lista se denota por corchetes [].

Podemos usar todas las formas anteriores de listas para asignar valores a variables.

8.2 Acceso de elementos

La sintaxis para accesar elementos de una lista es igual a la sintaxis utilizada para accesar caracteres de un “string”.

Para esto utilizamos los corchetes [], donde la expresión dentro de los mismos especifica el índice.

Recordemos que los índices comienzan en 0. print numbers[0]

numbers[1] = 5

Los corchetes pueden apareces en cualquier lugar de una expresión.

Cuando estos aparecen en el lado izquierdo de lo asignado, cambia uno de los elementos de la lista, por lo que el enésimo elemento de la lista ”numbers”, que era 123, es ahora 5.

Cualquier expresión con un número entero puede se utilizada como índice. >>> numbers[3-2]

5 >>>numbers[1.0]

TypeError: sequence index must be integer

Sin embargo, si intentamos leer o escribir un elemento que no existe, entonces obtenemos un error al correr el programa. >>> numbers[2] = 5

IndexError: list assignment index out of range

Si un índice tiene un valor negativo, este cuenta desde el final de la lista >>> numbers[-1]

5 >>> numbers[-3]

IndexError: list index out of range

En el ejemplo anterior: numbers[-1] es el último elemento de la lista numbers[-2] es el penúltimo elemento de la lista numbers[-3] no existe en la lista

Es muy común usar un “loop” como el índice de una lista.

Ejemplo:

horsemen = ["war", "famine", "pestilence", "death"]

i = 0while i < 4:print horsemen[i]i = i + 1

Este “while loop” cuenta desde 0 a 4.

Cuando el “loop” de la variable i es 4, la condición falla y el “loop” termina.

Por lo tanto, el cuerpo del “loop” se ejecuta cuando i es 0, 1, 2 y 3.

Cada vez que pasamos por el “loop”, la variable i es utilizada como un índice en la lista, y se imprime el elemento i de la lista en ese momento. (lista de recorrido)

8.3 Largo de la lista

La función “len” devuelve el largo de la lista.

Es buena idea utilizar este valor como el límite superior de un “loop” en lugar de una constante.

En ese caso, si el tamaño de la lista cambia, no tenemos que ir a través del programa cambiando todos los “loops”, pues estos trabajarán correctamente con una lista de cualquier tamaño.

Ejemplo:horsemen = ["war", "famine",

"pestilence", "death"]

i = 0while i < len(horsemen):print horsemen[i]i = i + 1

La última vez que el “loop” fue ejecutado, i es len(horsemen)-1, que es el índice del último elemento.

Cuando i es igual a len(horsemen), la condición falla y el cuerpo del programa no es ejecutado, lo cual es bueno, porque este valor no es un índice legal.

A pesar de que una lista puede contener otra, la lista anidada cuenta solo como un elemento.[’spam!’, 1, [’Brie’, ’Roquefort’, ’Pol le Veq’], [1,

2, 3]]

En este ejemplo el largo de la lista es 4.

8.4 Membrecía de una lista

“in” es un operador “booleano” que prueba la membrecía en una lista.

Además de ser utilizado con “strings”, también se usan con listas y otras secuencias.

Podemos usar “not” en combinación con “in” para probar si un elemento no es miembro de la lista.

El “for loop” también puede ser utilizado con listas.

8.5 Listas y “for loops”La sintaxis general de un “for loop”

es:for VARIABLE in LIST:BODY

Este enunciado es equivalente a :i = 0while i < len(LIST):VARIABLE = LIST[i]BODYi = i + 1

El “for loop” es más conciso porque podemos eliminar el “loop” de la variable i.

8.6 Operaciones con listas

Operador +>>> a = [1, 2, 3]>>> b = [4, 5, 6]>>> c = a + b>>> print c[1, 2, 3, 4, 5, 6]

Operador * Repite una lista el número dado de veces

>>> [1, 2, 3] * 3[1, 2, 3, 1, 2, 3, 1, 2, 3]

8.7 Partes de una lista

Las operaciones de particiones también trabajan con listas.

>>> list = [’a’, ’b’, ’c’, ’d’, ’e’, ’f’]>>> list[1:3][’b’, ’c’]>>> list[:4][’a’, ’b’, ’c’, ’d’]>>> list[3:][’d’, ’e’, ’f’]

Si omitimos el primer índice, la partición comienza desde el principio.

Si omitimos el segundo, la partición va al final.

Si omitimos ambas, la partición es realmente una copia de la lista completa.>>> list[:][’a’, ’b’, ’c’, ’d’, ’e’, ’f’]

8.8 Las listas son mutables

A diferencia de los “strings”, las listas son mutables, lo que quiere decir que podemos cambiar sus elementos.

Usando corchetes al lado izquierdo de la asignación, podemos actualizar uno de los elementos.

Con el operador de partición podemos actualizar varios elementos a la vez.>>> list = [’a’, ’b’, ’c’, ’d’, ’e’, ’f’]>>> list[1:3] = [’x’, ’y’]>>> print list[’a’, ’x’, ’y’, ’d’, ’e’, ’f’]

También podemos remover elementos de una lista asignándoles una lista vacía.>>> list = [’a’, ’b’, ’c’, ’d’, ’e’, ’f’]>>> list[1:3] = []>>> print list[’a’, ’d’, ’e’, ’f’]

Podemos añadir elementos a una lista moviéndolos a una partición vacía.>>> list = [’a’, ’d’, ’f’]>>> list[1:1] = [’b’, ’c’]>>> print list[’a’, ’b’, ’c’, ’d’, ’f’]>>> list[4:4] = [’e’]>>> print list[’a’, ’b’, ’c’, ’d’, ’e’, ’f’]

Eliminación de una lista

Usando particiones para eliminar elementos de una lista puede ser difícil, por lo que entonces estamos propensos a errores.

“del” remueve un elemento de una lista.

Ejemplo:>>> a = [’one’, ’two’, ’three’]>>> del a[1]>>> a[’one’, ’three’]

Como esperamos “del” maneja índices negativos y causa un error en la corrida si el índice esta fuera del alcance.

Podemos usar una partición como un índice para “del”.>>> list = [’a’, ’b’, ’c’, ’d’, ’e’, ’f’]>>> del list[1:5]>>> print list[’a’, ’f’]

8.10 Valores y objetos

Si ejecutamos las siguientes asignaciones:a = "banana"b = "banana“sabemos que a y b se refieren a un “string” con letras “banana”.

Sin embargo, no podemos decir que ambos apuntan al mismo “string”.

Hay dos estados posibles:

En el primer caso, a y b se refieren a dos cosas diferentes que tienen el mismo valor.

En el segundo caso, ambos se refieren a la misma cosa.

Estas “cosas” tienen nombre y se conocen como objetos.

Un objeto es algo a lo que una variable se puede referir.

Cada objeto tiene un identificador único, el que puede ser obtenido con la función “id”.

Imprimiendo el identificador de a y b, podemos decir que ambos se refieren al mismo objeto.>>> id(a)135044008>>> id(b)135044008

De hecho, obtenemos el mismo identificador doble, lo que significa que Phyton solo ha creado un “string”, y a y b se refieren a el.

Las listas se comportan diferente.

Cuando creamos dos listas, tenemos dos objetos:>>> a = [1, 2, 3]>>> b = [1, 2, 3]>>> id(a)135045528>>> id(b)135041704

Entonces el diagrama de estado es el siguiente:

donde a y b tienen el mismo valor pero no se refieren al mismo objeto.

8.11 Alias

Dado que las variables se refieren a objetos, si asignamos una variable a otra, ambas variables se refieren al mismo objeto.>>> a = [1, 2, 3]>>> b = a

En este caso, el diagrama de estado es:

Como la misma lista tiene dos nombres diferentes, a y b, decimos que esta es un alias.

Cambios hechos a un alias afectan al otro.

A pesar de que este comportamiento puede ser beneficioso, en algunos casos puede ser inesperado o indeseable.

En general, es más seguro evitar los alias cuando estamos trabajando con objetos mutables.

Claro que para elementos inmutables, no hay problema porque Phyton es libre de “strings” alias, cuando se presenta la oportunidad de economizar.

8.12 Clonando listas

Si deseamos modificar una lista y a la vez guardar una copia de la lista original, necesitamos ser capaces de crear una copia de la lista misma, no solo una referencia.

A veces este proceso se conoce como clonación, para evitar la ambigüedad del término copia.

La manera más fácil de clonar una lista es usar el operador de partición.>>> a = [1, 2, 3]>>> b = a[:]>>> print b[1, 2, 3]

Tomando cualquier partición de a se crea una nueva lista, que en este caso consiste de la lista completa.

Ahora podemos realizar cualquier cambio a b sin la preocupación de modificar a.>>> b[0] = 5>>> print a[1, 2, 3]

8.13 Parámetros de listas

Pasar una lista como un argumento pasa una referencia a la lista, no una copia de la lista.

Por ejemplo, la función “head” toma una lista como un argumento y devuelve el primer elemento.def head(list):return list[0]

Se utiliza la siguiente forma:>>> numbers = [1, 2, 3]>>> head(numbers)1

El parámetro “list” y la variable “numbers” son alias para el mismo objeto.

El diagrama de estado es:

Como el objeto de la lista es compartido por dos marcos, entonces lo dibujamos entre ambos.

Si una función modifica el parámetro de una lista, entonces se elimina el cambio.

Por ejemplo, “deleteHead” remueve el primer elemento de una lista.def deleteHead(list):del list[0]

Entonces mostramos como se utiliza el comando “deleteHead”.>>> numbers = [1, 2, 3]>>> deleteHead(numbers)>>> print numbers[2, 3]

Si una función devuelve una lista, esta devuelve una referencia a la lista.

Por ejemplo, “tail” devuelve una lista que contiene todo menos el primer elemento de la lista.def tail(list):return list[1:]

“tail” funciona de la siguiente forma:>>> numbers = [1, 2, 3]>>> rest = tail(numbers)>>> print rest[2, 3]

Como el valor devuelto fue creado por el operador de particiones, es una lista nueva. Por lo que haber creado “rest” no tiene ningún efecto en “numbers”.

8.14 Listas anidadas

Una lista anidada es una lista que aparece como un elemento de otra lista.

En esta lista, el tercer elemento es una lista anidada:>>> list = ["hello", 2.0, 5, [10, 20]]

Si imprimimos “list[3]”, obtenemos “[10, 20]”.

8.15 Matrices

Las listas anidadas también son utilizadas para representar matrices.

Por ejemplo, la matriz puede ser representada como:>>> matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

“matrix” es una lista con tres elementos, donde cada elemento es una fila de la matriz.

Podemos seleccionar una fila entera de una matriz de la siguiente forma:>>> matrix[1][4, 5, 6]

Podemos extraer un solo elemento de la matriz usando un doble índice:>>> matrix[1][1]5

El primer índice selecciona una fila, el segundo índice selecciona una columna.

8.16 Listas y “strings”

Dos de las funciones más utilizadas en el módulo “string” envuelve listas de “strings”.

La función “split” rompe un “string” como una lista de palabras. Cada espacio en blanco entre los caracteres es

considerado el límite de una palabra.

>>> import string

>>> song = "The rain in Spain...">>> string.split(song)[’The’, ’rain’, ’in’, ’Spain...’]

Existe un argumento opcional llamado delimitador, el cual puede ser usado para especificar cuales caracteres son utilizados como límites de las palabras.

El siguiente ejemplo usa el “string” ai como el delimitador>>> string.split(song, ’ai’)[’The r’, ’n in Sp’, ’n...’]

Notemos que el delimitador no aparece en la lista.

Esta toma una lista de “strings” y une los elementos con un espacio entre cada par.>>> list = [’The’, ’rain’, ’in’, ’Spain...’]>>> string.join(list)’The rain in Spain...’

Como “split”, “join” toma un delimitador opcional que es insertado entre los elementos.>>> string.join(list, ’_’)’The_rain_in_Spain...’

Capítulo 9: Tuplas

9.1 Mutabilidad y tuplas

Un “string” está compuesto de caracteres; mientras una lista está compuesta de elementos de cualquier tipo.

Una de las diferencias más notables es que los elementos de una lista pueden ser modificados, pero los caracteres de un “string” no.

En otras palabras, los “strings” son inmutables y las listas mutables.

En Phyton también existen las tuplas, la cual es similar a una lista con la excepción de que es inmutable.

Sintácticamente, una tupla es una lista de valores separados por comas.

Ejemplo:>>> tuple = ’a’, ’b’, ’c’, ’d’, ’e’

Aunque no es necesario, convencionalmente las tuplas se escriben entre paréntesis.>>> tuple = (’a’, ’b’, ’c’, ’d’, ’e’)

Para crear un tupla con un solo elemento, tenemos que incluir una coma al final.>>> t1 = (’a’,)>>> type(t1)<type ’tuple’>

Sin la coma, Phyton trata (‘a’) como un “string” entre paréntesis.>>> t2 = (’a’)>>> type(t2)<type ’str’>

Si dejamos la sintaxis a un lado, las operaciones en las tuplas son igual a las operaciones en las listas.

El operador índice selecciona un elemento de una tupla.>>> tuple = (’a’, ’b’, ’c’, ’d’, ’e’)>>> tuple[0]’a’

El operador partición selecciona el alcance de los elementos.>>> tuple[1:3](’b’, ’c’)

Si intentamos modificar uno de los elementos de la tupla obtenemos un error.>>> tuple[0] = ’A’TypeError: object doesn’t support item assignment

Como no podemos modificar los elementos de una tupla, podemos reemplazarlo con una diferente.>>> tuple = (’A’,) + tuple[1:]>>> tuple(’A’, ’b’, ’c’, ’d’, ’e’)

9.2 Asignando tuplas

A veces es bueno cambiar los valores de dos variables.

Con la forma convencional de asignación, teníamos que utilizar una variable temporera.

Ejemplo para cambiar a y b:>>> temp = a>>> a = b>>> b = temp

Si tenemos que hacer esto a menudo, este proceso sería engorroso.

Phyton provee una forma de asignación de tuplas que resuelve este problema:>>> a, b = b, a

El lado izquierdo es la tupla de las variables y el lado derecho es el de los valores.

Cada valor es asignado a su variable correspondiente.

Todas las expresiones en el lado derecho son evaluadas antes de cualquier asignación.

Esto hace que la asignación de tuplas sea versátil.

El número de variables en el lado izquierdo y el número de variables en el derecho tienen que ser iguales.

Ejemplo:

>>> a, b, c, d = 1, 2, 3ValueError: unpack tuple of wrong size

9.3 Tuplas como valores devueltos

Las funciones pueden devolver tuplas como respuestas.

Por ejemplo, podemos escribir una función que cambia dos parámetros:def swap(x, y):return y, x

Después podemos asignar el valor devuelto a una tupla con dos variables:a, b = swap(a, b)

En este caso, no es ventajoso realizar una función “swap”.

De hecho, existe un peligro en intentar encapsular “swap”, el cual es el siguiente error:def swap(x, y): # incorrect versionx, y = y, x

Si llamamos la función de la siguiente manera:swap(a, b)

entonces a y x son alias para el mismo valor.

Cambiando x dentro de “swap” hace que x se refiera a un valor diferente, pero no tiene efecto en “in_main_”.

Similarmente, cambiar y no tiene ningún efecto en b.

Esta función corre sin producir un mensaje de error, pero no realiza lo que se pretende.

Este es un buen ejemplo para un error de semántica.

9.4 Números aleatorios

Muchos programas de computadoras hacen lo mismo cada vez que son ejecutados, por lo que podemos llamarlos determinísticos.

El determinismo es usualmente bueno, porque esperamos que el mismo cálculo arroje el mismo resultado.

Para algunas aplicaciones, queremos que la computadora sea impredecible. Ejemplo: Juegos

Hacer un programa no determinístico no es sencillo, pero existen formas para que lo sea lo menos posible.

Una de las formas es generando números aleatorios y utilizarlos para determinas la salida del programa.

Phyton provee una función pre-construida que genera números seudo-aleatorios, los cuales no son completamente aleatorios en sentido matemático, pero para nuestros propósitos si lo son.

El módulo “random” contiene una función llamada “random” que devuelve un número decimal entre 0.0 y 1.0.

Cada vez que realizamos la operación, obtenemos el siguiente número en una serie larga.

Ejemplo:import randomfor i in range(10):x = random.random()print x

9.2 Lista de números aleatoriosEl primer paso es generar una lista de

valores aleatorios.

“randomList” toma un argumento entero y devuelve una lista de números aleatorios con el largo dado.

Se comienza con una lista de n ceros.

Cada vez que pasamos a través del “loop”, este reemplaza uno de los elementos con un número aleatorio.

El valor devuelto es una referencia a la lista completa.def randomList(n):s = [0] * nfor i in range(n):s[i] = random.random()return s

Los números generados por “random” son distribuidos uniformemente, lo que significa que cada valor es igualmente probable.

Si dividimos el alcance de los valores posibles en “buckets” del mismo tamaño, y contamos el número de veces que el valor aleatorio cae en cada “bucket”, tendremos seguramente el mismo número en cada uno.

Podemos probar esta teoría escribiendo un programa que divida el alcance en “buckets” y cuente el número de valores en cada uno.

9.6 Contando

Una buena propuesta para problemas como este es dividir el problema en partes y buscar soluciones computacionales a estos problemas.

En este caso, deseamos recorrer una lista de números y contar el número de veces que un valor cae en el rango dado.

Podemos proceder copiando el programa y adaptándolo para el problema actual.

El programa original es:count = 0for char in fruit:if char == ’a’:count = count + 1print count

Este primer paso es para reemplazar “fruit” with “t” y “char” con “num”.

Esto no cambia el programa, solo lo hace más fácil para leer.

El segundo paso es cambiar la prueba.

No tenemos la intención de encontrar valores, deseamos saber si “num” esta entre los valores “low” y “high”.

Ejemplo:count = 0for char in fruit:if char == ’a’:count = count + 1print count

El último paso es encapsular este código en la función “inBucket”.

Los parámetros son la lista y los valores “low” y “high”.def inBucket(t, low, high):count = 0for num in t:if low < num < high:count = count + 1return count

Copiando y modificando un programa existente, somos capaces de escribir esta función rápidamente y economizar tiempo.

Este plan de desarrollo se conoce como pareo de patrones.

Si trabajamos en un problema que hemos resuelto anteriormente, reusamos la solución.

9.7 Muchos “buckets”Si el número de “buckets” aumenta,

la función “inBucket” se vuelve un poco difícil.

Con dos “buckets”:low = inBucket(a, 0.0, 0.5)high = inBucket(a, 0.5, 1)

Con cuatro “buckets” se vuelve engorroso:bucket1 = inBucket(a, 0.0, 0.25)bucket2 = inBucket(a, 0.25, 0.5)bucket3 = inBucket(a, 0.5, 0.75)bucket4 = inBucket(a, 0.75, 1.0)

Existen dos problemas. Tenemos que declarar un nombre nuevo para cada

resultado de la variable. Tenemos que calcular el rango para cada “bucket”.

Podemos resolver el segundo problema primero. Si el número de “buckets” es “numBuckets”,

entonces el ancho de cada “bucket” es “1.0/numBuckets”.

Usamos un “loop” para calcular el rango de cada “bucket”.

La variable “loop”, i, cuenta desde 0 a “numBuckets-1”bucketWidth = 1.0 / numBucketsfor i in range(numBuckets):low = i * bucketWidthhigh = low + bucketWidthprint low, "to", high

Para calcular el limite inferior para cada “bucket”, multiplicamos la variable “loop” por el ancho del “bucket”.

El limite superior es la suma del inferior y el “bucketWidth”.

Ejemplo:Con “numBuckets=8”, el “output” es:

0.0 to 0.1250.125 to 0.250.25 to 0.3750.375 to 0.50.5 to 0.6250.625 to 0.750.75 to 0.8750.875 to 1.0

Podemos confirmar que cada “bucket” tiene el mismo ancho, que no se solapan, y que cubren completamente el alcance desde 0.0 a 1.0.

Para el primer problema, necesitamos una forma para guardar ocho enteros, usando la variable “loop” para indicar uno a la vez.

Tenemos que crear una lista “bucket” fuera del “loop”, porque solo queremos recorrerla una vez

Dentro del “loop”, llamaremos el “inBucket” repetidamente y actualizaremos el enésimo elemento i de la lista.

Ejemplo:numBuckets = 8buckets = [0] * numBucketsbucketWidth = 1.0 / numBucketsfor i in range(numBuckets):low = i * bucketWidthhigh = low + bucketWidthbuckets[i] = inBucket(t, low, high)print buckets

Con una lista de 1000 valores, el código produce la siguiente lista “bucket”:[138, 124, 128, 118, 130, 117, 114, 131]

Estos números están bien cerca de 125, que es lo que esperamos.

Al estar tan cerca podemos creer que el generador de números aleatorios está funcionando.

9.8 Solución por una pruebaA pesar de que el programa funciona,

no es tan eficiente como podría ser.

Cada vez que se llama el “inBucket”, se recorre la lista completa.

Si el numero de “buckets” aumenta, también el número de recorridas.

Sería mejor si pasamos una sola vez por la lista y computamos el índice del “bucket” en el cual falla para cada valor.

Luego podemos aumentar el contador apropiado.

Deseamos tomar un valor en el rango de 0.0 a 1.0 para calcular el índice del “bucket” en el cual se falla.

Dado que el problema es el inverso del problema anterior, podemos pensar que debemos dividir por el “bucketWidth” en vez de multiplicar, como en el ejemplo anterior.

Dado que “bucketWidth”=“1.0/numBuckets”, dividiendo por “bucketWidth” es lo mismo que multiplicar por “numBuckets”.

Si multiplicamos un número en el rango 0.0 a 1.0 por “numBuckets”, obtenemos un número en el rango desde 0.0 hasta “numBuckets”.

Si redondeamos ese número al entero menor, obtenemos exactamente lo que estamos buscando, un índice del “bucket”.numBuckets = 8buckets = [0] * numBucketsfor i in t:index = int(i * numBuckets)buckets[index] = buckets[index] + 1

Usamos le función “int” para convertir un número decimal en un entero.

Una lista que cuenta el número de valores en cada rango se conoce como un histograma, el cual se realiza con la función “histogram”.