Un buen enfoque sobre problemas como este es dividir el problema en subproblemas que encajen en un esquema computacional que hayamos visto antes.

En este caso, queremos recorrer una lista de números y contar el numero de veces que un valor cae en un intervalo dado.

Eso nos suena. En la Sección 7.8 escribimos un programa que recorr³a una cadena de texto y contaba el numero
de veces que aparecía una letra determinada.

Así, podemos hacerlo copiando el programa viejo y adaptándolo al problema actual. El programa original era:

   1: cuenta = 0

   2: for car in fruta:

   3:     if car == 'a':

   4:         cuenta = cuenta + 1

   5: print cuenta

El primer paso es sustituir fruta con lista y car con núm. Esto no cambia el programa, solo lo hace mas legible.

El segundo paso es cambiar la comprobación. No estamos interesados en encontrar letras. Queremos ver si num esta entre los valores de mínimo y máximo.

   1: cuenta = 0

   2: for num in lista

   3:     if minimo < num < maximo:

   4:         cuenta = cuenta + 1

   5: print cuenta

El ultimo paso es encapsular este código en una función llamada enElBalde.

Los parámetros son la lista y los valores minimo y maximo.

   1: def enElBalde(lista, minimo, maximo):

   2:     cuenta = 0

   3:     for num in lista:

   4:             if minimo < num < maximo:

   5:                 cuenta = cuenta + 1

   6:     return cuenta

Copiar y modificar un programa existente nos facilita escribir esta función rápidamente y nos ahorra un montón de tiempo de depuración. Este plan de desarrollo se llama coincidencia de esquemas. Si se encuentra trabajando en un
problema que ya soluciono, reutilice la solución.

Tal como aumenta el numero de baldes, enElBalde se hace un tanto difícil de manejar. Con dos baldes, no esta mal:

   1: bajo = enElBalde(a, 0.0, 0.5)

   2: alto = enElBalde(a, 0.5, 1)

   1: balde1 = enElBalde(a, 0.0, 0.25)

   2: balde2 = enElBalde(a, 0.25, 0.5)

   3: balde3 = enElBalde(a, 0.5, 0.75)

   4: balde4 = enElBalde(a, 0.75, 1.0)

Hay dos problemas. Uno es que tenemos que inventar nuevos nombres de variables para cada resultado. El otro es que tenemos que calcular el intervalo de cada balde.

Empezaremos por solucionar el segundo problema. Si el numero de baldes es numBaldes, la anchura de cada balde es 1.0 / numBaldes.

Usaremos un bucle para calcular el intervalo de cada balde. La variable del bucle, i, cuenta de 1 a numBaldes-1:

   1: anchuraBalde = 1.0 / numBaldes

   2: for i in range(numBaldes):

   3: minimo = i * anchuraBalde

   4: maximo = minimo + anchuraBalde

   5: print minimo, "hasta", maximo

Para calcular el límite inferior de cada balde, multiplicamos la variable de bucle por la anchura de balde. El límite superior esta a tan solo una anchuraBalde.

Con numBaldes = 8, la salida es:

   1: 0.0 hasta 0.125

   2: 0.125 hasta 0.25

   3: 0.25 hasta 0.375

   4: 0.375 hasta 0.5

   5: 0.5 hasta 0.625

   6: 0.625 hasta 0.75

   7: 0.75 hasta 0.875

   8: 0.875 hasta 1.0

Puede confirmar que todos los bucles tienen la misma anchura, que no se solapan y que cubren todo el intervalo entre 0,0 y 1,0.

Volvamos ahora al primer problema. Necesitamos un modo de almacenar ocho enteros, usando la variable de bucle para señalarlos uno por uno. En estos momentos debería usted estar pensando “Lista!”.

Debemos crear la lista de baldes fuera del bucle, porque solo queremos hacerlo una vez. Dentro del bucle, podemos llamar repetidamente a enElBalde y actualizar el i-esimo elemento de la lista:

   1: numBaldes = 8

   2: baldes = [0] * numBaldes

   3: anchuraBalde = 1.0 / numBaldes

   4: for i in range(numBaldes):

   5:     minimo = i * anchuraBalde

   6:     maximo = minimo + anchuraBalde

   7:     baldes[i] = enElBalde(lista, minimo, maximo)

   8: print baldes

   1: [138, 124, 128, 118, 130, 117, 114, 131]

Estos números son razonablemente próximos a 125, que es lo que esperábamos.

