Optimizacion prog de sis

INSTITUO TECNOLOGICO SUPERIOR DE MISANTLA

NUEVAS TECNICAS DE OPTIMIZACION
PROGRAMACION DE SISTEMAS
Francisco Cardoso Torres
instituto tecnológico superior de misantla

INDICE

Introducción 1
Cómo elegir buenos algoritmos. 2
Notaciones asintóticas más utilizadas: 3
Órdenes de magnitud más frecuentes 4
Primer algoritmo: fuerza bruta. 5
Segundo algoritmo: búsqueda dicotómica obinaria 5
Cuándo y cómo optimizar 6
Técnicas de optimización de código 8
Elimina código innecesario 9
Saca código de los bucles 9
Pasar objetos por referencia mejor que por valor 9
Minimiza y optimiza el acceso a disco 10
Referencias: 14

Introducción

"La raíz de todos los males es la optimización prematura." - D. Knuth

La optimización es un tema complejo, que tiene comoobjetivo maximizar la eficiencia temporal y espacial de los programas. Las técnicas usuales se basan en:
Diseñar adecuadamente las aplicaciones.
Esto debería cumplirse para todo el software en general, pero es importante tener en cuenta que a mejor diseño, más facilidad y menos necesidad de optimización posterior.
Elegir buenos algoritmos.
Hemos de estudiar qué algoritmos se adaptan mejor a lasespecificaciones del problema a resolver. No sirve de nada realizar una excelente implementación de un algoritmo concreto si éste no es el más adecuado para nuestra tarea.
Intentar exprimir todo el potencial del hardware utilizado.
Para ello es necesario un gran conocimiento del hardware y de las herramientas de programación usadas. Debemos estudiar cómo organizar nuestro código, para que a suvez el compilador pueda generar código máquina de mayor calidad. En algunas ocasiones especiales merece la pena escribir nosotros mismos el código ensamblador, normalmente cuando se trata de hardware específico que el compilador no suele saber aprovechar.
Por ejemplo, las extensiones MMX de Intel o 3dnow! de AMD no serán totalmente  aprovechadas si no las programamos nosotros mismos, ya que loscompiladores no saben generar código MMX/3D Now! automáticamente.
 

Cómo elegir buenos algoritmos.
La correcta elección del algoritmo que ha de resolver nuestro problema es fundamental. He aquí algunos conceptos básicos sobre algoritmos.
Los dos recursos críticos que consumen los algoritmos son el espacio(memoria) y el  tiempo(velocidad). Siempre es preferible maximizar la velocidad ydisminuir el uso de memoria. 
Coste temporal - tiempo de CPU utilizado
Coste espacial - cantidad de memoria utilizada
Al tamaño de la entrada de datos del algoritmo se le llama complejidad del problema. Para poder comparar y/o medir la eficiencia de los algoritmos, necesitamos definir una medida válida para todos ellos.
La unidad de medida que usaremos será la notación asintótica. Es una notaciónque nos permite evaluar el ritmo de crecimiento de una función. No se pretende establecer el coste exacto de un algoritmo, sino evaluar esas magnitudes en función del volumen de datos de entrada.
Estudiaremos el rendimiento de los algoritmos para entradas de datos muy grandes (ya que es éste el caso en que la ineficiencia de un programa puede ser crítica). Siempre expresaremos la eficiencia enfunción del volumen de datos (complejidad).

Notaciones asintóticas más utilizadas:
O(f) | conjunto de funciones que crecen como máximo con la misma rapidez que f (define una cota superior del algoritmo) |
Ω(f) | conjunto de funciones que crecen con mayor o igual rapidez que f (define una cota inferior del algoritmo) |
Θ(f) | conjunto de funciones que crecen exactamente al mismo ritmo que f|
Órdenes de magnitud más frecuentes
Θ(1) | Constante | Son las funciones independientes del volumen de datos. | Ideal |
Θ(log n) | Logarítmico | Propio de algoritmos que descartan muchos valores(generalmente la mitad) en  un único paso. Aparece en estructuras de tipo árbol. | Eficientes |
Θ(n log n) | Casi lineal | Aparece en bucles en los que cada paso implica un coste logarítmico. |...