PDF de programación - Diseñando para un alto rendimiento

Diseñando para un alto

rendimiento

24 de julio de 2020

Una vez que ha escrito el código de trabajo, generalmente hay trabajo adi-
cional que hacer. Necesita su código no solo para cumplir su tarea, sino
también para hacerlo rápidamente. El rendimiento de su código es qué tan
bien utiliza recursos como la memoria y el tiempo. Se dice que el software
funciona a un nivel aceptable, lo que significa que utiliza los recursos de
manera eficiente y responde a las tareas dentro de un marco de tiempo
deseable, es eficiente.

El rendimiento del software afecta a las personas del mundo real todos los
días, ya sea que estén tratando de subir sus últimos selfies a Instagram o
haciendo análisis de mercado en tiempo real para elegir acciones. La forma
en que el software debe funcionar a menudo se reduce a la percepción del
usuario. Si algo se siente instantáneo, podría ser lo suficientemente rápido.

El rendimiento del software también puede afectar el resultado final. Si su
software requiere que almacene algo en un disco o en una base de datos,
minimizar la cantidad de almacenamiento requerida le ahorrará dinero. El
software que informa las decisiones de hacer dinero puede generarle más
dinero si se ejecuta más rápido. El rendimiento tiene un impacto en el mun-
do real.

1

Percepcion humana

Los humanos generalmente perciben los cambios más rápidos que
100 ms como instantáneos. Si hacen clic en un botón y la pantalla
responde en 50 ms, están contentos. A medida que la capacidad
de respuesta disminuye más de 100 ms, las personas comienzan a
notar el retraso.
Para actividades de larga duración como la descarga de archivos
grandes, el retraso no siempre se puede evitar. En estos casos, las
actualizaciones precisas del progreso son importantes porque cam-
bian la percepción del progreso para que se sienta más rápido.

1. Sufriendo a través del tiempo y el espacio

Si lees sobre software de alto rendimiento, es probable que encuentres las
frases complejidad del tiempo y complejidad del espacio. Estos términos
parecen sacados directamente de la mecánica cuántica o la astrofísica,
pero también tienen un lugar en el software.

La complejidad del tiempo y el espacio son medidas de cuánto más tiempo
de ejecución, memoria o almacenamiento en disco necesita su software a
medida que aumentan sus entradas. Cuanto más rápido su software con-
suma tiempo o espacio, mayor será su complejidad.

La complejidad no pretende ser una medida cuantitativa exacta; más bien,
le ayuda a comprender cualitativamente qué tan rápido y grande será su
software en el peor de los casos. En esta sección, lo ayudaré a construir
una intuición para las mediciones de complejidad para que pueda obtener
el rendimiento en su trabajo. Sin embargo, hay un proceso formal para
determinar la complejidad de su software, y lo abordaré en un momento.

2

1.1. La complejidad es un poco. . . compleja

No dudaré en decir nada al respecto: medir la complejidad puede ser difícil
y a veces es confuso. Para mí no tenía mucho sentido en la escuela: aprendí
lo que sé ahora a través de la aplicación práctica repetida. Prepárate para
hacer lo mismo.

Las determinaciones de complejidad se realizan a través de un proceso
llamado análisis asintótico, que implica observar el código y determinar los
límites de su peor desempeño.

Nota

Tenga en cuenta que las mediciones de complejidad se utilizan pa-
ra contrastar formas de lograr una tarea en particular; no son tan
útiles para comparar tareas no relacionadas. Es útil comparar dos
algoritmos para ordenar una lista de números, por ejemplo, pero no
puede comparar un algoritmo de clasificación de listas con un árbol
de búsqueda. Asegúrate de comparar manzanas con manzanas.

La notación utilizada en el análisis asintótico puede parecer críptica al prin-
cipio, pero tiene una traducción sencilla en inglés. Comúnmente verá la
complejidad escrita en notación O grande, lo que significa el peor rendi-
miento para el código que se analiza. La notación O grande se parece a
O(n2), a menudo leída como "orden n-cuadrado", donde n es el número
de entradas y n2 es la complejidad. Esto es la abreviatura de "la cantidad
de tiempo que tarda el código en ejecutarse aumenta proporcionalmente al
cuadrado del número de entradas", como se muestra en la figura 1. O(n2)
es mucho más rápido de escribir. Usaré la notación O grande más en el
resto del texto.

3

Figura 1: O(n2) es una abreviatura de notación O grande para una relación

y = x2.

1.2. Complejidad de tiempo

La complejidad del tiempo es una medida de la rapidez con que su código
puede realizar una tarea en relación con sus entradas. A medida que au-
menta el número de entradas, la complejidad del tiempo le indica a qué
velocidad se ralentizará su código. Esto puede ayudarlo a razonar sobre
cuánto tiempo debe llevar una tarea a medida que crece la escala de sus
entradas.

LINEALIDAD

