1.2.2 Contar el número de operaciones

• La función es si existen y tales que para todo se tiene que .

• respresenta que es . A veces, se escribe .

• está dominada por si .

• Ejemplos:
  • 
  • , donde es un polinomio y la exponencial.

1.2.2.1 O, y

• La función es si existen y tales que para todo se tiene que . Se representa por .

• .

1.2.2.2 Complejidad

• Un algoritmo tiene complejidad ó coste en (resp. , ) si su número de operaciones (como función del tamaño de los datos de entrada) es una función que pertenece a (resp. , ).

1.2.2.3 Coste en el peor caso y coste promedio

• El coste en el peor caso es el máximo número de operaciones para un dato de entrada que tenga tamaño n.

• El coste promedio es el promedio del número de operaciones sobre todos los posibles datos de entrada de tamaño n.

1.2.3 ¿Cómo funcionan las listas?

• Internamente, una lista es un espacio de direcciones de memoria consecutivas que contienen referencias a los objetos almacenados en la lista.

• Mantener las direcciones consecutivas tiene un precio:
  • Si queremos añadir un elemento al final usando append), es necesario que la dirección de memoria al final de la lista esté desocupada. Si no lo está, tenemos que desplazar la lista a un nuevo emplazamiento en la memoria donde haya sitio para todos los elementos.
  • Añadir un elemento en cualquier posición distinta de la última obliga a desplazar los elementos posteriores de la lista para hacer hueco al nuevo elemento.
  • Al quitar un elemento, tenemos que desplazar el resto de los elementos a la izquierda hasta tapar el hueco que deja el elemento que hemos sacado.

• Ejemplo: Comparamos los tiempos necesarios para eliminar todos los elementos de una lista, primero eliminando cada vez el último elemento, y después eliminando el primer elemento de la lista.

def elimina_por_detras(xs):
    """
    Elimina los elementos de xs por detrás.
    """
    while len(xs)>0:
        del xs[-1]

def elimina_por_delante(xs):
    """
    Elimina los elementos de xs por delante.
    """
    while len(xs)>0:
        del xs[0]

# Comparación:
#    sage: time elimina_por_detras(range(100000))
#    Time: CPU 0.06 s, Wall: 0.07 s
#    sage: time elimina_por_delante(range(100000))
#    Time: CPU 45.21 s, Wall: 45.51 s

• Ejercicio: Comparar el tiempo necesario para añadir 50.000 elementos al principio y al final de la lista vacía.

• Solución:

def agrega_inicio(xs,ys):
    """
    Agrega los elementos de xs al inicio de ys. Por ejemplo,
       sage: agrega_inicio([3,5,7],[2,4])
       [7, 5, 3, 2, 4]
    """
    zs = ys
    for x in xs:
        zs.insert(0,x)
    return zs

def agrega_final(xs,ys):
    """
    Agrega los elementos de xs al final de ys. Por ejemplo,
       sage: agrega_final([3,5,7],[2,4])
       [2, 4, 3, 5, 7]
    """
    zs = ys
    for x in xs:
        zs.append(x)
    return zs
    
# Comparación:
#    sage: time x = agrega_inicio(srange(50000),[])
#    Time: CPU 1.52 s, Wall: 1.52 s
#    sage: time x = agrega_final(srange(50000),[])
#    Time: CPU 0.03 s, Wall: 0.04 s

1.2.4 Coste de las operaciones usuales con listas

1.2.4.1 Añadir un elemento

• Coste de añadir un elemento al final de una lista:
  • Mejor caso: si el espacio al final de la lista está disponible, sólo se necesita operaciones.
  • Peor caso: si el espacio al final de la lista no está disponible, tenemos que copiar la lista entera a un lugar nuevo, lo que cuesta .

• Para reduccir recolocaciones, Python reserva al final de cada lista un espacio igual a su longitud.

• Coste de añadir n elementos al final de una lista:

  

• Se dice que añadir un elemento a una lista tiene coste amortizado , porque añadir elementos siempre tiene complejidad en .

1.2.4.2 Insertar un elemento en una posición arbitraria

• Insertar un elemento en la posición k-ésima de una lista de n elementos obliga a desplazar los n-k últimos elementos para abrir hueco.

• Ejemplo: crear una lista de n elementos insertando los elementos al principio tiene coste:

1.2.4.3 Quitar elementos

• Quitar un elemento del final de la lista tiene coste .

• Quitar el elemento en la posición k-ésima de una lista de n elementos tiene coste .