Por lo menos, están lo bastante cerca como para que podamos pensar que el generador de números aleatorios funciona.

Como ejercicio, compruebe esta función con listas mas largas, y vea
si el numero de valores en cada balde tiende a equilibrarse.

Aunque este programa funciona, no es tan eficiente como podría ser. Cada vez que llama a enElBalde recorre la lista entera. Con el aumento del numero de baldes, llega a ser un montón de recorridos.

Sería mejor hacer una sola pasada por la lista y calcular para cada valor el índice del balde en el que cae. Luego podemos incrementar el contador apropiado.

En la sección anterior tomamos un índice, i, y lo multiplicamos por la anchuraBalde para hallar el límite inferior de un balde dado. Ahora queremos tomar un valor del intervalo 0,0 a 1,0 y hallar el índice del balde en el que cae.

Como el problema es el inverso del anterior, podemos suponer que deberíamos por anchuraBalde en lugar de multiplicar.

La suposición es correcta.

Como anchuraBalde = 1.0 / numBaldes, dividir por anchuraBalde es lo mismo que multiplicar por numBaldes. Si multiplicamos un numero del intervalo que va de 0,0 a 1,0 por numBaldes, obtenemos un numero del intervalo entre 0,0 y numBaldes. Si redondeamos ese numero al entero inferior obtendremos exactamente lo que estamos buscando, un índice de balde:

   1: numBaldes = 8

   2: baldes = [0] * numBaldes

   3: for i in lista:

   4:     indice = int(i * numBaldes)

   5:     baldes[indice] = baldes[indice] + 1

Usamos la función int para convertir un numero en coma flotante en un entero.

¿Es posible que este calculo genere un índice que este fuera del intervalo (tanto negativo como mayor que len(baldes)-1)?
Una lista como baldes que contiene conteos del numero de valores en cada intervalo se llama histograma.

Como ejercicio, escriba una función llamada histograma que tome como parámetros una lista y un numero de baldes y devuelva un histograma con el numero dado de baldes.

tipo inmutable: Un tipo en el cual los elementos no se puede modificar. Las asignaciones de elementos o porciones de tipos inmutables provocan un error.

tipo mutable: Un tipo de datos en el cual los elementos pueden ser modificados. Todos los tipos mutables son compuestos. Las listas y diccionarios son tipos de datos mutables, las cadenas y las tuplas no.

tupla: Un tipo de secuencia que es similar a una lista excepto en que es inmutable. Las tuplas se pueden usar donde quiera que se necesite un tipo inmutable, como puede ser la clave de un diccionario.

asignación de tuplas: Una asignación de todos los elementos de una tupla usando una única sentencia de asignación. La  asignación de tuplas sucede mas bien en paralelo que secuencialmente, haciéndola útil para intercambiar valores.

determinista: Un programa que hace lo mismo todas las veces que se ejecuta.

pseudoaleatorio: Una secuencia de números que parece ser aleatoria pero que en realidad es el resultado de un calculo determinista.

histograma: Una lista de enteros en la que cada elemento cuenta el numero de veces que ocurre algo.

coincidencia de esquemas: Un plan de desarrollo de programas que implica la identificación de un esquema computacional conocido y el copiado de la solución para un problema similar.

Diccionarios

Los tipos compuestos que ha visto hasta ahora (cadenas, listas y tuplas) usan enteros como índices. Si intenta usar cualquier otro tipo como índice provocara un error.

Los diccionarios son similares a otros tipos compuestos excepto en que pueden usar como índice cualquier tipo inmutable. A modo de ejemplo, crearemos un diccionario que traduzca palabras inglesas al español. En este diccionario, los índices son strings (cadenas).

Una forma de crear un diccionario es empezar con el diccionario vacío y añadir elementos. El diccionario vacío se expresa como {}:

   1: >>> ing_a_esp = {}

   2: >>> ing_a_esp['one'] = 'uno'

   3: >>> ing_a_esp['two'] = 'dos'

La primera asignación crea un diccionario llamado ing a esp; las otras asignaciones añaden nuevos elementos al diccionario. Podemos presentar el valor actual del diccionario del modo habitual:

   1: >>> print ing_a_esp

   2: {'one': 'uno', 'two': 'dos'}

Los elementos de un diccionario aparecen en una lista separada por comas.

Cada entrada contiene un índice y un valor separado por dos puntos (:). En un diccionario, los índices se llaman claves, por eso los elementos se llaman pares clave-valor.

