MesuraCercaLineal

import java.util.*;

/** Classe MesuraCercaLineal: anàlisi empírica de l'algorisme de cerca lineal
  *
  * @author PRG ETSInf
  * @version Year 2011-2012
  */

class MesuraCercaLineal {

  // Constants que defineixen els parametres de mesura
  static final int MAXTALLA=1000000, INCRTALLA=100000, INITALLA=100000, REPETICIONS=10000;

  // Per omplir l'array
  static void omplirArray(int [] a) {
    for (int i=0;i<a.length;i++) a[i]=i;
  }

  public static void mesuraCercaLineal() {
    int [] a;             // Array pel problema
    int t, r, aux;        // Contadors de talla i repeticions, nombre aleatori auxiliar
    double tm1=0, tm2=0, tmt=0, tp1=0, tp2=0, tpt=0, tmed1=0, tmed2=0, tmedt=0;   // Temps

    // Imprimir capçalera de resultats
    System.out.printf("# Temps en milisegons\n# Talla    Millor   Pitjor    Promedi\n");
    System.out.printf("#------------------------------------\n");

    // Este bucle repeteix el process per diverses talles
    for (t=INITALLA; t<=MAXTALLA; t+=INCRTALLA) {

      // Crear i omplir l'array
      a=new int[t];
      omplirArray(a);

      // Cas millor: cercar a[0]
      // Com \'es massa r\`apid, les repeticions s'inclouen en la mesura del temps

      AlgorismesMesurables.cercaLineal(a,a[0]);  // Crida inicial per evitar sobrecarrega en la primera mesura
      tm1=System.nanoTime();        // Temps inicial
      for (r=0;r<REPETICIONS;r++)
        AlgorismesMesurables.cercaLineal(a,a[0]);
      tm2=System.nanoTime();        // Temps final
      tmt=((tm2-tm1)/REPETICIONS)/1e6;    // Temps promedi pel cas millor

      // Cas pitjor: cercar -1

      tpt=0;                        // Temps acumulat inicial a 0
      for (r=0;r<REPETICIONS;r++) {
        tp1=System.nanoTime();      // Temps inicial
        AlgorismesMesurables.cercaLineal(a,-1);
        tp2=System.nanoTime();      // Temps final
        tpt+=(tp2-tp1)/1e6;             // Actualitzar temps acumulat
      }
      tpt=tpt/REPETICIONS;          // Temps promedi pel cas pitjor

      // Cas promedi: cercar a nombre aleatori entre 0 i t-1

      tmedt=0;                        // Temps acumulat inicial a 0
      for (r=0;r<REPETICIONS;r++) {
        aux=(int) Math.floor(Math.random()*t);    // Nombre aleatori a cercar
        tmed1=System.nanoTime();      // Temps inicial
        AlgorismesMesurables.cercaLineal(a,aux);
        tmed2=System.nanoTime();      // Temps final
        tmedt+=(tmed2-tmed1)/1e6;         // Actualitzar temps acumulat
      }
      tmedt=tmedt/REPETICIONS;        // Temps promedi pel cas promedi

      // Imprimir resultats
      System.out.printf(Locale.US,"%8d   %10.7f   %10.7f   %10.7f\n",t,tmt,tpt,tmedt);

    }
  }

  public static void main(String args[]) {
    mesuraCercaLineal();
  }

}