Algoritmos Eficientes - Historial de revisiones

Niurka ciget.cav en 19:01 16 jun 2011

2011-06-16T19:01:45Z

Arletisjcconsolacion en 15:17 16 jun 2011

2011-06-16T15:17:28Z

Rosy en 12:32 15 jun 2011

2011-06-15T12:32:24Z

Rosy en 12:31 15 jun 2011

2011-06-15T12:31:35Z

Rosy en 12:26 15 jun 2011

2011-06-15T12:26:34Z

Rosy en 12:21 15 jun 2011

2011-06-15T12:21:10Z

Rosy en 12:18 15 jun 2011

2011-06-15T12:18:29Z

Rosy en 12:17 15 jun 2011

2011-06-15T12:17:14Z

Rosy en 12:16 15 jun 2011

2011-06-15T12:16:04Z

Rosy: Página creada con ' Diseño de Algoritmos Eficientes '''Objetivos:''' Mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución. Se toma como ejemplo la bú...'

2011-06-15T12:14:55Z

Página creada con ' Diseño de Algoritmos Eficientes '''Objetivos:''' Mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución. Se toma como ejemplo la bú...'

Página nueva

[[Diseño de Algoritmos Eficientes]]
'''Objetivos:''' Mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución. Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].
Temas:

Búsqueda secuencial en arreglos.
Búsqueda binaria en arreglos.
Análisis de algoritmos.
Búsqueda binaria recursiva.

Motivación
Se tiene un archivo post.dat con los datos de los alumnos que dieron la PAA. Cada línea de este archivo contiene el carnet de identidad (c.i.) y el nombre de un postulante. Se tiene un segundo archivo mat.dat con los puntajes de los alumnos en la prueba específica de matemáticas. Cada línea contiene el c.i. de un alumno seguido de su puntaje. Por ejemplo, el contenido de ambos archivos podría ser:

post.dat mat.dat
-------- -------
11456789-6:Juan Gonzalez:... 12245894-7:715
12245894-7:Pedro Fernandez:... 11478387-1:801
... ...
Del archivo se concluye que Pedro Fernandez obtuvo 715 puntos. Observe también que no todos los alumnos dan la prueba de matemáticas por lo que el archivo mat.dat contiene menos líneas que post.dat. Los postulantes a las universidades son uno 150000 alumnos y los que dan la prueba de matemáticas unos 100000.
El problema consiste en producir un archivo post-mat.dat que contenga una línea por cada postulante que da la prueba de matemáticas con su nombre y su puntaje. Por ejemplo:

12245894-7:Pedro Fernandez:715
11478387-1:Alberto Fuenzalida:612
...
Lectura de un archivo con delimitadores Hasta el momento los archivos que hemos usado en el curso están estructurados de modo que cada campo de datos tiene un largo fijo. Por lo tanto, es sencillo extraer el campo de la línea completa por medio de la función substring. Sin embargo este mecanismo es demasiado frágil ya que es fácil equivocarse en la posición exacta de los datos en el archivo.
Por esta razón, en la biblioteca del curso se incluyó un mecanismo más robusto para leer archivos con campos de datos. La idea es que los archivos se deben estructurar de modo que los campos de datos estén separados por un delimitador (típicamente ":"). Este delimitador se especifica al crear el lecto o el escritor del archivo. Al leer un archivo, la clase TextReader se encarga transparentemente de ubicar el delimitador y extraer el campo de datos. Del mismo modo, al escribir en el archivo, la clase TextWriter agrega transparentemente el caracter delimitador para separar los campos.
A modo de ejemplo, el siguiente código lee el archivo post.dat y deja el contenido en dos arreglos de nombres cis y nombres:

TextReader lect= new TextReader("post.dat", ":");
String[ ] cis= new String[1000];
String[ ] nombres= new String[1000];
int i= 0;
while (!lect.eofReached()) {
cis[i]= lect.readString();
nombres[i]= lect.readString();
lect.skip();
i++;
}
int nalum= i;
En general, el patrón de lectura que usaremos de acá en adelante es:

TextReader lect= new TextReader(... nombre ..., ":");
...
while (!lect.eofReached()) { // termina si se acabó el archivo
...= lect.read...(); // lee un campo
...= lect.read...(); // lee otro campo
... // el resto de los campos
lect.skip(); // cambia de línea
... // procesa la línea
}
Del mismo modo, para escribir en un archivo separado con delimitadores se usará el patrón:

TextWriter escr= new TextWriter(... nombre ..., ":");
...
while (...) {
...
escr.print(...); // escribe un campo
escr.print(...); // escribe otro campo
...
escr.println(...); // escribe el último campo y cambia de línea
}
Primera solución (ineficiente)
Por cada línea del archivo mat.dat:

Se obtiene el c.i. del postulante.
Se busca ese c.i. en el archivo post.dat.
Se escribe el c.i., el nombre y el puntaje en post-mat.
Problema: Con los procesadores y discos modernos se puede leer un archivo con 150000 líneas en un segundo aproximadamente. Pero como hay que leerlo 100000 veces, el programa tardará 100000 segundos. ¡Es decir 28 horas! Este tiempo es inaceptable.

Búsqueda secuencial en arreglos Leer de disco un archivo de 150000 líneas es ineficiente. Se puede mejorar el tiempo si se leen las 150000 líneas y se colocan en 2 arreglos en memoria:

Con esto, el programa no cambia en esencia, solo que ahora se busca cada c.i. en memoria y no en disco. Como accesar datos en memoria es más eficiente que accesarlos en disco, se puede disminuir el tiempo en un factor 10. Es decir reducir el tiempo a poco menos de 3 horas (lo que todavía es inaceptable).
Para resolver el problema , se decide escribir una función que busca un string x en un arreglo a y entrega en qué posición se encuentra:

int buscarSec(String x, String[ ] a, int n) {
int i= 0;
while (i<n) {
if (compare(x, a[i])==0)
return i;
i= i+1;
}
return -1; // No se encuentra en el arreglo
}
Este tipo de búsqueda se denomina búsqueda secuencial en arreglos, porque se visitan los elementos en secuencia: el elemento 0, el 1, 2, ..., y así hasta encontrar el elemento que contiene el valor buscado.
¿Cuantas iteraciones toma el ciclo?

Peor caso: n iteraciones.
Mejor caso: 1
Caso promedio: n/2 aprox.
Para concretar la solución del problema el programa que escribe el archivo post-mat.txt es:

lect= new TextReader("mat.dat", ":");
TextWriter escr= new TextWriter("post-mat.dat", ":");
while (!lect.eofReached()) {
String carnet= lect.readString();
int ptje= lect.readInt();
lect.skip();
// Obtenemos la posicion de carnet en el arreglo cis
int k= buscarSec(carnet, cis, nalum);
if (k==-1)
println("no se encontro el carnet "+carnet);
else {
escr.print(carnet);
escr.print(nombres[k]);
escr.println(ptje);
}
}
Búsqueda binaria Si el arreglo cis está ordenado de menor a mayor (en orden lexicográfico), se puede escribir una función de búsqueda mucho más eficiente.
Para buscar x en un arreglo a:

Comparar x con el elemento que se encuentra en la mitad.
Si x es igual, entonces ese es el índice.
Si x es menor, buscar en la primera mitad.
Si x es mayor, buscar en la segunda mitad.
Si en algún momento, el intervalo de búsqueda se hace vacío, entonces x no está en el arreglo. El función es:

int buscarBin(String x, String[ ] a, int n) {
int imin= 0;
int imax= n-1;
while (imin<=imax) {
int icentro= (imin+imax)/2;
int comp= compare(x, a[icentro]);
if (comp==0)
return icentro;
if (comp<0)
imax= icentro-1;
else
imin= icentro+1;
}
return -1; // No se encuentra en el arreglo
}
Este tipo de búsqueda se llama búsqueda binaria, porque en cada iteración se divide por 2 el tamaño del intervalo de búsqueda.
Observe que la función tiene más líneas que la búsqueda secuencial y que para realizar cada iteración hay que realizar más trabajo. La pregunta es entonces ¿Cuál es mejor?

Análisis de la búsqueda secuencial El análisis de un algoritmo consiste en estimar el tiempo que toma ese algoritmo en función del tamaño de los datos que debe manipular. Normalmente se prefiere expresar estos tiempos en una unidad independiente de la velocidad del procesador. Por ejemplo, para la búsqueda secuencial se puede usar como unidad el tiempo que toma ejecutar una iteración del ciclo. En este caso, ese tiempo es un valor constante (aunque varía según la velocidad del procesador, pero no significativamente).
Normalmente, el criterio que se usa para comparar algoritmos son los tiempos de ejecución para valores de n grandes, siendo n el tamaño de los datos.
Notación O(f(n))
Para indicar cuál es la complejidad de un algoritmo se usa la notación O(f(n)). Se dice que un algoritmo toma tiempo O(f(n)) si existe un k y c tal que para todo n>=k siempre se verifica:

tiempo de ejecución para tamaño n <= c*f(n)
Esto significa que el tiempo de ejecución crece a lo más al ritmo de f(n) salvo por un factor constante.
Por lo tanto, la búsqueda secuencial toma, en el peor caso, tiempo O(n), es decir tiempo proporcional al número de elementos en el arreglo. En el caso promedio toma tiempo O(n/2) pero esto es lo mismo que O(n).
Por lo tanto, si se necesita buscar un elemento, la búsqueda secuencial toma un tiempo razonable, pero no olvide que para resolver nuestro problema inicial se necesitan realizar 100000 búsquedas de este tipo, con n=150000.
Análisis:

Mejor caso: 1 iteración.
Peor caso: log2 n iteraciones.
Caso promedio: un poquito mejor que log2 n.
Por lo tanto el tiempo de ejecución toma tiempo O(log n).
Para el caso en que n es 150000, una búsqueda binaria necesitará sólo 18 iteraciones del ciclo (en el peor caso). Es decir 4000 veces menos iteraciones que en la búsqueda secuencial. Pero cada iteración ahora es un poco más compleja. Digamos 2 veces más compleja y por lo tanto toma el doble de tiempo. Comparemos entonces los tiempos al realizar 100 mil búsquedas secuenciales y 100 mil búsquedas binarias:

Tipo de Iteraciones en Iteraciones Costo por Tiempo Búsqueda función de n cuando n=150000 iteración Total Secuencial O(n) 75000 (promedio) 1 2 horas Binaria O(log2 n) 18 2 3.6 segundos
Problema de la búsqueda binaria: se necesita ordenar previamente el arreglo por carnet de identidad. Pronto veremos que existen algoritmos de ordenamiento muy eficientes con tiempos de ejecución O(n log n).
Conclusión
Cuando se comparan algoritmos para resolver un mismo problema, lo esencial es comparar la velocidad de crecimiento de sus tiempos de ejecución y no cuantas líneas tiene cada programa o cuan compleja resulta cada iteración. La velocidad de crecimiento del tiempo de ejecución se expresa por medio de la notación O(f(n)). Con esto, no se está diciendo que el tiempo es exactamente f(n), si no que a lo más crece a la velocidad de f(n).
Si dos algoritmos F y G toman tiempo O(f(n)) y O(g(n)) respectivamente. Se dice que F es mejor que G si:

límite de F(n)/G(n) -> 0 cuando n -> infinito
Por lo tanto la búsqueda binaria es mejor que la búsqueda secuencial porque log(n)/n tiende a 0. En la práctica esto se traduce en que no importa que un algoritmo F sea más lento que G para valores de n pequeños, lo que es realmente relevante para los usuarios es qué algoritmo se comporta mejor cuando deben procesar grandes volúmenes de datos.
Observación
El problema de determinar la velocidad de crecimiento del tiempo de ejecución de un algoritmo es uno de los problemas complejos de la computación. Por lo general es incluso más difícil que programar el algoritmo. En este curso, nos limitaremos a estimar esta velocidad para algoritmos simples (y no se preguntará durante los controles).

Búsqueda binaria recursiva Existe una variante de la búsqueda en un arreglo ordenado que puede ser implementada naturalmente usando recursividad. La función buscarBinRec busca un string x en un arreglo de string a, en un intervalo de índices [imin,imax]. Esta función también retorna el índice en donde se encuentra x. El algoritmo recursivo es:

Caso base:

Si imin>imax, el intervalo es vacío, por lo que x no se encuentra en el arreglo en ese intervalo y se retorna -1.
Si no, se calcula icentro=(imin+imax)/2 y se compara x con a[icentro]. Si son iguales, x se encuentra en a[icentro] por lo que se retorna icentro.

Caso recursivo:

Si x<a[icentro] se busca recursivamente en el intervalo [imin,icentro-1].
Si x>a[icentro] se busca recursivamente en el intervalo [icentro+1,imax].
La función queda:

int buscarBinRec(String x, String[] a, int imin, int imax) {
if (imin>imax)
return -1;
int icentro= (imin+imax)/2;
int comp= compare(x, a[icentro]);
if (comp==0)
return icentro;
if (comp<0)
return buscarBinRec(x, a, imin, icentro-1);
else
return buscarBinRec(x, a, icentro+1, imax);
}
Análisis: este algoritmo es idéntico al de la búsqueda binaria no recursiva por lo tanto los tiempos de ejecución son equivalentes, excepto por un factor constante. En efecto, la solución recursiva se obtiene reemplazando las iteraciones de la solución no recursiva por una llamada a una función. Las llamadas a funciones son ligeramente más caras que las iteraciones en un ciclo.
Por lo tanto, si la preocupación es la eficiencia en tiempo de ejecución, se debería preferir las soluciones no recursivas. Sin embargo, existen problemas que es muy difícil llevar a soluciones no recursivas (piense en las torres de Hanoi). Cuando la preocupación es la claridad de una solución, es frecuente que se opte más bien por la recursividad.

== Fuentes ==
[http://www.cs.wisc.edu/~arch/www Página de arquitectura de computadores]

[[Categoría:telemática]]

← Revisión anterior		Revisión del 15:17 16 jun 2011
Línea 1:		Línea 1:
		+	{{normalizar}}
	'''Diseño de Algoritmos Eficientes'''		'''Diseño de Algoritmos Eficientes'''

@@ Línea 1: / Línea 1: @@
 '''Diseño de Algoritmos Eficientes'''
-''El Diseño de Algoritnos Eficientes consiste en mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución.  Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].
+''El Diseño de Algoritnos Eficientes'' consiste en mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución.  Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].
 ==Búsqueda secuencial en arreglos.==

@@ Línea 1: / Línea 1: @@
 '''Diseño de Algoritmos Eficientes'''
-'''Objetivos:''' Mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución.  Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].
+''El Diseño de Algoritnos Eficientes consiste en mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución.  Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].
 ==Búsqueda secuencial en arreglos.==

← Revisión anterior		Revisión del 12:21 15 jun 2011
Línea 1:		Línea 1:
−	=Diseño de Algoritmos Eficientes=	+	'''Diseño de Algoritmos Eficientes'''
		+
	'''Objetivos:''' Mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución. Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].		'''Objetivos:''' Mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución. Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].

@@ Línea 1: / Línea 1: @@
-{{normalizar}}
+{{Definición
-'''Diseño de Algoritmos Eficientes'''
+|nombre= Algoritmos eficientes
-''El Diseño de Algoritnos Eficientes'' consiste en mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución.  Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].
+'''Algoritmos Eficientes.''' Consiste en mostrar cómo se comparan los algoritmos en términos de eficiencia en tiempo de ejecución.  Se toma como ejemplo la búsqueda en un arreglo, comparando la eficiencia de la búsqueda secuencial con la [[búsqueda binaria]].
-==Búsqueda secuencial en arreglos.==
+=== Búsqueda secuencial en arreglos ===
 Se tiene un archivo post.dat con los datos de los alumnos que dieron la PAA.  Cada línea de este archivo contiene el carnet de identidad (c.i.) y el nombre de un postulante.  Se tiene un segundo archivo mat.dat con los puntajes de los alumnos en la prueba específica de matemáticas.  Cada línea contiene el c.i. de un alumno seguido de su puntaje.  Por ejemplo, el contenido de ambos archivos podría ser:
@@ Línea 21: / Línea 26: @@
      ...
 Lectura de un archivo con delimitadores  Hasta el momento los archivos que hemos usado en el curso están estructurados de modo que cada campo de datos tiene un largo fijo.  Por lo tanto, es sencillo extraer el campo de la línea completa por medio de la función substring.  Sin embargo este mecanismo es demasiado frágil ya que es fácil equivocarse en la posición exacta de los datos en el archivo.
 Por esta razón, en la biblioteca del curso se incluyó un mecanismo más robusto para leer archivos con campos de datos.  La idea es que los archivos se deben estructurar de modo que los campos de datos estén separados por un delimitador (típicamente ":").  Este delimitador se especifica al crear el lecto o el escritor del archivo.  Al leer un archivo, la clase TextReader se encarga transparentemente de ubicar el delimitador y extraer el campo de datos.  Del mismo modo, al escribir en el archivo, la clase TextWriter agrega transparentemente el caracter delimitador para separar los campos.
 A modo de ejemplo, el siguiente código lee el archivo post.dat y deja el contenido en dos arreglos de nombres cis y nombres:
@@ Línea 103: / Línea 110: @@
+       }
+     }
-==Búsqueda binaria en arreglos.==
 '''Búsqueda binaria:'''  Si el arreglo cis está ordenado de menor a mayor (en orden lexicográfico), se puede escribir una función de búsqueda mucho más eficiente.
 Para buscar x en un arreglo a:
@@ Línea 131: / Línea 140: @@
 Observe que la función tiene más líneas que la búsqueda secuencial y que para realizar cada iteración hay que realizar más trabajo. La pregunta es entonces ¿Cuál es mejor?
 ===Análisis de la búsqueda secuencial===
-  El análisis de un algoritmo consiste en estimar el tiempo que toma ese algoritmo en función del tamaño de los datos que debe manipular. Normalmente se prefiere expresar estos tiempos en una unidad independiente de la velocidad del procesador.  Por ejemplo, para la búsqueda secuencial se puede usar como unidad el tiempo que toma ejecutar una iteración del ciclo.  En este caso, ese tiempo es un valor constante (aunque varía según la velocidad del procesador, pero no significativamente).
 Normalmente, el criterio que se usa para comparar algoritmos son los tiempos de ejecución para valores de n grandes, siendo n el tamaño de los datos.
 Notación O(f(n))
@@ Línea 139: / Línea 149: @@
 tiempo de ejecución para tamaño n <= c*f(n)
 Esto significa que el tiempo de ejecución crece a lo más al ritmo de f(n) salvo por un factor constante.
 Por lo tanto, la búsqueda secuencial toma, en el peor caso, tiempo O(n), es decir tiempo proporcional al número de elementos en el arreglo. En el caso promedio toma tiempo O(n/2) pero esto es lo mismo que O(n).
 Por lo tanto, si se necesita buscar un elemento, la búsqueda secuencial toma un tiempo razonable, pero no olvide que para resolver nuestro problema inicial se necesitan realizar 100000 búsquedas de este tipo, con n=150000.
 Análisis:
 Mejor caso: 1 iteración.
 Peor caso: log2 n iteraciones.
@@ Línea 149: / Línea 161: @@
 Para el caso en que n es 150000, una búsqueda binaria necesitará sólo 18 iteraciones del ciclo (en el peor caso).  Es decir 4000 veces menos iteraciones que en la búsqueda secuencial.  Pero cada iteración ahora es un poco más compleja.  Digamos 2 veces más compleja y por lo tanto toma el doble de tiempo.  Comparemos entonces los tiempos al realizar 100 mil búsquedas secuenciales y 100 mil búsquedas binarias:
- Tipo de  Iteraciones en  Iteraciones  Costo por  Tiempo  Búsqueda  función de n  cuando n=150000  iteración  Total   Secuencial  O(n)  75000 (promedio)  1  2 horas  Binaria     O(log2 n)  18  2  3.6 segundos
+Tipo de  Iteraciones en  Iteraciones  Costo por  Tiempo  Búsqueda  función de n  cuando n=150000  iteración  Total   Secuencial  O(n)  75000 (promedio)  1  2 horas  Binaria     O(log2 n)  18  2  3.6 segundos
 Problema de la búsqueda binaria: se necesita ordenar previamente el arreglo por carnet de identidad.  Pronto veremos que existen algoritmos de ordenamiento muy eficientes con tiempos de ejecución O(n log n).
 Conclusión
 Cuando se comparan algoritmos para resolver un mismo problema, lo esencial es comparar la velocidad de crecimiento de sus tiempos de ejecución y no cuantas líneas tiene cada programa o cuan compleja resulta cada iteración.  La velocidad de crecimiento del tiempo de ejecución se expresa por medio de la notación O(f(n)).  Con esto, no se está diciendo que el tiempo es exactamente f(n), si no que a lo más crece a la velocidad de f(n).
 Si dos algoritmos F y G toman tiempo O(f(n)) y O(g(n)) respectivamente. Se dice que F es mejor que G si:
   límite de F(n)/G(n) -> 0 cuando n -> infinito
 Por lo tanto la búsqueda binaria es mejor que la búsqueda secuencial porque log(n)/n tiende a 0.  En la práctica esto se traduce en que no importa que un algoritmo F sea más lento que G para valores de n pequeños, lo que es realmente relevante para los usuarios es qué algoritmo se comporta mejor cuando deben procesar grandes volúmenes de datos.
 Observación
 El problema de determinar la velocidad de crecimiento del tiempo de ejecución de un algoritmo es uno de los problemas complejos de la computación.  Por lo general es incluso más difícil que programar el algoritmo.  En este curso, nos limitaremos a estimar esta velocidad para algoritmos simples (y no se preguntará durante los controles).
-==Búsqueda binaria recursiva==
+===Búsqueda binaria recursiva===
-  Existe una variante de la búsqueda en un arreglo ordenado que puede ser implementada naturalmente usando recursividad.  La función buscarBinRec busca un string x en un arreglo de string a, en un intervalo de índices [imin,imax].  Esta función también retorna el índice en donde se encuentra x.  El algoritmo recursivo es:
 Caso base:
@@ Línea 187: / Línea 205: @@
+     }
 Análisis: este algoritmo es idéntico al de la búsqueda binaria no recursiva por lo tanto los tiempos de ejecución son equivalentes, excepto por un factor constante.  En efecto, la solución recursiva se obtiene reemplazando las iteraciones de la solución no recursiva por una llamada a una función.  Las llamadas a funciones son ligeramente más caras que las iteraciones en un ciclo.
 Por lo tanto, si la preocupación es la eficiencia en tiempo de ejecución, se debería preferir las soluciones no recursivas.  Sin embargo, existen problemas que es muy difícil llevar a soluciones no recursivas (piense en las torres de Hanoi).  Cuando la preocupación es la claridad de una solución, es frecuente que se opte más bien por la recursividad.
-== Fuentes ==
+=== Fuentes ===
-[http://www.google.com]
-[[Categoría:telemática]]
+[[Categoría:Telemática]]