1.2.4.4 Acceder o actualizar elementos

• Acceder o actualizar elementos tiene coste .

1.2.5 Comparativa entre listas y diccionarios

• Acceder a un elemento de un diccionario (dic[clave]) es más lento que a un elemento de una lista (lista[indice]). Sin embargo, ambos son similares.

• Insertar o quitar un elemento del final de una lista es más rápido que hacerlo de un diccionario. Sin embargo, ambos son similares.

• Insertar o quitar un elemento cualquiera de una lista es mucho más lento que hacerlo de un diccionario.

• Comprobar si un valor está en una lista es mucho más lento que hacer la comprobación en un conjunto o diccionario.

1.2.5.1 Ejemplo: Intersección de listas y conjuntos

• Ejercicio. Definir la función interseccion tal que interseccion(xs,ys) es la intersección de xs e ys.

• Solución.

# 1ª definición (Intersección con listas):
def interseccion1(xs,ys):
    return [x for x in xs if x in ys]

# 2ª definición (usando pertenencia de conjuntos):
def interseccion2(xs,ys):
    c = set(ys)
    return [x for x in xs if x in c]

# 3ª definición (usando intersección de conjuntos):
def interseccion3(xs,ys):
    return list(set(xs) & set(ys))

# Comparaciones
#    sage: n = 5000
#    sage: xs = [randint(1,10*n) for k in range(n)]
#    sage: ys = [randint(1,10*n) for k in range(n)]
#    sage: time zs = interseccion1(xs, ys)
#    CPU 3.33 s, Wall: 3.38 s
#    sage: time zs = interseccion2(xs, ys)
#    CPU 0.00 s, Wall: 0.01 s
#    sage: time zs = interseccion3(xs, ys)
#    CPU 0.00 s, Wall: 0.00 s

1.2.5.2 Ejemplo: Números triangulares, pentagonales y hexagonales

• Ejercicio. Calcular los tres primeros números que son simultáneamente triangulares, pentagonales y hexagonales.

• Solución.

def triangulares(n):
    """
    Conjunto de los números triangulares menores que n. Por ejemplo,
       sage: triangulares(20)
       set([1, 10, 3, 6, 15])
    """
    k=1
    triangulares = set()
    while k*(k+1)/2<n:
        triangulares.add(k*(k+1)/2)
        k = k+1
    return triangulares

def pentagonales(n):
    """
    Conjunto de los números pentagonales menores que n. Por ejemplo,
       sage: pentagonales(100)
       set([1, 35, 5, 70, 12, 51, 22, 92])
    """
    k=1
    pentagonales = set()
    while k*(3*k-1)/2<n:
        pentagonales.add(k*(3*k-1)/2)
        k = k+1
    return pentagonales

def hexagonales(n):
    """
    Conjunto de los números hexagonales menores que n. Por ejemplo,
       sage: hexagonales(100)
       set([1, 66, 6, 45, 15, 91, 28])
    """
    k=1
    hexagonales = set()
    while k*(2*k-1)<n:
        hexagonales.add(k*(2*k-1))
        k = k+1
    return hexagonales

def numeros_tph(n):
    '''
    Conjunto de los números menores que n que son a la vez triangulares,
    pentagonales y hexagonales. Por ejemplo, 
       sage: numeros_tph(100)
       set([1])
    '''
    return triangulares(n) & pentagonales(n) & hexagonales(n)

# Cálculos:
#    sage: time numeros_tph(1e6)
#    set([1, 40755])
#    Time: CPU 0.11 s, Wall: 0.11 s
#    sage: time numeros_tph(1e8)
#    set([1, 40755])
#    Time: CPU 1.02 s, Wall: 1.02 s
#    sage: time numeros_tph(1e10)
#    set([1, 40755, 1533776805])
#    Time: CPU 11.38 s, Wall: 11.44 s

1.3 Eficiencia en cálculo científico

1.3.1 Optimiza sólo si es necesario, sólo dónde es necesario

• Metodología de optimización progresiva:
  1. Escribe código correcto, y claro.
  2. Pruébalo en suficientes casos.
  3. Comprueba si es lo bastante rápido para el tamaño de tus datos. Si lo es, dedícate a otra cosa.
  4. Si el código no es lo bastante rápido, identifica las partes del programa que más influyen en la velocidad.
  5. Piensa si tu algoritmo es mejorable y, si puedes, usa otro mejor.
  6. Si tu código no es lo bastante rápido y no conoces mejores algoritmos, reescribe las partes críticas del código en un lenguaje compilado

1.3.2 Caso práctico: la constante de Brun

• La constante de Brun es por definición la suma de los inversos de todos los primos gemelos
  "

• En 1919 Viggo Brun demostró la convergencia de la serie.

• La mejor estimación hasta la actualidad es la de Pascal Sebah y Patrick Demichel publicada en el año 2002, con todos los primos gemelos hasta 1016:
  

• Nota: En los siguientes ejercicios calcularemmos una aproximación y mejoraremos progresivamente su eficiencia.

• Ejercicio. Definir la función primos tal que primos(k) es la lista de los números primos menores que k. Por ejemplo,

sage: primos(40)
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

• Solución.

def primos(k):
    def criba(xs):
        ys = []
        while xs:
            p = xs[0]
            ys.append(p)
            xs = [k for k in xs if k % p != 0]
        return ys
    return criba(range(2,k))

• Ejercicio. Definir la función gemelos tal que gemelos(xs) es la lista de los elementos x de la lista ordenada xs tales x+2 también está en xs. Por ejemplo,

sage: gemelos([2,3,5,7,8,10])
[3, 5, 8]

• Solución.

def gemelos(xs):
    return [x for x in xs if x+2 in xs]

• Ejercicio. Definir la función brun tal que brun(k) es la suma de los inversos de los primos gemelos menores que k. Por ejemplo,

sage: brun(1e4)
1.61689355743220

• Solución.

def brun(k):
    return sum((1.0/x + 1/(x+2)) for x in gemelos(primos(k)))

• Ejercicio. Definir la función tiempos_brun tal que tiempos_brun(ns) escribe los tiempos para calcular brun(x) variando x sobre los elementos de ns. Por ejemplo,

sage: tiempos_brun([2^n for n in srange(14,17)])
[0.9799999999999898, 3.3760000000000048, 12.352000000000004]

• Solución.

def tiempos_brun(ns):
    tiempos = []
    for n in ns:
        tcpu0 = cputime()
        x = brun(n)
        tiempos.append(cputime()-tcpu0)
    return tiempos

• Ejercicio. Determinar las funciones que requieren más tiempo al evaluar brun(10000).

• Solución.

sage: import cProfile, pstats
sage: cProfile.runctx("brun(10000)", globals(), locals(), "Profile.prof")
sage: s = pstats.Stats("Profile.prof")
sage: s.strip_dirs().sort_stats("time").print_stats()
Fri Aug  8 13:53:46 2014    Profile.prof

         1446 function calls in 0.422 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.285    0.285    0.287    0.287 <string>:14(criba)
        1    0.130    0.130    0.130    0.130 <string>:23(gemelos)
      206    0.003    0.000    0.003    0.000 <string>:39(<genexpr>)
     1229    0.002    0.000    0.002    0.000 {method 'append' of 'list' objects}
        1    0.001    0.001    0.001    0.001 {range}
        1    0.001    0.001    0.289    0.289 <string>:8(primos)
        1    0.001    0.001    0.003    0.003 {sum}
        1    0.000    0.000    0.422    0.422 <string>:32(brun)

• Ejercicio. Redefinir gemelos más eficientemente.

• Solución.

def gemelos2(xs):
    return [xs[j] for j in xrange(len(xs)-1) if xs[j+1]==xs[j]+2]

def gemelos2a(xs):
    return [x for (x,y) in zip(xs,xs[1:]) if x+2 == y]

• Ejercicio. Redefinir primos más eficientemente.

• Solución.

def primos2(n):
    aux = [True]*int(n)
    aux[0] = False
    aux[1] = False
    for i in xrange(2,floor(sqrt(n))+1):
        if aux[i]:
            for j in xrange(i*i,n,i):
                aux[j] = False
    return [k for k in xrange(n) if aux[k]]

• Ejercicio. Redefinir brun usando las funciones redefinidas.

• Solución.

def brun2(k):
    return sum((1.0/x + 1/(x+2)) for x in gemelos2(primos2(k)))

• Ejercicio. Calcular los tiempos empleados al evaluar brun2(10000).

• Solución.

