Capítulo 1. Resolución de problemas

Este trabajo se ha traducido utilizando IA. Agradecemos tus opiniones y comentarios: translation-feedback@oreilly.com

¿Qué es un algoritmo?

Explicar cómo funciona un algoritmo es como contar una historia. Cada algoritmo introduce un concepto novedoso o una innovación que mejora las soluciones ordinarias. En este capítulo exploro varias soluciones a un problema sencillo para explicar los factores que afectan al rendimiento de un algoritmo. Por el camino introduzco técnicas utilizadas para analizar el rendimiento de un algoritmoindependientemente de su implementación, aunque siempre proporcionaré pruebas empíricas de implementaciones reales.

Nota

Un algoritmo es un método de resolución de problemas paso a paso implementado como un programa informático que devuelve un resultado correcto en un tiempo predecible. El estudio de los algoritmos se ocupa tanto de la corrección (¿funcionará este algoritmo para todas las entradas?) como del rendimiento (¿es ésta la forma más eficaz de resolver este problema?).

Recorramos un ejemplo de método de resolución de problemas para ver cómo es esto en la práctica. ¿Qué pasaría si quisieras encontrar el valor más grande de una lista desordenada? Cada lista Python de la Figura 1-1 es unainstancia del problema, es decir, la entrada procesada por un algoritmo (que se muestra como un cilindro); la respuesta correcta aparece a la derecha. ¿Cómo se implementa este algoritmo? ¿Cómo funcionaría en diferentes instancias del problema? ¿Puedes predecir el tiempo necesario para encontrar el valor más grande de una lista de un millón de valores?

Algorithm Processing
Figura 1-1. Tres instancias de problemas diferentes procesadas por un algoritmo

Un algoritmo es algo más que un método de resolución de problemas; el programa también debe completarse en un tiempo predecible. La función incorporada de Python max() ya resuelve este problema. Ahora bien, puede ser difícil predecir el rendimiento de un algoritmo en instancias de problemas que contengan datos aleatorios, por lo que merece la pena identificar instancias de problemas construidas cuidadosamente.

La Tabla 1-1 muestra los resultados de la temporización max() en dos tipos de instancias del problema de tamaño N: una en la que la lista contiene números enteros ascendentes y otra en la que la lista contiene números enteros descendentes. Aunque tu ejecución puede dar resultados diferentes a los de la tabla, según la configuración de tu sistema informático, puedes verificar las dos afirmaciones siguientes:

  • El tiempo de max() en valores ascendentes es siempre más lento que en valores descendentes una vez que N es lo suficientemente grande.

  • A medida que N se multiplica por diez en las filas siguientes, el tiempo correspondiente paramax() también parece multiplicarse por diez, con alguna desviación, como cabe esperar de los ensayos de ejecución en vivo.

Para este problema, se devuelve el valor máximo, y la entrada no se modifica. En algunos casos, el algoritmo actualiza directamente la instancia del problema en lugar de calcular un nuevo valor; por ejemplo, al ordenar una lista de valores, como verás en el Capítulo 5. En este libro, N representa el tamaño de una instancia del problema.

Tabla 1-1. Ejecución de max() en dos tipos de instancias de problemas de tamaño N (tiempo en ms)
N Valores ascendentes Valores descendentes

100

0.001

0.001

1,000

0.013

0.013

10,000

0.135

0.125

100,000

1.367

1.276

1,000,000

14.278

13.419

Cuando se trata del momento oportuno:

  • No puedes predecir de antemano el valor de T(100.000) -es decir, el tiempo que necesita el algoritmo para resolver una instancia del problema de tamaño 100.000- porque las plataformas informáticas varían y se pueden utilizar distintos lenguajes de programación.

  • Sin embargo, una vez que determines empíricamente T(10.000), puedes predecirT(100.000) -es decir, el tiempo para resolver una instancia de problema diez veces mayor-, aunque la predicción será inevitablemente inexacta hasta cierto punto.

Al diseñar un algoritmo, el reto principal es asegurarse de que es correcto y funciona para todas las entradas. En el Capítulo 2dedicaré más tiempo a explicar cómo analizar y comparar el comportamiento de distintos algoritmos que resuelven exactamente el mismo problema. El campo del análisis de algoritmos está ligado al estudio de problemas interesantes y relevantes que surgen en la vida real. Aunque las matemáticas de los algoritmos pueden ser difíciles de entender, daré ejemplos concretos para conectar siempre los conceptos abstractos con los problemas del mundo real.

La forma estándar de juzgar la eficiencia de un algoritmo es contar cuántas operaciones de cálculo requiere. Pero esto es excepcionalmente difícil de hacer. Los ordenadores tienen una unidad central de procesamiento (CPU) que ejecuta instrucciones de máquina que realizan cálculos matemáticos (como sumar y multiplicar), asignan valores a los registros de la CPU y comparan dos valores entre sí. Los lenguajes de programación modernos (como C oC++) se compilan en instrucciones de máquina. Otros lenguajes (como Python o Java) se compilan en una representación intermedia de código de bytes. El intérprete de Python (que a su vez es un programa en C) ejecuta el código de bytes, mientras que las funciones incorporadas, como min() y max(), se implementan en C y, en última instancia, se compilan en instrucciones de máquina para su ejecución.

Es casi imposible contar el número total de instrucciones de máquina ejecutadas para un algoritmo, ¡por no mencionar que las CPU actuales pueden ejecutar miles de millones de instrucciones por segundo! En su lugar, contaré el número de veces que se invoca una operación clave para cada algoritmo, que podría ser "el número de veces que se comparan entre sí dos valores de una matriz" o "cuántas veces se llama a una función". En este debate sobremax(), la operación clave es "cuántas veces se invoca al operador menor que (<)". Ampliaré este principio de recuento en el Capítulo 2.

Ahora es un buen momento para levantar el capó del algoritmo max() y ver por qué se comporta como lo hace.

Encontrar el mayor valor de una lista arbitraria

