¿Un código siempre se puede optimizar o existe un límite que sería la manera perfecta de hacerlo?

Estuve leyendo las respuestas y casi todas cubren la optimización desde el punto de vista del hardware, el compilador o con características propias del lenguaje de programación, y todo eso es correcto. Sin embargo, hay algo que están pasando por alto y es la optimización del tiempo y memoria del algoritmo en sí.

Si hablamos de tiempo, podemos poner este ejemplo: la búsqueda secuencial tiene una complejidad O(n)O(n) en el peor de los casos. Eso significa que si tuvieras una lista de 10 elementos y por mala suerte, el elemento que buscas está al final, necesitarás revisar 10 veces hasta encontrar lo que buscas. Si la lista tuviera 1000 elementos, ahora necesitas buscar 1000 veces.

Sin embargo, si la lista esta ordenada se puede hacer algo genial: se puede buscar en la mitad si el elemento está presente. Si no, se puede descartar una mitad completa y buscar de nuevo en la otra mitad. En el ejemplo adjunto, estamos buscando el número 7.

Fuente de la imagen: Búsqueda binaria - Wikipedia, la enciclopedia libre

En el peor de los casos, necesitaremos buscar en log2log2 pasos. Para una lista de 1000 elementos, log21000=9.94log21000=9.94. Redondeando, ¡10 pasos! Hemos optimizado la búsqueda con un algoritmo de complejidad O(logn)O(logn)y bajado el número de pasos de 1000 a solo 10. ¡100 veces más eficiente!

Otro punto que se puede optimizar es el uso de memoria. Por ejemplo, si tenemos una lista de 100 personas, con 1MB de datos por persona, en la memoria del computador se consumirá 100MB. En estos tiempos, totalmente posible. Sin embargo, si tuviéramos una lista de 10 millones de personas, necesitaríamos 10 millones de MB, o sea, 10TB de memoria RAM, algo que sería estúpidamente caro.

Una forma de optimizar la memoria sería tener los 10TB en disco (que es más barato) y cargar 1000 personas a la vez, necesitando solo 1GB de memoria. Se procesa ese batch, se borra de memoria y se cargan otros 1000, y así sucesivamente hasta procesar los 10 millones. Hemos reducido el costo de la memoria 10 mil veces (si el costo fuera lineal), necesitando 1GB en vez de 10TB.

En general, se llega a un punto donde hay que elegir entre tiempo y memoria. Si queremos que vaya rápido, necesitaremos usar más memoria. Si queremos ahorrar memoria, necesitaremos aceptar que irá más lento. Como siempre, elegir uno u otro va a requerir entender los requerimientos del programa (objetivo, cantidad de datos, tiempo esperado para ejecutar, etc.)