Ordenamiento y optimización
Transcript of Ordenamiento y optimización
2
ÍNDICE
1. Unidad 1: Estructura de los datos y algoritmos ...................................................3
Tema 2: Ordenamiento y optimización ......................................................................... 3
Objetivo: ........................................................................................................................ 3
Introducción: ................................................................................................................. 3
2. Información de los subtemas .............................................................................5
2.1 Subtema 1: Tipos de ordenamiento: por selección, por intercambio - burbuja,
por inserción .................................................................................................................. 5
2.2 Subtema 2: Evaluación de tiempos de procesamiento ...................................... 8
2.3 Subtema 3: Recursividad y pruebas de estrés .................................................. 10
2.4 Subtema 4: Ejercicios de aplicación ................................................................. 13
3. Bibliografía ...................................................................................................... 15
Ordenamiento y optimización
3
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
1. Unidad 1: Estructura de los datos y algoritmos
Tema 2: Ordenamiento y optimización
Objetivo:
Estudiar el problema de ordenamiento de un array de elementos sobre los
cuales se puede establecer una relación de orden.
Introducción:
La aplicación del proceso de ordenación es fundamental en el área de la computación.
Ya que la mayoría de los datos que se producen por un programa están ordenados de
alguna u otra manera. Al estar ordenada esta información sea de forma descendente,
ascendente o alfabética, los procesos que se ejecuten con el programa a futuro serán
más eficientes y optimizarán tiempos (Joyanes Aguilar, 2008).
El algoritmo de ordenamiento ubica los elementos de un vector, tomando en cuenta
una secuencia establecida lo cual creará una relación de orden. El resultado de salida
del ordenamiento será una permutación o reordenamiento de los elementos de
entrada que va a satisfacer la relación de orden que se dio a los elementos que forman
la lista o vector (Joyanes Aguilar, 2008).
Clasificación de los Algoritmos de ordenamiento
Los algoritmos de ordenamiento se clasifican de la siguiente manera (Joyanes Aguilar,
2008):
1. Algoritmos de ordenamiento interno: este tipo de algoritmo es considerado el
más rápido en la memoria del ordenador.
2. Algoritmos de ordenamiento externo: este tipo de algoritmo se almacenan en un
lugar externo como un disco duro, y a diferencia de los algoritmos de
ordenamiento esos son considerados los menos rápidos.
3. Algoritmos de ordenación natural: este tipo de algoritmo trata de optimizar los
tiempos y tarda lo mínimo posible cuando la entrada de los elementos está
ordenada.
4. Algoritmos de ordenación no natural: este tipo de algoritmo a diferencia del antes
mencionado tarda lo mínimo posible cuando la entrada está inversamente
ordenada.
Ordenamiento y optimización
4
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
El proceso de ordenamiento de los elementos puede aplicarse tanto a vectores
(unidimensionales) como a matrices (bidimensionales).
Ejemplo:
Imagen 1. Ordenamiento de vector
Fuente: (Joyanes Aguilar, 2008)
Ordenar ascendentemente el vector.
7, 3, 2, 1, 9, 6, 7, 5, 4
Nuevo vector ordenado
1, 2, 3, 4, 5, 6, 7, 7, 9
Ordenamiento y optimización
5
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
2. Informacio n de los subtemas
2.1 Subtema 1: Tipos de ordenamiento: por selección, por intercambio - burbuja, por inserción
Para los procesos de ordenamientos que a continuación se detallan es necesario que
consideremos y dejemos claro que para cualquiera de ellos que apliquemos debemos
conocer los elementos fundamentales de ordenamiento que son la comparación y el
movimiento de los elementos en el vector (Guardati Buemo, 2007).
Ordenación por selección o Selection Sort
El tipo de ordenamiento por selección busca en el vector el menor elemento y lo
coloca en la primera posición del mismo vector, este proceso se lo realiza
sucesivamente hasta que los elementos del vector se hayan ordenado correctamente y
en función de la orden dada (Joyanes Aguilar, 2003). Es necesario aclarar que el
ordenamiento por lección se lo puede realizar de forma ascendente y descendente.
A continuación se muestra un ejemplo de ordenamiento de un vector con 10
elementos, en el ejemplo veremos cómo se aplica el método que se explicó en párrafo
anterior.
Imagen 2. Ordenación de arreglo, método de inserción
Fuente: (Joyanes Aguilar, 2003)
Ordenamiento y optimización
6
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
Método de intercambio o de burbuja
Este método es muy sencillo y su principio básico de ejecución es comparar los pares
de los elementos adyacentes del vector para posteriormente cambiarlos entre sí de tal
manera que los elementos se encuentren ordenados (Guardati Buemo, 2007).
A continuación se muestra un ejemplo haciendo uso del método. Se pide ordenar en
forma ascendente el vector propuesto a continuación.
50 15 56 14 35 1 12 9
A [1] A [2] A [3] A [4] A [5] A [6] A [7] A [8]
Imagen 3. Ordenación de arreglo, método de burbuja
Fuente: (Guardati Buemo, 2007)
Para aplicar este método se realizarían los siguientes pasos (Joyanes Aguilar, 2008):
1. Se compara el elemento A [1] y A [2]; en caso de estar en orden, se mantienen sin
cambio, de lo contrario se realiza el proceso de intercambio de las posiciones entre sí.
2. Como siguiente paso se comparan los elementos de la posición [2] y [3]; solo se
intercambiarán si es necesario, es decir si no están en orden.
3. El proceso se ejecutará hasta que cada uno de los elementos del vector haya sido
cotejado con sus elementos adyacentes o predecesores y que se hayan realizado el
proceso de intercambio necesario para que se ordene en función de la orden dada.
A continuación veremos el arreglo totalmente ordenado.
1 9 12 14 15 35 50 56
A [1] A [2] A [3] A [4] A [5] A [6] A [7] A [8]
Imagen 4. Arreglo ordenado por método burbuja
Fuente: (Guardati Buemo, 2007)
Ordenación por inserción o insertion sort
Este método de ordenación tiene como finalidad el insertar un elemento en el vector,
esto sin afectar el orden que ya tiene el vector, para posteriormente comenzar
nuevamente con los elementos del vector que aún falten. Este método también se
conoce como el método de la baraja (Guardati Buemo, 2007).
A continuación se muestra un ejemplo aplicando el método de inserción, con un vector
cuyos elementos están desordenados.
Ordenamiento y optimización
7
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
Imagen 5. Arreglo desordenado para aplicar método de inserción
Fuente: (Guardati Buemo, 2007)
Para insertar el elemento 45 que es el elemento que se debe ordenar en el vector, se
tendrá que insertar entre los elementos 43 y 65, para lo cual se deberá mover hacia la
derecha los elementos cuyo valor sea superior a 45, se saltará sobre los elementos 65
y 84 como se muestra en la Imagen 6.
Imagen 6. Arreglo ordenado por método de inserción
Fuente: (Guardati Buemo, 2007)
Como se puede visualizar en el ejemplo el método de inserción consiste en realizar
comparaciones y desplazamientos de manera sucesiva hasta que los elementos del
vector se ordenen. Es necesario que se considere que este proceso sucesivo se
realizará siempre desde el segundo elemento o posición del vector (Joyanes Aguilar,
2008).
Ordenamiento y optimización
8
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
2.2 Subtema 2: Evaluación de tiempos de procesamiento
Al desarrollar cualquier algoritmo, es necesario que consideremos la evaluación y
optimización de los tiempos de procesamiento, la optimización se obtiene de realizar
una correcta elección de algoritmo y estructura de datos, esto hará referencia al
análisis cuidadoso de su desempeño para identificar y analizar las fallas y por ende
concebir mejoras antes de ejecutar dicho algoritmo (Guardati Buemo, 2007).
El evaluar eficiente los tiempos no es una tarea sencilla, y estos resultados podrían
variar de un ordenador a otro (Joyanes Aguilar, 2003). También debemos considerar
que la cantidad de factores pueden influir lo cual conlleva un tiempo de ejecución o
procesamiento extenso.
A continuación se mencionan varios de los factores que pueden influir en lo antes
indicado:
1. Algoritmo usado
2. Sistema operativo
3. Velocidad del procesador, número de procesadores y conjunto de instrucciones
que entiende
4. Cantidad de memoria RAM, y caché, y velocidad de cada una
5. Coprocesador matemático, GPU
Muchas veces podemos ver que en el mismo equipo, el algoritmo tarda muchas veces
más tiempo en dar respuesta en comparación a otras, esto debido al tiempo que
consumen otras aplicaciones que se están ejecutando al mismo tiempo, o quizás si no
se cuenta con la suficiente memoria RAM en el momento de ejecutar el programa o
algoritmo (Joyanes Aguilar, 2008).
Las pruebas de rendimiento a un programa o algoritmo se ejecutan para caracterizar y
evaluar las ciertas características que se relacionen con el rendimiento u objetivo de la
prueba. A lo largo del ciclo de vida del desarrollo de software, se implementan varios
tipos de prueba de rendimiento, cada una con un objetivo de prueba diferente
(Joyanes Aguilar, 2008).
La evaluación del rendimiento del sistema suele realizarse en combinación con el
representante del usuario y desde un enfoque de varios niveles (IBM, 2006).
1. El primer nivel de análisis de rendimiento implica la evaluación de los
resultados para un solo actor o instancia de caso de uso y la comparación de
resultados en varias ejecuciones de la prueba (IBM, 2006).
Por ejemplo, capturar el comportamiento de rendimiento de un solo actor que
realiza un solo caso de uso sin otra actividad en el destino de la prueba y
Ordenamiento y optimización
9
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
comparar los resultados con varias ejecuciones de prueba del mismo actor o
caso de uso. Este análisis de primer nivel puede ayudar a identificar las
tendencias que podrían indicar la contienda entre recursos del sistema, que
puede afectar a la validez de las conclusiones que se extraigan de otros
resultados de pruebas de rendimiento.
2. En un segundo nivel de análisis se examina los valores de datos reales y las
estadísticas de resumen para la ejecución de casos de uso o actores específicos
y el comportamiento del rendimiento del destino de la prueba realizada.
Un tercer análisis puede ayudarle a comprender las causas y el significado de los
problemas de rendimiento que se estén dando. Este análisis detallado toma los datos
de bajo nivel y utiliza métodos estadísticos para ayudar a los verificadores a extraer las
conclusiones correctas de los datos. El análisis detallado proporciona criterios
objetivos y cuantitativos para tomar decisiones, pero requiere más tiempo y un
conocimiento básico de estadística.
Ordenamiento y optimización
10
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
2.3 Subtema 3: Recursividad y pruebas de estrés
La recursividad es una propiedad que se da a las funciones que se vayan a utilizar
dentro de un programa o algoritmo, esta propiedad permite a la función llamarse así
misma o también llamar a otras funciones. La aplicación de la recursión en funciones
permite a los programadores determinar o desarrollar soluciones naturales, sencillas,
que comúnmente serían muchas veces difíciles de resolver (Joyanes Aguilar, 2008).
Al ejecutar una función recursiva ésta deberá contener al menos una definición
explícita para que se ejecute, caso contrario esta recursividad podría caer en un ciclo
infinito, es decir no tendría finalización.
En ocasiones se suelen confundir los conceptos de recursividad e iteración, pero
debemos tener clara su diferencia; la primera tiene que realizar constantemente
llamadas a las funciones que tiene en el algoritmo o programa, mientras que la
iteración no requiere de tantas llamadas.
Recursión Vs Iteración
Ambas acciones dentro de la programación se basan a una estructura de control. Cada
una con una diferencia particular la iteración utilizará una estructura de control
repetitiva, mientras que la recursión utilizará una estructura de selección.
La recursión tiene muchas desventajas, una de ellas es debido a que se ejecuta en
repetidas ocasiones el proceso de recursividad, lo cual provoca consumir más tiempo
de lo normal para realizar las invocaciones de la función.
El uso de la recursividad muchas veces resulta demasiado costoso en relación al
tiempo de procesado y al espacio de memoria que se esté utilizando. Las llamadas
recursivas producen que otra copia de la función sea creada; lo cual puede consumir
memoria de manera considerable. Mientras que la iteración por lo contrario se
produce dentro de una función, por lo cual la operación o acción de llamada a la
función y asignación de memoria adicional serán omitidas ahorrando tiempos de
respuesta (Joyanes Aguilar, 2008).
Tipos de recursividad
Recursividad Directa
Es recursividad de tipo directa cuando la función efectúa una llamada a sí misma.
Ejemplo. La función A mediante una sentencia invoca a A.
Ordenamiento y optimización
11
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
Recursividad indirecta
Por otro lado la función recursiva de tipo indirecta, se ejecuta o realiza cuando la
función llama a otra función, misma que de manera directa o indirecta puede llamar a
la función principal (Joyanes Aguilar, 2008).
Recursión Infinita
Una recursión infinita se dará cuando la etapa de la recursión no reduce el problema
en cada ciclo que esta se ejecute (Joyanes Aguilar, 2003). Dicho de otra manera, esta
recursión se ejecutará las n veces que sea necesaria.
Se deberán considerar que dentro de la recursividad se apliquen 3 condiciones para su
terminación formal:
1. Una condición de salida para detener o continuar el proceso de
recursión.
2. Deberá existir una llamada recursiva.
3. Deberá existir un caso final para finalizar la recursión.
Pruebas de estrés
Las pruebas de estrés ayudarán a encontrar el volumen de datos o instante de tiempo
en el que la aplicación comienza a fallar o no da respuesta a las peticiones que se
están realizando. Por lo general esta prueba supera los límites esperados en el
ambiente de producción o aquellos determinados en la etapa de pruebas (Jmeter
apache, 2019) .
Un ejemplo de la aplicación de las pruebas de estrés es encontrar la cantidad de
usuarios que acceden simultáneamente a una aplicación, e identificar en qué
momento la aplicación deja de responder en forma correcta a todas las peticiones que
los usuarios están realizando.
El realizar este tipo de pruebas busca encontrar cuellos de botella que existan en el
programa de distintas formas, considerando el uso de diferentes herramientas de
código abierto o licenciadas las cuales se basan en parámetros predefinidos para
determinar su análisis.
Una de estas herramientas es la conocida aplicación de código abierto APACHE JMETER
la cual permite probar el rendimiento de recursos estáticos o dinámicos, así mismo
aplicaciones web dinámicas. De igual manera se puede simular cargas pesadas en
servidor, grupos de servidores, red u objetos para probar su resistencia o análisis
Ordenamiento y optimización
12
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
generales de rendimiento bajo diferentes tipos de cargas. Las características que
incluye esta aplicación son las siguientes (Jmeter apache, 2019):
1. Cargar y probar el rendimiento de aplicaciones, servidores y/o tipos de
protocolos diferentes como por ejemplo:
a. Web:http,https (Java, NodeJS, PHP, ASP.NET)
b. Servicios web soap / rest
c. FTP
d. Bases de Datos mediante conector JDBC
e. LDAP
f. Middleware orientado a mensajes (MOM) a través de JMS
g. Correos SMTP, POP3 y/o IMAP
h. Comandos nativos o script de Shell
i. TCP
j. Objetos nativos Java
2. Prueba IDE
3. Modo por línea de comando
Generación de informe HTML dinámico, entre otros.
Ordenamiento y optimización
13
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
2.4 Subtema 4: Ejercicios de aplicación
1. La Se creará una función recursiva para calcular el factorial de un número,
además de generar un programa n el cual se maneje la función (Franco, 2016).
Imagen 7. Aplicación de recursividad
Fuente: (Franco, 2016)
Al utilizar o poner a prueba la función Factorial en la ventana de comandos para
calcular factorial de 4, 4!, nos dará como respuesta.
Imagen 8. Respuesta de proceso de recursividad
Fuente: (Franco, 2016)
2. Se deberá crear una función donde se calcule el Fibonacci de un número de
modo recursivo. Además de un programa que use la función, para que calcule
el valor del elemento considerando la posición que ocupa en la serie (Franco,
2016).
Imagen 9. Aplicación de recursividad
Fuente: (Franco, 2016)
Ordenamiento y optimización
14
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
Al corroborar la función Fibonacci en la ventana de comandos para calcular el término
8 de la sucesión.
Imagen 10. Respuesta de proceso de recursividad
Fuente: (Franco, 2016)
Ordenamiento y optimización
15
© U
niv
ersi
dad
Est
atal
de
Mila
gro
– U
NEM
I
FORMATO CONTROLADO: FR0018/ v1.0 / 18-11-2019
3. Bibliografí a
» Franco, Á. (2016). Funciones recursivas. Retrieved February 23, 2020, from
http://www.sc.ehu.es/sbweb/fisica3/basico/recursiva/recursiva.html
» Guardati Buemo, S. (2007). Estructura de Datos Orientada a Objetos.
Algoritmos con C++. Retrieved from
https://www.academia.edu/6122916/Estructura_De_Datos_Oientada_A_Objet
os
» IBM. (2006). Prueba de rendimiento. Retrieved February 23, 2020, from
https://cgrw01.cgr.go.cr/rup/RUP.es/LargeProjects/core.base_rup/guidances/c
oncepts/performance_testing_37A31809.html
» Jmeter apache. (2019). Apache JMeter. Retrieved February 23, 2020, from
https://jmeter.apache.org/
» Joyanes Aguilar, L. (2003). Fundamentos de programacion: Libro de problemas.
Algoritmos, estructuras de datos y objetos (2a. ed.). (C. Fernández Madrid, Ed.)
(Segunda ed). Retrieved from www.fullengineeringbook.net
» Joyanes Aguilar, L. (2008). Fundamentos de Programación. (J. L. G. y C.
Sánnchez, Ed.) (Cuarta). España: Mc Graww Hill. Retrieved from
https://combomix.net/wp-content/uploads/2017/03/Fundamentos-de-
programación-4ta-Edición-Luis-Joyanes-Aguilar-2.pdf