Considera la implementación defectuosa de Python del Listado 1-1, que intenta encontrar el mayor valor de una lista arbitraria que contenga al menos un valor, comparando cada valor de A con my_max, actualizandomy_max según sea necesario cuando se encuentren valores mayores.

Listado 1-1. Implementación defectuosa para localizar el valor más grande de la lista
def flawed(A):
  my_max = 0        1
  for v in A:       2
    if my_max < v:
      my_max = v    3
  return my_max
1

my_max es una variable que contiene el valor máximo; aquí my_max se inicializa a 0.

2

El bucle for define una variable v que itera sobre cada elemento de A. La sentencia if se ejecuta una vez por cada valor, v.

3

Actualiza my_max si v es mayor.

Un elemento central de esta solución es el operador menor que (<), que compara dos números para determinar si un valor es menor que otro. Enla Figura 1-2, a medida que v toma valores sucesivos de A, puedes ver que my_max se actualiza tres veces para determinar el mayor valor de A. flawed() determina el mayor valor de A, invocando menos-que seis veces, una para cada uno de sus valores. En una instancia de problema de tamaño N, flawed() invoca a menos-que N veces.

LargestVisualization
Figura 1-2. Visualización de la ejecución de flawed()

Esta implementación es defectuosa porque supone que al menos un valor de A es mayor que 0. Al calcular flawed([–5,–3,–11]) se obtiene 0, lo cual es incorrecto. Una solución habitual es inicializar my_max con el valor más pequeño posible, como my_max = float('-inf'). Este enfoque sigue siendo defectuoso, ya que devolvería este valor si A fuera la lista vacía []. Arreglemos ahora este defecto.

Consejo

La sentencia de Python range(x,y) produce los enteros desde x hasta, pero sin incluir, y. También puedes solicitar range(x,y,–1), que produce los enteros desde x contando hacia abajo hasta, pero sin incluir, y. Así,list(range(1,7)) produce [1,2,3,4,5,6], y list(range(5,0,–1))produce [5,4,3,2,1]. Puedes contar por incrementos arbitrarios, asílist(range(1,10,2)) produce [1,3,5,7,9] utilizando una diferencia de 2 entre valores.

Operaciones clave de recuento

Como el valor mayor debe estar contenido en A, la funciónlargest() correcta del Listado 1-2 selecciona el primer valor de Acomo my_max, comprobando los demás valores para ver si alguno es mayor.

Listado 1-2. Función correcta para encontrar el mayor valor de la lista
def largest(A):
  my_max = A[0]                 1
  for idx in range(1, len(A)):  2
    if my_max < A[idx]:
      my_max = A[idx]           3
  return my_max
1

Establece my_max en el primer valor de A, que se encuentra en la posición 0 del índice.

2

idx toma valores enteros desde 1 hasta, pero sin incluir, len(A).

3

Actualiza my_max si el valor de A en la posición idx es mayor.

Advertencia

Si invocas a largest() o max() con una lista vacía, lanzará una excepciónValueError: list index out of range. Estas excepciones en tiempo de ejecución son errores del programador, que reflejan una falta de comprensión de que largest()requiere un list con al menos un valor.

Ahora que tenemos una implementación correcta en Python de nuestro algoritmo, ¿puedes determinar cuántas veces se invoca menos-que en este nuevo algoritmo? Correcto! N - 1 veces. Hemos corregido el fallo del algoritmo y mejorado su rendimiento (hay que admitir que sólo un poco).

¿Por qué es importante contar los usos de menor que? Es la operación clave que se utiliza al comparar dos valores. Todas las demás sentencias del programa (como los bucles for o while ) son elecciones arbitrarias durante la implementación, basadas en el lenguaje de programación utilizado. Ampliaremos esta idea en el próximo capítulo, pero por ahora basta con contar las operaciones clave.

Los modelos pueden predecir el rendimiento de los algoritmos

¿Y si alguien te muestra un algoritmo diferente para este mismo problema? ¿Cómo determinarías cuál utilizar? Considera el algoritmo alternate() del Listado 1-3 que comprueba repetidamente cada valor de A para ver si es mayor o igual que todos los demás valores de la misma lista. ¿Dará este algoritmo el resultado correcto? ¿Cuántas veces invoca a menos-que en un problema de tamaño N?

Listado 1-3. Un enfoque diferente para localizar el valor más grande en A
def alternate(A):
  for v in A:
    v_is_largest = True        1
    for x in A:
      if v < x:
        v_is_largest = False   2
        break
    if v_is_largest:
      return v	               3
  return None                  4
1

Al iterar sobre A, asume que cada valor, v, puede ser el mayor.

2

Si v es menor que otro valor, x, detente y anota que v no es mayor.

3

Si v_is_largest es true, devuelve v ya que es el valor máximo en A.

4

Si A es una lista vacía, devuelve None.

alternate() intenta encontrar un valor, v, en A tal que ningún otro valor, x, en A sea mayor. La implementación utiliza dos bucles anidados for. Esta vez no es tan sencillo calcular cuántas veces se invoca a menos-que, porque el bucle interno for sobre x se detiene en cuanto se encuentra un xque sea mayor que v. Asimismo, el bucle externo for sobre vse detiene una vez que se encuentra el valor máximo. La Figura 1-3muestra la ejecución de alternate() en nuestro ejemplo de lista.

Alternate Visualization
Figura 1-3. Visualización de la ejecución de alternate()

En el caso de este problema, se invoca a menos-que 14 veces. Pero puedes ver que este recuento total depende de los valores concretos de la listaA. ¿Y si los valores estuvieran en otro orden? ¿Se te ocurre una disposición de los valores que requiera el menor número de invocaciones de menos-que? Un problema de este tipo se consideraría el mejor caso paraalternate(). Por ejemplo, si el primer valor de A es el mayor de todos los N valores, entonces el número total de llamadas a menos-que es siempre N. En resumen:

En el mejor de los casos

Una instancia de problema de tamaño N que requiere la menor cantidad de trabajo realizado por un algoritmo

