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:

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:

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?

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:

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:

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:

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.