La complejidad lineal es una de las complejidades más comunes que sur-
gen del código. Esta complejidad se llama así porque graficar el número de
entradas frente al tiempo produce una línea recta. Si piensa en la ecuación
para una línea en matemáticas, y = mx + b, puede pensar en x como el
número de entradas e y como el tiempo que le toma ejecutar su programa.
Puede haber algo de sobrecarga para su programa independientemente de
la entrada (la b, o la intersección, en la ecuación), y cada entrada adicio-

4

nal agrega una cierta cantidad de tiempo de ejecución (m, o la pendiente).
Esto se ilustra en la figura 2.

Figura 2: Visualizando una tarea con complejidad lineal

La complejidad lineal es frecuente en el software porque muchas operacio-
nes necesitan realizar alguna tarea para cada elemento de una lista: impri-
mir una lista de nombres, sumar una lista de enteros, etc. A medida que la
lista crece, la cantidad de tiempo que la computadora tiene que pasar crece
proporcionalmente. Sumar 1,000 enteros toma aproximadamente la mitad
del tiempo que sumar 2,000 enteros. Para cierto número de elementos, n,
este tipo de actividades son lineales con n o, en la notación O grande, O(n).

Puede detectar el código que probablemente sea O(n) en Python buscan-
do bucles. Es probable que un solo ciclo sobre una lista, conjunto u otra
secuencia sea lineal:

names = [’Aliya’, ’Beth’, ’David’, ’Kareem’]
for name in names:

print(name)

5

Esto sigue siendo cierto incluso si realiza varios pasos dentro del bucle:

names = [’Aliya’, ’Beth’, ’David’, ’Kareem’]
for name in names:

greeting = ’Hi, my name is’
print(f’{greeting} {name}’)

Incluso sigue siendo cierto si recorre la misma lista varias veces:

names = [’Aliya’, ’Beth’, ’David’, ’Kareem’]
for name in names:

print(f’This is {name}!’)

message = ’Let\’s welcome ’
for name in names:

message += f’{name} ’

print(message)

Aunque está recorriendo la lista de nombres dos veces, piénselo de nuevo
en términos de la ecuación para una línea. El primer ciclo lleva algo de
tiempo, f, por elemento, y el segundo ciclo lleva algo de tiempo, g, por
elemento. La ecuación lineal sería algo así como y = fx + gx + b, que es
equivalente a y = (f + g)x + b. Sigue siendo una línea, incluso si es más
pronunciada.

Aquí es donde entra en juego la parte "asintótica" del análisis asintótico.
Aunque una actividad particular puede ser abruptamente lineal, otras ope-
raciones más complejas aún pueden superarla si las entradas son lo sufi-
cientemente numerosas, como se muestra en la figura 3.

6

Figura 3: Complejidad de orden superior a grandes escalas

PROPORCIONAL AL CUADRADO

Otro tipo de complejidad temporal es proporcional al cuadrado de las en-
tradas (O(n2)). Esto surge en los casos en los que, para cada elemento de
una lista, debe mirar todos los demás elementos de la lista. A medida que
agrega más entradas, su código debe iterar sobre los elementos adiciona-
les, pero también debe iterar sobre esos elementos adicionales en cada
una de esas iteraciones. El aumento en el tiempo de ejecución se agrava.

Puede detectar esto en el código Python por la presencia de bucles anida-
dos. El siguiente código verifica si una lista tiene elementos duplicados:

def has_duplicates(sequence):

# Ref_1
for index1, item1 in enumerate(sequence):

# Ref_2
for index2, item2 in enumerate(sequence):

# Ref_3

if item1 == item2 and index1 != index2:

return True

return False

7

Ref_1 El bucle externo itera sobre cada elemento de la secuencia.

Ref_2 El ciclo interno itera sobre cada elemento nuevamente, para cada

elemento en el ciclo externo.

Ref_3 Comprueba si dos elementos tienen el mismo valor, pero no el mis-

mo elemento específico de la secuencia

O(n2) es el peor caso para este código porque incluso si solo los últimos ele-
mentos son duplicados, o si no existen duplicados, el código todavía tiene
que iterar sobre todas las entradas antes de que finalice. Si los dos pri-
meros elementos son duplicados, el código será mucho más rápido porque
puede detenerse de inmediato, pero es útil examinar el peor de los casos
para tener una mejor idea de lo que el código es capaz de hacer. La nota-
ción Big O siempre mide la complejidad del código en el peor de los casos
por este motivo.

Anotaciones adicionales

A veces es útil calcular no solo el peor de los casos, sino también
el caso promedio y el mejor. La notación Ω grande (omega grande)
se usa para el análisis del mejor caso, y la notación Θ grande (theta
grande) se usa para expresar que los límites superior e inferior son
de la complejidad especificada. Por lo general, estos pueden ayu-
darlo a elegir el enfoque que mejor se adapte a lo que está tratando
de lograr de varias opciones. La complejidad de muchos algoritmos
se puede encontrar buscando en línea, como por ejemplo, "comple-
jidad de clasificación rápida". También puede encontrar la compleji-
dad temporal de algunas operaciones comunes en los documentos
de Python (https://wiki.python.org/moin/TimeComplexity).

TIEMPO CONSTANTE

La complejidad ideal es el tiempo constante (O(1)), que no depende del
tamaño de las entradas