En el peor de los casos

Una instancia de problema de tamaño N que exige la mayor cantidad de trabajo

Intentemos identificar el peor caso para alternate() que requiera el mayor número de llamadas a menos-que. Más que asegurarnos de que el valor mayor es el último de A, en el peor de los casos para alternate(), los valores de A deben aparecer en orden ascendente.

La Figura 1-4 visualiza el mejor caso en la parte superior dondep = [9,5,2,1,3,4] y el peor caso en la parte inferior donde p = [1,2,3,4,5,9].

Best and Worst Case
Figura 1-4. Visualización de la ejecución de alternate() en el mejor y el peor de los casos

En el mejor de los casos, hay seis llamadas a menos-que; si hubiera N valores en el mejor de los casos, el número total de invocaciones a menos-que sería N. Es un poco más complicado para el peor de los casos. En la Figura 1-4 puedes ver que hay un total de 26 llamadas a menos-que cuando la lista de N valores está en orden ascendente. Con un poco de matemáticas, puedo demostrar que para N valores, este recuento siempre será (N2 + 3N - 2)/2.

La Tabla 1-2 presenta pruebas empíricas sobrelargest() y alternate() en el peor de los casos de problemas de tamaño N.

Tabla 1-2. Comparación de largest() con alternate() en los peores casos de problemas
N La más grande Alternativa La más grande Alternativa
(# menos-que) (# menos-que) (tiempo en ms) (tiempo en ms)

8

7

43

0.001

0.001

16

15

151

0.001

0.003

32

31

559

0.002

0.011

64

63

2,143

0.003

0.040

128

127

8,383

0.006

0.153

256

255

33,151

0.012

0.599

512

511

131,839

0.026

2.381

1,024

1,023

525,823

0.053

9.512

2,048

2,047

2,100,223

0.108

38.161

Para instancias de problemas pequeñas, no parece malo, pero a medida que las instancias del problema duplican su tamaño, el número de invocaciones menos que paraalternate() se cuadruplica esencialmente, superando con creces el recuento paralargest(). Las dos columnas siguientes de la Tabla 1-2muestran el rendimiento de estas dos implementaciones en 100 pruebas aleatorias de instancias de problemas de tamaño N. El tiempo de ejecución de alternate()también se cuadruplica.

Nota

Mido el tiempo que necesita un algoritmo para procesar instancias de problemas aleatorios de tamaño N. De este conjunto de ejecuciones, selecciono el tiempo de ejecución más rápido (es decir, el más pequeño). Esto es preferible al simple promedio del tiempo total de ejecución de todas las ejecuciones, que podría sesgar los resultados.

A lo largo de este libro, voy a presentar tablas, comola Tabla 1-2, que contienen el número total de ejecuciones de una operación clave (aquí, el operador menos-que), así como el rendimiento en tiempo de ejecución. Cada fila representará un tamaño de instancia de problema distinto, N. Lee la tabla de arriba abajo para ver cómo cambian los valores de cada columna a medida que se duplica el tamaño de instancia del problema.

Contar el número de invocaciones a menos-que explica los comportamientos delargest() y alternate(). A medida que N se duplica, el número de llamadas a menos-que se duplica paralargest() pero se cuadruplica paraalternate(). Este comportamiento es coherente y puedes utilizar esta información para predecir el rendimiento en tiempo de ejecución de estos dos algoritmos en problemas de mayor tamaño. La Figura 1-5 representa el recuento de invocaciones a menos-que poralternate() (utilizando el eje y a la izquierda) frente a su rendimiento en tiempo de ejecución (utilizando el eje y a la derecha), mostrando la correlación directa entre ambos.

Tournament
Figura 1-5. Relación entre el número de operaciones menos que yel rendimiento en tiempo de ejecución

¡Enhorabuena! Acabas de realizar un paso clave en el análisis algorítmico: juzgar el rendimiento relativo de dos algoritmos contando el número de veces que se realiza una operación clave. Ciertamente, puedes ir e implementar ambas variantes (como hice yo) y medir su rendimiento respectivo en tiempo de ejecución en instancias del problema que duplican su tamaño; pero en realidad no es necesario, ya que el modelo predice este comportamiento y confirma que largest() es el algoritmo más eficiente de los dos.

largest() y son implementaciones del mismo algoritmo, pero como muestra max() la Tabla 1-3, siempre es significativamente más lento que , normalmente cuatro veces más lento. La razón es que Python es un lenguaje largest() max()interpretado, lo que significa que se compila a un código de bytes intermedio que es ejecutado por un intérprete de Python. Las funciones incorporadas, como , siempre superarán al código Python escrito con el mismo propósito, porque la función incorporada se implementa dentro del intérprete. Lo que debes observar es que, en todos los casos, a medida que N se duplica, el rendimiento correspondiente de y -tanto para max() largest()max()el mejor caso como para el peor- tambiénse duplica.

La Tabla 1-3 muestra que es posible predecir el tiempo necesario para resolver instancias de problemas de tamaño creciente. Una vez que conozcas el rendimiento en tiempo de ejecución de largest() o max() en el mejor o peor caso de un problema de tamaño N, puedes predecir que el rendimiento en tiempo de ejecución se duplicará cuando N se duplique. Ahora cambiemos ligeramente el problema para hacerlo más interesante.

Tabla 1-3. Rendimiento de largest() y max() en el mejor y el peor de los casos
N largest() peor caso max() peor caso largest() mejor caso max() mejor caso

4,096

0.20

0.05

0.14

0.05

8,192

0.40

0.11

0.29

0.10

16,384

0.80

0.21

0.57

0.19

32,768

1.60

0.41

1.14

0.39

65,536

3.21

0.85

2.28

0.78

131,072

6.46

1.73

4.59

1.59

262,144

13.06

3.50

9.32

3.24

524,288

26.17

7.00

18.74

6.50

Encontrar los dos valores más grandes de una lista arbitraria

Idea un algoritmo que encuentre los dos valores más grandes de una lista arbitraria. Tal vez puedas modificar el algoritmo existente largest() con unos pocos retoques. ¿Por qué no intentas resolver este problema modificado y vuelves aquí con tu solución? El listado 1-4 contiene mi solución.

Listado 1-4. Encuentra los dos valores más grandes modificando la aproximación largest() 
def largest_two(A):
  my_max,second = A[:2]                1
  if my_max < second:
    my_max,second = second,my_max

  for idx in range(2, len(A)):
    if my_max < A[idx]:                2
      my_max,second = A[idx],my_max
    elif second < A[idx]:              3
      second = A[idx]
  return (my_max, second)
1

Asegúrate de que my_max y second son los dos primeros valores de A en orden descendente.

2

Si A[idx] es un valor máximo recién encontrado, entonces establece my_max en A[idx], ysecond se convierte en el antiguo my_max.

3

Si A[idx] es mayor que second (pero menor que my_max), actualiza sólo second.

largest_two() se siente similar a : calcula y para que sean los dos primeros valores de , debidamente ordenados. Luego, para cada uno de los valores restantes en (¿cuántos? N - 2, ¡correcto!), si encuentras un mayor que , ajusta tanto como , de lo contrario comprueba si sólo hay que actualizar . largest() my_max second A A A[idx] my_max my_max second second

Contar el número de veces que se invoca menos-que es más complicado porque, una vez más, depende de los valores de la instancia del problema.

largest_two() realiza el menor número de invocaciones de menos-que cuando la condición de la sentencia if dentro del bucle for es verdadera. Cuando Acontiene valores en orden ascendente, este menos-que siempre es cierto, por lo que se invoca N - 2 veces; no olvides añadir 1 debido al uso de menos-que al principio de la función. Por tanto, en el mejor de los casos, sólo necesitas N - 1 invocaciones de menos-que para determinar los dos valores superiores. El menos-que de la condición elif no se utiliza nunca en el mejor de los casos.

Para largest_two(), ¿puedes construir una instancia del problema en el peor de los casos? Pruébalo tú mismo: ocurre siempre que el menor que en la condición if dentro del bucle for sea False.

Seguro que puedes ver que siempre que A contiene valores en orden descendente,largest_two() requiere el mayor número de invocaciones de menos-que. En concreto, para el peor de los casos, menos-que se utiliza dos veces cada vez a través del bucle for, o 1 + 2 × (N - 2) = 2N - 3 veces. De alguna manera esto parece correcto, ¿verdad? Si necesitas utilizar menos-que N - 1 veces para encontrar el valor más grande en A, tal vez necesites realmente N - 2 invocaciones adicionales a menos-que (dejando fuera el valor más grande, por supuesto) para encontrar también el segundo valor más grande.

Para resumir el comportamiento de largest_two():

  • En el mejor de los casos, encuentra ambos valores con N - 1 invocaciones menos-que.

  • En el peor de los casos, encuentra ambos valores con 2N - 3invocaciones menos-que.

¿Hemos terminado? ¿Es éste el "mejor" algoritmo para resolver el problema de encontrar los dos valores mayores de una lista arbitraria? Podemos elegir preferir un algoritmo a otro en función de varios factores:

Almacenamiento adicional necesario

¿Necesita un algoritmo hacer una copia de la instancia original del problema?

Esfuerzo de programación

¿Cuántas líneas de código debe escribir el programador?

Entrada mutable

¿Modifica el algoritmo la entrada proporcionada por la instancia del problema en cuestión, o la deja sola?

Velocidad

¿Supera un algoritmo a la competencia, independientemente de la entrada proporcionada?

Investiguemos tres algoritmos diferentes para resolver exactamente este mismo problema, mostrados en el Listado 1-5. sorting_two() crea una nueva lista que contiene los valores de A en orden descendente, coge los dos primeros valores y los devuelve como una tupla. double_two() utiliza max() para encontrar el valor máximo en A, lo elimina de una copia de A, y luego utilizamax() de esa lista reducida para encontrar el segundo mayor. mutable_two() encuentra la ubicación del valor más grande en A y lo elimina de A; luego establece en second el valor más grande que queda en A antes de reinsertar el valor de my_max en su ubicación original. Los dos primeros algoritmos requieren almacenamiento adicional, mientras que el tercero modifica su entrada: los tres sólo funcionan en instancias del problema que contengan más de un valor.

Listado 1-5. Tres enfoques diferentes utilizando utilidades de Python
def sorting_two(A):
  return tuple(sorted(A, reverse=True)[:2])    1

def double_two(A):
  my_max = max(A)                              2
  copy = list(A)
  copy.remove(my_max)                          3
  return (my_max, max(copy))                   4

def mutable_two(A):
  idx = max(range(len(A)), key=A.__getitem__)  5
  my_max = A[idx]                              6
  del A[idx]
  second = max(A)                              7
  A.insert(idx, my_max)                        8
  return (my_max, second)
1

Crea una nueva lista ordenando A en orden descendente y devuelve sus dos valores principales.

2

Utiliza la función incorporada max() para encontrar el mayor.

3

Crea una copia del original A, y elimina my_max.

4

Devuelve una tupla que contiene my_max y el mayor valor de copy.

5

Este truco de Python encuentra la ubicación del índice del valor máximo en A, en lugar del valor en sí.

6

Registra el valor my_max y bórralo de A.

7

Ahora encuentra max() de los valores restantes.

8

Restaura A insertando my_max en su ubicación original.

Estos distintos enfoques no utilizan directamente menos-que porque se basan en bibliotecas de Python ya existentes. Tanto sorting_two() como double_two()hacen una copia de la matriz, A, lo que parece innecesario, ya quelargest_two() no lo hace. Además, parece excesivo ordenar toda la lista sólo para encontrar los dos valores más grandes. Del mismo modo que cuento las operaciones cuando analizo el rendimiento en tiempo de ejecución, evaluaré el almacenamiento adicional utilizado por un algoritmo: para ambos enfoques, la cantidad de almacenamiento es directamente proporcional a N. El tercer enfoque,mutable_two(), actualiza brevemente A borrando su valor máximo, para volver a añadirlo más tarde. La persona que llama podría sorprenderse al ver que se ha modificado la lista original.

Con un poco de experiencia en Python, puedo calcular exactamente cuántas veces se invoca menos-que utilizando una clase especial RecordedItem.1 La Tabla 1-4 muestra que double_two() invoca el mayor número de operaciones menos-que cuando los valores están en orden ascendente, mientras que largest_two() (y otros) realizan el mayor número de operaciones menos-que cuando los valores están en orden descendente. En la última columna, denominada "Alternando", los 524.288 valores están dispuestos con números pares en orden ascendente, alternando con números impares en orden descendente: para N = 8, la entrada sería [0,7,2,5,4,3,6,1].

Tabla 1-4. Rendimiento de los distintos enfoques en 524.288 valores ascendentes y descendentes
Algoritmo Ascendente Descendente Alternando

mayor_dos

524,287

1,048,573

1,048,573

clasificación_dos

524,287

524,287

2,948,953

doble_dos

1,572,860

1,048,573

1,048,573

mutable_dos

1,048,573

1,048,573

1,048,573

torneo_dos

524,305

524,305

524,305

El algoritmo tournament_two() que describo a continuación tiene el menor número de invocaciones menos-que, independientemente de la entrada. A los aficionados al baloncesto les resultará familiar su lógica.

Advertencia

Si determinas cuál es el peor caso para un algoritmo que resuelve un problema determinado, tal vez otro algoritmo que resuelva el mismo problema no se vea tan negativamente afectado por ese caso. Diferentes algoritmos pueden tener diferentes puntos débiles que puedes descubrir con un análisis diligente.

Algoritmo del Torneo

Un torneo de eliminación simple consiste en un número de equipos que compiten por ser el campeón. Lo ideal es que el número de equipos sea una potencia de 2, como 16 o 64. El torneo se construye a partir de una secuencia de rondas en las que todos los equipos que quedan en el torneo se emparejan para jugar un partido; los perdedores del partido son eliminados, mientras que los ganadores pasan a la siguiente ronda. El último equipo que queda es el campeón del torneo.

Considera la instancia del problema p = [3,1,4,1,5,9,2,6] con N = 8 valores. La Figura 1-6 muestra el torneo de eliminación simple cuya ronda inicial compara ocho valores vecinos utilizando menos-que; los valores mayores avanzan en el torneo.2 En la ronda Elite Eight, se eliminan cuatro valores, quedando los valores [3,4,9,6]. En la ronda de los Cuatro Finalistas, los valores [4,9] avanzan, y finalmente 9 es declarado campeón.

Tournament
Figura 1-6. Un torneo con ocho valores iniciales

En este torneo, hay siete invocaciones de menos-que (es decir, una por cada coincidencia), lo que debería ser tranquilizador, ya que esto significa que el valor más grande se encuentra con N - 1 usos de menos-que, como habíamos comentado antes. Si almacenas cada una de estas N - 1 coincidencias, podrás localizar rápidamente el segundo valor más grande, como te muestro a continuación.

¿Dónde se puede "esconder" el segundo valor más grande una vez que el 9 haya sido declarado campeón? Empieza con el 4 como candidato a segundo valor más grande, ya que fue el valor que perdió en la ronda del Campeonato. Pero el valor más grande, 9, tuvo dos enfrentamientos anteriores, por lo que debes comprobar los otros dos valores perdedores: el valor 6 en la ronda de los Cuatro Finalistas y el valor 5 en la ronda de los Ocho Elite. Así pues, el segundo valor más grande es 6.

Para ocho valores iniciales, sólo necesitas 2 invocaciones menos-que adicionales -(¿es 4 < 6?) y (¿es 6 < 5?)- para determinar que 6 es el segundo valor más grande. No es casualidad que 8 =23 y necesites 3 - 1 = 2 comparaciones. Resulta que para N = 2K, necesitas K - 1 comparaciones adicionales, donde K es el número de rondas.

Cuando hay 8 =23 valores iniciales, el algoritmo construye un torneo con 3 rondas. La Figura 1-7 visualiza un torneo de 5 rondas formado por 32 valores. Para duplicar el número de valores del torneo, sólo necesitas una ronda adicional; en otras palabras, con cada nueva ronda K, puedes añadir 2K valores más. ¿Quieres encontrar el mayor de 64 valores? Sólo necesitas 6 rondas, ya que26 = 64.

Hierarchy
Figura 1-7. Un torneo con 32 valores iniciales

Para determinar el número de rondas para cualquier N, recurre a la función logaritmo, log(), que es lo contrario de la función exponente. Con N = 8 valores iniciales, se necesitan 3 rondas para el torneo, ya que23 = 8 y log 2(8) = 3. En este libro -y tradicionalmente en informática- el operador log() está en base 2.

Consejo

La mayoría de las calculadoras de mano calculan log() en base 10. La funciónln() representa el logaritmo natural en base e (que es aproximadamente 2,718). Para calcular rápidamente log(N) en base 2 utilizando una calculadora (o en Microsoft Excel), calcula log(N)/log(2).

Cuando N es una potencia de 2 -como 64 o 65.536- el número de rondas de un torneo es log(N), lo que significa que el número de invocaciones adicionales de menos-que es log(N) - 1. El algoritmo implementado en el Listado 1-6 minimiza las invocaciones de menos-que utilizando almacenamiento adicional para registrar los resultados de todas las partidas.

Listado 1-6. Algoritmo para encontrar los dos valores más grandes en A utilizando el torneo
def tournament_two(A):
  N = len(A)
  winner = [None] * (N-1)          1
  loser = [None] * (N-1)
  prior = [-1] * (N-1)             2

  idx = 0
  for i in range(0, N, 2):         3
    if A[i] < A[i+1]:
      winner[idx] = A[i+1]
      loser[idx] = A[i]
    else:
      winner[idx] = A[i]
      loser[idx] = A[i+1]
    idx += 1

  m = 0                            4
  while idx < N-1:
    if winner[m] < winner[m+1]:    5
      winner[idx] = winner[m+1]
      loser[idx]  = winner[m]
      prior[idx]  = m+1
    else:
      winner[idx] = winner[m]
      loser[idx]  = winner[m+1]
      prior[idx]  = m
    m += 2                         6
    idx += 1

  largest = winner[m]
  second = loser[m]                7
  m = prior[m]
  while m >= 0:
    if second < loser[m]:          8
      second = loser[m]
    m = prior[m]

  return (largest, second)
1

Estas matrices almacenan los ganadores y perdedores del partido idx; habrá N - 1 de ellos en el torneo.

2

Cuando un valor avanza en la coincidencia m, prior[m] registra la coincidencia anterior, o –1 cuando era la coincidencia inicial.

3

Inicializa los primeros N/2 pares ganador/perdedor utilizando N/2 invocaciones de menos-que. Éstas representan los emparejamientos de la ronda más baja.

4

Empareja a los ganadores para encontrar un nuevo ganador, y registra el índice de emparejamiento prior.

5

Se necesitan N/2 - 1 invocaciones adicionales de menos-que.

6

Avanza m de 2 en 2 para encontrar el siguiente par de ganadores. Cuando idx llega a N - 1,winner[m] es el mayor.

7

Candidato inicial a segundo más grande, pero debe comprobar todos los demás que perdieron en largest para encontrar el segundo más grande real.

8

No más de log(N) - 1 invocaciones adicionales de menos-que.

La Figura 1-8 muestra la ejecución de este algoritmo. Tras el paso de inicialización, los N valores de la matriz original, A, se separan en N/2 winners y losers; en el ejemplo de la Figura 1-6, hay cuatro pares. Durante cada paso de avance en el bucle while, el ganador/perdedor de dos emparejamientos consecutivos, m y m+1, se colocan en winner[idx] y loser[idx] respectivamente; prior[idx] registra el emparejamiento anterior del que procede el ganador (dibujado por una flecha de derecha a izquierda). Después de tres pasos, se almacena toda la información de los partidos y, a continuación, el algoritmo inspecciona a los perdedores de todos los partidos anteriores en busca del ganador. Puedes visualizar esto siguiendo las flechas hacia atrás hasta que se detengan. Puedes ver que el candidato a segundo mayor valor se encuentra en loser[6]: con sólo dos invocaciones less-than con loser[5] y loser[2], determina cuál es el mayor.

Acabo de esbozar un algoritmo para calcular el mayor y el segundo mayor valor en A utilizando sólo N - 1 + log(N) - 1 = N + log(N) - 2 invocaciones menos que para cualquier N que sea una potencia de 2. ¿Es tournament_two() práctico? ¿Superará a largest_two()? Si sólo cuentas el número de veces que se invoca al menos-que, tournament_two() debería ser más rápido. largest_two() requiere 131.069 operaciones menos-que en problemas de tamañoN = 65.536, mientras que tournament_two() sólo requiere 65.536 + 16 - 2 = 65.550, justo la mitad. Pero hay más en esta historia.

Step by step execution
Figura 1-8. Ejecución paso a paso del algoritmo del torneo

La Tabla 1-5 revela que tournament_two() es significativamente más lento que cualquiera de sus competidores. Registremos el tiempo total que se tarda en resolver 100 instancias de problemas aleatorios (de tamaño N creciente de 1.024 a 2.097.152). De paso, incluiré los resultados de rendimiento de los distintos algoritmos delListado 1-5. Ten en cuenta que si ejecutas el código de ejemplo en tu ordenador, tus resultados individuales serán diferentes, pero la tendencia general de cada columna seguirá siendo la misma.

Tabla 1-5. Comparación del tiempo de ejecución (en ms) de los cuatro algoritmos
N double_two mutable_two largest_two sorting_two tournament_two

1,024

0.00

0.01

0.01

0.01

0.03

2,048

0.01

0.01

0.01

0.02

0.05

4,096

0.01

0.02

0.03

0.03

0.10

8,192

0.03

0.05

0.05

0.08

0.21

16,384

0.06

0.09

0.11

0.18

0.43

32,768

0.12

0.20

0.22

0.40

0.90

65,536

0.30

0.39

0.44

0.89

1.79

131,072

0.55

0.81

0.91

1.94

3.59

262,144

1.42

1.76

1.93

4.36

7.51

524,288

6.79

6.29

5.82

11.44

18.49

1,048,576

16.82

16.69

14.43

29.45

42.55

2,097,152

35.96

38.10

31.71

66.14

…

La Tabla 1-5 puede resultar abrumadora, ya que parece un muro de números. Si ejecutas estas funciones en un ordenador diferente -quizás con menos memoria o una CPU más lenta- tus resultados podrían ser muy diferentes; sin embargo, hay algunas tendencias que deberían revelarse independientemente del ordenador en el que las ejecutes. En su mayor parte, a medida que lees hacia abajo en cualquier columna, el tiempo de ejecución se duplica más o menos a medida que se duplica el tamaño del problema.

Hay algunas situaciones inesperadas en esta tabla: observa quedouble_two() empieza siendo la más rápida de las cinco soluciones, pero finalmente (una vez que N > 262.144), largest_two() se convierte en la más rápida en completarse. El ingenioso planteamiento tournament_two() es, con diferencia, el más lento, simplemente porque necesita asignar matrices de almacenamiento cada vez más grandes para ser procesado. Es tan lento que ni siquiera lo ejecuto en la instancia más grande del problema porque tardaría mucho.

Para dar sentido a estas cifras, la Figura 1-9 visualiza las tendencias del tiempo de ejecución a medida que la instancia del tamaño del problema aumenta.

Hierarchy
Figura 1-9. Comparación del rendimiento en tiempo de ejecución

Esta imagen revela más detalles sobre el rendimiento en tiempo de ejecución de estos cinco enfoques:

  • Puedes ver que los rendimientos de mutable_two(), double_two(), ylargest_two() son más parecidos entre sí que los de los otros dos enfoques. Es casi como si todos fueran de la misma "familia", todos en una trayectoria en línea recta que parece bastante predecible.

  • tournament_two() es el menos eficiente, y se comporta de forma notablemente distinta a los demás enfoques. Dado que hay tan pocos puntos de datos, no está claro si está "curvándose hacia arriba" hacia mayores ineficiencias o si también seguirá una línea recta.

  • sorting_two() parece ir mejor que , pero es más lento que los otros tres enfoques. ¿Se curvará más hacia arriba o acabará enderezándose? tournament_two()

Para entender por qué estas líneas tienen la forma que tienen, tienes que aprender los dos conceptos fundamentales que explican la complejidadinherente a un algoritmo.

Complejidad temporal y complejidad espacial

Puede ser difícil contar el número de operaciones elementales (como la suma, la asignación de variables o la lógica de control), debido a la diferencia en los lenguajes de programación, además del hecho de que algunos lenguajes, como Java y Python, son ejecutados por un intérprete. Pero si pudieras contar el número total de operaciones elementales ejecutadas por un algoritmo, verías que el número total de operaciones varía en función del tamaño de la instancia del problema. El objetivo de la complejidad temporal es llegar a una funciónC(N) que cuente el número de operaciones elementales realizadas por un algoritmo en función de N, el tamaño de una instancia del problema.

Suponiendo que cada operación elemental lleva una cantidad de tiempo fija, t, basada en la CPU que ejecuta la operación, puedo modelar el tiempo para realizar el algoritmo como T(N) = t × C(N). El listado 1-7 confirma la idea de que la estructura de un programa es fundamental. Para las funciones f0, f1, f2, y f3, puedes calcular exactamente cuántas veces ejecuta cada una la operación ct = ct + 1 en función del tamaño de la entrada, N. La Tabla 1-6 contiene los recuentos para unos cuantos valores de N.

Listado 1-7. Cuatro funciones diferentes con distintos perfiles de rendimiento
def f0(N):      def f1(N):            def f2(N):             def f3(N):
  ct = 0          ct = 0                ct = 0                 ct = 0
  ct = ct + 1     for i in range(N):    for i in range(N):     for i in range(N):
  ct = ct + 1       ct = ct + 1           ct = ct + 1            for j in range(N):
  return ct       return ct               ct = ct + 1              ct = ct + 1
                                          ct = ct + 1          return ct
                                          ct = ct + 1
                                          ct = ct + 1
                                          ct = ct + 1
                                          ct = ct + 1
                                        return ct

La cuenta para f0 es siempre la misma, independientemente de N. La cuenta paraf2 es siempre siete veces mayor que f1, y ambas duplican su tamaño a medida que N se duplica. En cambio, el recuento de f3 aumenta mucho más rápidamente; como has visto antes, al duplicarse N, el recuento de f3(N)se cuadruplica. Aquí, f1 y f2 se parecen más entre sí que a f3. En el próximo capítulo, explicaremos la importancia de los bucles fory de los bucles anidados for a la hora de evaluar el rendimiento de un algoritmo.

Tabla 1-6. Operaciones de recuento en cuatro funciones diferentes
N f0 f1 f2 f3

512

2

512

3,584

262,144

1,024

2

1,024

7,168

1,048,576

2,048

2

2,048

14,336

4,194,304

Al evaluar un algoritmo, también tenemos que considerar la complejidad espacial, que da cuenta de la memoria adicional que necesita un algoritmo en función del tamaño, N, de una instancia del problema. La memoria es un término genérico para los datos almacenados en el sistema de archivos o en la memoria RAM de un ordenador. largest_two() tiene unos requisitos de espacio mínimos: utiliza dos variables, my_max y second, y una variable iteradora, idx. Independientemente del tamaño de la instancia del problema, su espacio adicional nunca cambia. Esto significa que la complejidad espacial es independiente del tamaño de la instancia del problema, o constante; mutable_two() tiene un comportamiento similar. En cambio, tournament_two() asignó tres matrices -winner, loser, y prior- todas de tamaño N - 1 . A medida que aumenta N, el almacenamiento extra total aumenta de forma directamente proporcional al tamaño de la instancia del problema.3 Construir la estructura del torneo va a ralentizar tournament_two(), si se compara con largest_two(). Tanto double_two() como sorting_two() hacen una copia de la entrada, A, lo que significa que su uso del almacenamiento se parece mucho más a tournament_two() que a largest_two(). A lo largo de este libro, evaluaré tanto la complejidad temporal como la complejidad espacial de cada algoritmo.

Si revisas la Tabla 1-5, puedes ver que los resultados de sincronización de la columnalargest_two más o menos se duplican en las filas siguientes; las columnas double_two ymutable_two se comportan de forma similar, como ya he observado. Esto significa que el tiempo total parece ser directamente proporcional al tamaño de la instancia del problema, que se duplica en las filas siguientes. Se trata de una observación importante, ya que estas funciones son más eficientes que sorting_two(), que parece seguir una trayectoria diferente, menos eficiente. tournament_two() sigue siendo la menos eficiente, con un rendimiento en tiempo de ejecución que aumenta a más del doble, creciendo tan rápidamente que no me molesto en ejecutarla para instancias de problemas grandes.

Como informático, no puedo limitarme a proclamar que las curvas de rendimiento delargest_two() y mutable_two() "parecen iguales". Necesito apoyarme en una teoría y una notación formales para captar esta idea. En el próximo capítulo, presentaré las herramientas matemáticas necesarias para analizar adecuadamente el comportamiento de los algoritmos.

Resumen

Este capítulo ha sido una introducción al rico y diverso campo de los algoritmos. He mostrado cómo modelar el rendimiento de un algoritmo en una instancia de problema de tamaño N contando el número de operaciones clave que realiza. También puedes evaluar empíricamente el rendimiento en tiempo de ejecución de la implementación de un algoritmo. En ambos casos, puedes determinar el orden de crecimiento del algoritmo a medida que se duplica el tamaño de la instancia del problema N.

Introduje varios conceptos clave, entre ellos

  • Complejidad temporal estimada contando el número de operaciones clave ejecutadas por un algoritmo en una instancia de problema de tamaño N.

  • Complejidad espacial estimada por la cantidad de memoria necesaria cuando un algoritmo se ejecuta en una instancia de problema de tamaño N.

En el próximo capítulo, presentaré las herramientas matemáticas del análisis asintótico que completarán mi explicación de las técnicas necesarias para analizar correctamentelos algoritmos.

Ejercicios de Desafío

  1. Detector de palabras palíndromas: Una palabra palíndroma se lee igual al revés que al derecho, como señora. Idea un algoritmo que valide si una palabra de N caracteres es un palíndromo. Confirma empíricamente que supera a las dos alternativas del Listado 1-8:

    Listado 1-8. Cuatro funciones diferentes con distintos perfiles de rendimiento
    def is_palindrome1(w):
  """Create slice with negative step and confirm equality with w."""
  return w[::-1] == w

def is_palindrome2(w):
  """Strip outermost characters if same, return false when mismatch."""
  while len(w) > 1:
    if w[0] != w[-1]:     # if mismatch, return False
      return False
    w = w[1:-1]           # strip characters on either end; repeat

  return True             # must have been palindrome

    Una vez que tengas este problema funcionando, modifícalo para que detecte las cadenas palíndromas con espacios, puntuación y mayúsculas mixtas. Por ejemplo, la siguiente cadena debería clasificarse como palíndromo: "A man, a plan, a canal. Panama!"

  2. Mediana en tiempo lineal: Existe un maravilloso algoritmo que localiza eficientemente el valor de la mediana en una lista arbitraria (para simplificar, supongamos que el tamaño de la lista es impar). Revisa el código del Listado 1-9 y cuenta el número de veces que se invoca a menos-que, utilizando los valores de RecordedItem que se muestran en el capítulo. Esta implementación reordena la lista arbitraria a medida que la procesa.

    Listado 1-9. Algoritmo en tiempo lineal para calcular la mediana de una lista desordenada
    def partition(A, lo, hi, idx):
  """Partition using A[idx] as value."""
  if lo == hi: return lo

  A[idx],A[lo] = A[lo],A[idx]    # swap into position
  i = lo
  j = hi + 1
  while True:
    while True:
      i += 1
      if i == hi: break
      if A[lo] < A[i]: break

    while True:
      j -= 1
      if j == lo: break
      if A[j] < A[lo]: break

    if i >= j: break
    A[i],A[j] = A[j],A[i]

  A[lo],A[j] = A[j],A[lo]
  return j

def linear_median(A):
  """
  Efficient implementation that returns median value in arbitrary list,
  assuming A has an odd number of values. Note this algorithm will
  rearrange values in A.
  """
  lo = 0
  hi = len(A) - 1
  mid = hi // 2
  while lo < hi:
    idx = random.randint(lo, hi)     # select valid index randomly
    j = partition(A, lo, hi, idx)

    if j == mid:
      return A[j]
    if j < mid:
      lo = j+1
    else:
      hi = j-1
  return A[lo]

    Implementa un enfoque diferente (que requiere almacenamiento adicional) que cree una lista ordenada a partir de la entrada y seleccione el valor medio. Compara su rendimiento en tiempo de ejecución con linear_median() generando una tabla de rendimiento en tiempo de ejecución.

  3. Ordenación por recuento: Si sabes que una lista arbitraria, A, sólo contiene enteros no negativos de 0 a M, el algoritmo siguiente ordenará correctamente A utilizando sólo un almacenamiento extra de tamaño M.

    El listado 1-10 tiene bucles anidados: un bucle for dentro de un buclewhile. Sin embargo, puedes demostrar que A[pos+idx] = v sólo se ejecuta N veces.

    Listado 1-10. Algoritmo de ordenación de recuento en tiempo lineal
    def counting_sort(A, M):
  counts = [0] * M
  for v in A:
    counts[v] += 1

  pos = 0
  v = 0
  while pos < len(A):
    for idx in range(counts[v]):
      A[pos+idx] = v
    pos += counts[v]
    v += 1

    Realiza un análisis de rendimiento para demostrar que el tiempo para ordenar N enteros en el rango de 0 a M se duplica al duplicarse el tamaño de N.

    Puedes eliminar el bucle interno for, y mejorar el rendimiento de esta operación, utilizando la posibilidad que ofrece Python de sustituir una sublista utilizandosublist[left:right] = [2,3,4]. Haz el cambio y valida empíricamente que también se duplica a medida que se duplica N, a la vez que se obtiene una mejora del 30% en la velocidad.

  4. Modifica el algoritmo del torneo para que funcione con un número impar de valores.

  5. ¿El código del Listado 1-11 localizará correctamente los dos valores mayores en A?

    Listado 1-11. Otro intento de calcular los dos valores más grandes de una lista desordenada
    def two_largest_attempt(A):
  m1 = max(A[:len(A)//2])
  m2 = max(A[len(A)//2:])
  if m1 < m2:
    return (m2, m1)
  return (m1, m2)

    Explica las circunstancias en las que este código funciona correctamente y en las que falla.

1 La clase envoltorio RecordedItem anula el operador menor que __lt__() para que cuente siempre que se invoque a éste (o al operador mayor que __gt__() ).

2 Si una coincidencia contiene dos valores iguales, sólo avanza uno de ellos.

3 Es decir, almacenamiento adicional a los datos que codifican la instancia del problema, que no se cuenta como parte de la complejidad espacial de ningún algoritmo.

Get Algoritmos de aprendizaje now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial