Algoritmi lezione 6

utility.h
*********************************************************************************
string genera_stringa_casuale(int lunghezza) {
    static const string alfabeto =
        "0123456789"
        "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
        "abcdefghijklmnopqrstuvwxyz";

    string risultato="";

    for (int i = 0; i < lunghezza; ++i)
        risultato += alfabeto[ rand()% alfabeto.length() ];


    return risultato;
}

void carica_vettore_interi(int v[], int dimensione)
{
  for (int i=0; i<dimensione; i++)
    v[i] = rand(); //RAND_MAX
}

void carica_vettore_stringhe(string v[], int dimensione, int lunghezza=100)
{
  for (int i=0; i<dimensione; i++)
    v[i] = genera_stringa_casuale(lunghezza);
}

enum Stato {START, STOP};
auto Cronometro(Stato stato = Stato::START)
{
  static std::chrono::time_point<std::chrono::system_clock> inizio;
  static std::chrono::time_point<std::chrono::system_clock> fine;

  if (stato == Stato::START)
  {
    inizio = chrono::high_resolution_clock::now();
    fine = inizio;
  }
  else
    fine = chrono::high_resolution_clock::now();


  return chrono::duration_cast<std::chrono::milliseconds>(fine - inizio).count();
}

sorgente principale
**********************************************************************************
#include <iostream>
#include <chrono>
#include <ctime>

using namespace std;

#include "../utility_vettori.h"

string cerca_stringa_max(string v[], int dimensione)
{
  string stringa_max = v[0];
  for (int i=1; i<dimensione; i++)
    if (v[i]>stringa_max) stringa_max= v[i];

  return stringa_max;
}

int cerca_pos_stringa_max(string v[], int dimensione)
{
  int pos_stringa_max = 0;
  for (int i=1; i<dimensione; i++)
    if (v[i]>v[pos_stringa_max]) pos_stringa_max = i;

  return pos_stringa_max;
}

const int QUANTI_ELEMENTI = 30;
string v[QUANTI_ELEMENTI];

//complessità O(n)
int main()
{
  carica_vettore_stringhe(v, QUANTI_ELEMENTI - 1, 1000000);

  v[QUANTI_ELEMENTI-1] = string(1000000, 'z');

  //ordino dal più piccolo al più grande
  for (int i=0; i<QUANTI_ELEMENTI-1; i++)
    for (int j=i+1; j<QUANTI_ELEMENTI; j++)
      if (v[j]>v[i]) swap(v[i], v[j]);

  int numero_run = 1;
  int ripetizioni_per_run = 10000;


// RICERCA CON RESTITUZIONE DELL'ELEMENTO MASSIMO
  Cronometro(Stato::START);
  for(int conta_run =0; conta_run<numero_run; conta_run++)
    for (int conta=0; conta<ripetizioni_per_run; conta++)
      cerca_stringa_max(v, QUANTI_ELEMENTI);

  cout << "Tempo impiegato (ELEMENTO): " << Cronometro(Stato::STOP) << endl;



//RICERCA CON RESTITUZIONE DELLA POSIZIONE DELL'ELEMENTO MASSIMO
  Cronometro(Stato::START);
  for(int conta_run =0; conta_run<numero_run; conta_run++)
    for (int conta=0; conta<ripetizioni_per_run; conta++)
      cerca_pos_stringa_max(v, QUANTI_ELEMENTI);

  cout << "Tempo impiegato (POSIZIONE): " << Cronometro(Stato::STOP) << endl;;

  return 0;
}