# Tiempos
#    sage: cProfile.runctx("brun2(10000)", globals(), locals(), "Profile.prof")
#    sage: s = pstats.Stats("Profile.prof")
#    sage: s.strip_dirs().sort_stats("time").print_stats()
#    Fri Aug  8 14:22:05 2014    Profile.prof
#    
#             244 function calls in 0.018 seconds
#    
#       Ordered by: internal time
#    
#       ncalls  tottime  percall  cumtime  percall filename:lineno(function)
#            1    0.009    0.009    0.012    0.012 <string>:174(primos2)
#          206    0.004    0.000    0.004    0.000 <string>:191(<genexpr>)
#            1    0.002    0.002    0.002    0.002 <string>:152(gemelos3)
#            1    0.001    0.001    0.001    0.001 homset.py:40(Hom)
#            1    0.001    0.001    0.002    0.002 other.py:1545(_do_sqrt)
#            1    0.001    0.001    0.004    0.004 {sum}
#            1    0.000    0.000    0.000    0.000 other.py:544(__call__)
#            1    0.000    0.000    0.000    0.000 {zip}
#            1    0.000    0.000    0.018    0.018 <string>:184(brun2)

1.4 Ejercicios

1.4.1 Conjuntos y diccionarios

1.4.1.1 Factores primos de una lista

• Ejercicio. Definir factores tal que factores(xs) es la lista de los factores primos de los números de xs. Por ejemplo, factores([200,30]) == [2, 3, 5]

• Solución:

# 1ª definición (por iteración):
def factores(xs):
    c = set()
    for x in xs:
        for (p,e) in factor(x):
            c.add(p)
    return list(c)

# 2ª definición (por comprensión):
def factores2(xs):
    return list(set([p for x in xs for (p,e) in factor(x)]))

1.4.1.2 Frecuencia de las letras de una cadena.

• Ejercicio. Definir la función frecuencia_letras tal que frecuencia_letras(cs) es el diccionario con las letras de la cadena cs y el número de veces que aparece. Por ejemplo,

sage: frecuencia_letras("Todo para nada")
{'a': 4, 'd': 2, 'o': 2, 'n': 1, 'p': 1, 'r': 1, 'T': 1}

• Solución:

def frecuencia_letras(cs):
    d = dict([])
    for c in cs:
        if c in d:
            d[c] = 1 + d[c]
        elif c.isalpha():
            d[c] = 1
    return d

1.4.1.3 Frecuencia de palabras en un texto

• Ejercicio. Definir la función frecuencia_palabras tal que frecuencia_palabras(cs) es el diccionario con las palabras de la cadena cs y el número de veces que aparece. Por ejemplo,

sage: frecuencia_palabras("nunca como como nunca como")
{'nunca': 2, 'como': 3}

• Solución:

def frecuencia_palabras(cs):
    ps = cs.split()
    d = dict([])
    for p in ps:
        if p in d:
            d[p] = 1 + d[p]
        else:
            d[p] = 1
    return d

1.4.1.4 Conjuntos y el problema de Collatz

• Ejercicio. El sucesor de Collatz de un número n es n/2, si n es par y 3*n+1, en caso contrario. La órbita de un número se obtiene escribiendo los sucesivos sucesores de Collatz hasta llegar a 1. Por ejemplo, la órbita de Collatz de 7 es 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. La conjetura de Collatz afirma que todos los números tienen una órbita finita.
  
  Definir la función conjetura_Collatz tal que conjetura_Collatz(n) se verifica si se cumple la conjetura de Collatz para todos los números menores o iguales que n.

• Solución:

load Tiempo.sage

# 1ª definición (por iteración):
def conjetura_Collatz(n):
    for k in range(2,n):
        j = k
        while j != 1:
            if is_even(j):
                j = j/2
            else:
                j =  3*j + 1
    return True

# 2ª definición (parando en los menores):
def conjetura_Collatz2(n):
    for k in range(2,n):
        j = k
        while j >= k:
            if is_even(j):
                j = j/2
            else:
                j =  3*j + 1
    return True

# 3ª definición (con conjuntos)
def conjetura_Collatz3(n):
    s = set()
    for k in range(1,n):
        j = k
        while j != 1 and not (j in s):
            s.add(j)
            if is_even(j):
                j = j/2
            else:
                j =  3*j + 1
    return True

# Comparación de eficiencia
#    sage: tiempo1(conjetura_Collatz,500)
#    2.525918960571289
# 
#    sage: tiempo1(conjetura_Collatz2,500)
#    0.3285210132598877
# 
#    sage: tiempo1(conjetura_Collatz3,500)
#    0.10817289352416992

1.4.1.5 Conjetura de Goldbach