Otra forma de crear un diccionario es dando una lista de pares clave-valor con la misma sintaxis que la salida del ejemplo anterior:

   1: >>> ing_a_esp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}

   1: >>> print ing_a_esp

   2: {'one': 'uno', 'three': 'tres', 'two': 'dos'}

¡Los pares clave-valor no están en orden! Afortunadamente, no necesitamos preocuparnos por el orden, ya que los elementos de un diccionario nunca se indexan con índices enteros. En lugar de eso, usamos las claves para buscar los valores correspondientes:

   1: >>> print ing_a_esp['two']

   2: 'dos'

La clave ‘two’ nos da el valor ‘dos’ aunque aparezca en el tercer par clave-valor.

La sentencia del elimina un par clave-valor de un diccionario. Por ejemplo, el diccionario siguiente contiene los nombres de varias frutas y el numero de esas frutas en el almacén:

   1: >>> inventario = {'manzanas': 430, 'bananas': 312,

   2: ... 'naranjas': 525, 'peras': 217}

   3: >>> print inventario

   4: {'naranjas': 525, 'manzanas': 430, 'peras': 217, 'bananas': 312}

   1: >>> del inventario['peras']

   2: >>> print inventario

   3: {'naranjas': 525, 'manzanas': 430, 'bananas': 312}

O si esperamos recibir mas peras pronto, podemos simplemente cambiar el inventario asociado con las peras:

   1: >>> inventario['peras'] = 0

   2: >>> print inventario

   3: {'naranajas': 525, 'manzanas': 430, 'peras': 0, 'bananas': 312}

La función len también funciona con diccionarios; devuelve el numero de pares clave-valor:

   1: >>> len(inventario)

   2: 4

Un metodo es similar a una función, acepta parámetros y devuelve un valor, pero la sintaxis es diferente. Por ejemplo, el método keys acepta un diccionario y devuelve una lista con las claves que aparecen, pero en lugar de la sintaxis de la función keys(ing a esp), usamos la sintaxis del metodo ing a esp.keys().

   1: >>> ing_a_esp.keys()

   2: ['one', 'three', 'two']

Esta forma de notación de punto especifica el nombre de la función, keys, y el nombre del objeto al que se va a aplicar la función, ing a esp. Los paréntesis indican que este metodo no admite parámetros.

La llamada a un metodo se denomina invocación; en este caso, diríamos que estamos invocando keys sobre el objeto ing a esp.

El método valúes es similar; devuelve una lista de los valores del diccionario:

   1: >>> ing_a_esp.values()

   2: ['uno', 'tres', 'dos']

El metodo ítems devuelve ambos, una lista de tuplas con los pares clave-valor del diccionario:

   1: >>> ing_a_esp.items()

   2: [('one','uno'), ('three', 'tres'), ('two', 'dos')]

La sintaxis nos proporciona información muy útil acerca del tipo de datos. Los corchetes indican que es una lista. Los paréntesis indican que los elementos de la lista son tuplas.

Si un método acepta un argumento, usa la misma sintaxis que una llamada a una función. Por ejemplo, el metodo has key acepta una clave y devuelve verdadero (1) si la clave aparece en el diccionario:

   1: >>> ing_a_esp.has_key('one')

   2: 1

   3: >>> ing_a_esp.has_key('deux')

   4: 0

Si usted invoca un metodo sin especificar un objeto, provoca un error. En este caso, el mensaje de error no es de mucha ayuda:

   1: >>> has_key('one')

   2: NameError: has_key

Debe usted estar atento a los alias a causa de la mutabilidad de los diccionarios.

Si dos variables se refieren al mismo objeto los cambios en una afectan a la otra.

Si quiere modificar un diccionario y mantener una copia del original, use el metodo copy. Por ejemplo, opuestos es un diccionario que contiene pares de opuestos:

   1: >>> opuestos = {'arriba': 'abajo', 'derecho': 'torcido',

   2: ...             'verdadero': 'falso'}

   3: >>> alias = opuestos

   4: >>> copia = opuestos.copy()

alias y opuestos se refieren al mismo objeto; copia hace referencia a una copia nueva del mismo diccionario. Si modificamos alias, opuestos también resulta cambiado:

   1: >>> alias['derecho'] = 'sentado'

   2: >>> opuestos['derecho']

   3: 'sentado'

   1: >>> copia['derecho'] = 'privilegio'

   2: >>> opuestos['derecho']

   3: 'sentado'

