Martes 20/08/19

Punteros: Arrays y aritmética

Declarar un array como int vec [5] es asignar un contiguo bloque de memoria. La variable vec es un puntero al primer elemento del array.

Referencias

Significa casi lo mismo que un puntero, aunque es más usado en el contexto de pasar parámetros. Puntero se usa más en C++ y referencia en otros lenguajes. C++ soporta el tipo de dato referencia.

Pasar parámetros en C++

Existe paso de parámetros por valor y por referencia.

Por valor: El caller no va a ver los cambios hechos por el callee a los parámetros pasados. El callee recibe una copia independiente del parámetro.

Por referencia: Pasar un parámetro por referencia es recibir un puntero a un parámetro. El caller ve los cambios hechos por el callee.

En C++ existen new y delete que son equivalentes a malloc en C++.

Tarea moral

Aprender qué hace el operador ->.

Garbage collector: Hace un mapeo de todas las referencias en el heap. Tiene dos fases: Fase de marcado: Identifica las fases del heap que están siendo utilizadas y las que no. Fase de reclamación: Todas las celdas de memoria las retorna al memory pool.

Jueves 22/08/19

Realizamos el quiz 2.

Algoritmo

Conjunto de instrucciones finitas y ordenadas para resolver un problema. Las instrucciones son computables y dan un resultado en un tiempo finito.

Un algoritmo es:

❅ Ordenado

❅ Finito

❅ Determinístico

❅ Efectivo

❅ Con input/output

Eficaz: Cumplir con las tareas que quería.

Eficiente: Hacerlo de la forma más óptima.

Análisis de algoritmos

• Metodología para estimar el consumo de recursos de un algoritmo.

• Se analizan algoritmos para ver si me va a servir en lo que yo necesito.

• Comparar con otros que tienen la misma funcionalidad para saber cuál es el mejor.

• Permite clasificar problemas por dificultad.

• Permite predecir el rendimiento para poder tomar decisiones.

• Mejor entendimiento de los algoritmos y por ende, podemos mejorarlos.

Factores que afectan el runtime de un algoritmo:

☼ CPU, memoria, disco

☼ Compilador

☼ Lenguaje de programación

☼ Sistema operativo

☼ Desarrollador

☼ Tamaño del input

☼ Aplicaciones que se estén ejecutando en el computador

¿Cómo deberia comparar el algoritmo para saber quién es mejor?

• Tiempo (CPU): ¿Cuánto tiempo dura ejecutándose en una máquina específica?

• Espacio(Disco/Memoria) ¿Cuánto espacio consume el programa?

• Otros:

• Ancho de banda

• Dispositivos perifeŕicos

Formas de saber cuál algoritmo es más eficiente

• Empírica: Benchmark. Hago un zip y veo cual archivo ocupa menos espacio.

• Simulacional: Probar cuando la carpeta tiene x dato. Pero lo malo es que no se puede probar con todas las posibilidades.

• Analítico: Modelo matemático (tiempo y espacio).

Complejidad Computacional

Clasifica el tiempo que toma un algoritmo.

✹ Representa un algoritmo en función del tamaño del input.

✹ Se enfoca en operaciones dominantes (primitivas)

✹ Es estimado por conteo de instrucciones elementales.

✹ Se analiza la tasa de crecimiento de la función.