Temas:
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
... ...
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
...
Por cada línea del archivo mat.dat:
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
}
¿Cuantas iteraciones toma el ciclo?
TextReader lect= new TextReader("mat.txt");
TextWriter escr= new TextWriter("post-mat.txt");
while (true) {
String lin= lect.readLine();
if (lect.eofReached())
break;
FieldParser decod= new FieldReader(lin, ":");
String carnet= decod.readString();
String ptje= decod.readString();
// Obtenemos la posicion de carnet en el arreglo cis
int k= buscarSeq(carnet, cis, length(cis));
if (k!=-1)
escr.println(carnet+":"+nombres[k]+":"+ptje);
else
println("no se encontro el carnet "+carnet);
}
lect.close();
escr.close();
Para buscar x en un arreglo a:
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
}
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?
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:
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:
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:
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).