En la Sección 8.14 usamos una lista de listas para representar una matriz. Es una buena opción para una matriz en la que la mayoría de los valores es diferente de cero, pero piense en una matriz como esta:

0 2 0 0 0
0 0 0 1 0
0 0 0 0 0
0 0 0 3 0
0 0 0 0 0

La representación de la lista contiene un montón de ceros:

 

   1: matriz = [ [0,0,0,1,0],

   2:            [0,0,0,0,0],

   3:            [0,2,0,0,0],

   4:            [0,0,0,0,0],

   5:            [0,0,0,3,0] ]

Una posible alternativa es usar un diccionario. Como claves, podemos usar tuplas que contengan los números de fila y columna. Esta es la representación de la misma matriz por medio de un diccionario:

   1: matriz = {(0,3): 1, (2, 1): 2, (4, 3): 3}

Solo hay tres pares clave-valor, una para cada elemento de la matriz diferente de cero. Cada clave es una tupla, y cada valor es un entero.

Para acceder a un elemento de la matriz, podemos usar el operador []:

   1: matriz[0,3]

   2: 1

Fíjese en que la sintaxis para la representación por medio del diccionario no es la misma de la representación por medio de la lista anidada. En lugar de dos índices enteros, usamos un índice que es una tupla de enteros.

Hay un problema. Si apuntamos a un elemento que es cero, se produce un error porque en el diccionario no hay una entrada con esa clave:

   1: >>> matriz[1,3]

   2: KeyError: (1, 3)

El metodo get soluciona este problema:

   1: >>> matriz.get((0,3), 0)

   2: 1

El primer argumento es la clave; el segundo argumento es el valor que debe devolver get en caso de que la clave no este en el diccionario:

   1: >>> matriz.get((1,3), 0)

   2: 0

get mejora sensiblemente la semántica del acceso a una matriz dispersa. Lástima de sintaxis.

Si estuvo jugando con la función fibonacci de la Sección 5.7, es posible que haya notado que cuanto mas grande es el argumento que le da, mas tiempo le cuesta ejecutarse. Mas aun, el tiempo de ejecución aumenta muy rápidamente.

En nuestra maquina, fibonacci(20) acaba instantáneamente, fibonacci(30) tarda mas o menos un segundo, y fibonacci(40) tarda una eternidad.

Para entender por que, observe este grafico de llamadas de fibonacci con n=4:

Un grafico de llamadas muestra un conjunto de cajas de función con líneas que conectan cada caja con las cajas de las funciones a las que llama. En lo alto del grafico, fibonacci con n=4 llama a fibonacci con n=3 y n=2. A su vez, fibonacci con n=3 llama a fibonacci con n=2 y n=1. Y así sucesivamente.

Cuente cuantas veces se llama a fibonacci(0) y fibonacci(1). Es una solución ineficaz al problema, y empeora mucho tal como crece el argumento.

Una buena solución es llevar un registro de los valores que ya se han calculado almacenándolos en un diccionario. A un valor que ya ha sido calculado y almacenado para un uso posterior se le llama pista. Aquí hay una implementación de fibonacci con pistas:

   1: anteriores = {0:1, 1:1}

   2: def fibonacci(n):

   3:         if anteriores.has_key(n):

   4:             return anteriores[n]

   5:         else:

   6:         nuevoValor = fibonacci(n-1) + fibonacci(n-2)

   7:         anteriores[n] = nuevoValor

   8:         return nuevoValor

El diccionario llamado anteriores mantiene un registro de los valores de Fibonacci que ya conocemos. El programa comienza con solo dos pares: 0 corresponde a 1 y 1 corresponde a 1.

Siempre que se llama a fibonacci comprueba si el diccionario contiene el resultado ya calculado. Si esta ahí, la función puede devolver el valor inmediatamente sin hacer mas llamadas recursivas. Si no, tiene que calcular el nuevo valor. El nuevo valor se añade al diccionario antes de que la función vuelva.

Con esta versión de fibonacci, nuestra maquina puede calcular fibonacci(40) en un abrir y cerrar de ojos. Pero cuando intentamos calcular fibonacci(50), nos encontramos con otro problema:

   1: >>> fibonacci(50)

   2: OverflowError: integer addition

La respuesta, como vera en un momento, es 20.365.011.074. El problema es que este numero es demasiado grande para caber en un entero de Python. Se desborda. Afortunadamente, hay una solución fácil para este problema.