• Ejercicio. La conjetura de Goldbach afirma que todo número par mayor que 2 se puede expresar como suma de dos números primos.
  Definir la función goldbach tal que golbach(n) se verifica si todos los números pares mayores que 2 y menores que n se puede expresar como suma de dos números primos.

• Solución.

def goldbach(n): 
    pares = set(srange(4,n,2))
    primos = [x for x in srange(n) if is_prime(x)]
    suma_dos_primos = set([x+y for x in primos for y in primos])
    return pares <= suma_dos_primos

1.4.1.6 Dos dados

• Ejercicio. Definir la función dos_dados tal que dos_dados() es un diccionario cuyas claves son los números enteros entre 2 y 12, y su valor en el número k sea una lista de tuplas con todas las posibles formas de sumar k usando dos números enteros entre 1 y 6. Por ejemplo,

sage: dos_dados()[3]
[(1, 2), (2, 1)]
sage: dos_dados()[7]
[(1, 6), (2, 5), (3, 4), (4, 3), (5, 2), (6, 1)]

• Solución.

def dos_dados():
    d = dict([(k,[]) for k in srange(2,13)])
    for i in srange(1,7):
        for j in srange(1,7):
            d[i+j].append((i,j))
    return d

1.4.2 Gráficas de tiempo de ejecución

1.4.2.1 Pares como sumas de dos primos

• Ejercicio. Definir la función sumas tal que sumas(n) es la lista de pares de primos cuya suma es n. Por ejemplo,

sage: sumas(20)
[(3, 17), (7, 13), (13, 7), (17, 3)]
sage: sumas2(21)
[]

• Solución.

# 1ª definición (con listas):
def sumas1(n):
    if is_odd(n):
        return []
    else:
        lista = []
        primos = prime_range(n)
        for k in primos:
            if n-k in primos:
                lista.append((k,n-k))
        return lista

# 1ª definición (con conjuntos):
def sumas2(n):
    if is_odd(n):
        return []
    else:
        lista = []
        primos = set(prime_range(n))
        for k in primos:
            if n-k in primos:
                lista.append((k,n-k))
        return lista

# 3ª definición (con conjuntos y comprensión):
def sumas3(n):
    primos = set(prime_range(n))
    return [(k,n-k) for k in primos if n-k in primos]

# Comparaciones
#    sage: time x = sumas1(10000)
#    Time: CPU 0.25 s, Wall: 0.25 s
#    sage: time x = sumas2(10000)
#    Time: CPU 0.00 s, Wall: 0.00 s
#    sage: time x = sumas3(10000)
#    Time: CPU 0.01 s, Wall: 0.01 s
#    
#    sage: time x = sumas2(1000000)
#    Time: CPU 0.34 s, Wall: 0.34 s
#    sage: time x = sumas3(1000000)
#    Time: CPU 0.34 s, Wall: 0.34 s

def tiempos_sumas1(ns):
    """
    Tiempo de sumas1 para los elementos de ns.
       sage: tiempos_sumas1(srange(1000,1006,2))
       [0.007999999999995566, 0.004001000000002364, 0.0040000000000048885]
    """
    tiempos = []
    for n in ns:
        tcpu0 = cputime()
        x = sumas1(n)
        tiempos.append(cputime()-tcpu0)
    return tiempos

def grafica_tiempos_sumas1(ns):
    """
    Dibuja una gráfica con los tiempos sumas1 de los elementos de ns. Por
    ejemplo,
       sage: grafica_tiempos_sumas1(srange(1000,1500,2))
       Dibuja ../fig/Tiempos_sumas_de_dos_primos.png
    """
    g = line(zip(ns,tiempos_sumas1(ns)))
    g.show()

def tiempos_sumas2(ns):
    """
    Tiempo de sumas2 para los elementos de ns.
       sage: tiempos_sumas2(srange(1000,1006,2))
       [0.0, 0.004000000000019099, 0.0]
    """
    tiempos = []
    for n in ns:
        tcpu0 = cputime()
        x = sumas2(n)
        tiempos.append(cputime()-tcpu0)
    return tiempos

def grafica_tiempos_sumas2(ns):
    """
    Dibuja una gráfica con los tiempos sumas2 de los elementos de ns. Por
    ejemplo,
       sage: grafica_tiempos_sumas2(srange(1000,1500,2))
       Dibuja ../fig/Tiempos_sumas_de_dos_primos2.png
    """
    g = line(zip(ns,tiempos_sumas2(ns)))
    g.show()