Algoritmi lezione 10

//raccolta funzioni aggiornata (a seguire il main)
//utility.h  (include brutale)
//versione 27-2-24
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 stampa_vettore_stringhe(string v[], int dimensione)
{
  for (int i=0; i<dimensione; i++)
    cout << v[i] << endl;
}


void stampa_vettore_interi(unsigned long v[], int dimensione)
{
  for (int i=0; i<dimensione; i++)
    cout << v[i] << endl;
}

void carica_vettore_interi(unsigned long v[], long dimensione)
{
   mt19937 twister{time(0)};

  for (long i=0; i<dimensione; i++)
    v[i] = twister();

}

bool verifica_ordine_crescente(unsigned long v[], long dimensione)
{
  for (int i=0; i<dimensione-1; i++)
    if (v[i]>v[i+1]) return false;

  return true;
}

void mischia_vettore_interi(unsigned long v[], long dimensione, int scambi)
{
  mt19937 twister{time(0)};

  for (long i=0; i<scambi; i++)
   swap( v[twister()%dimensione], v[twister()%dimensione] );
}

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

void ordina_vettore_stringhe(string v[], int QUANTI_ELEMENTI, bool A_Z=true)
{
 //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 (A_Z && v[j]<v[i])
          swap(v[i], v[j]);
      else
        if (!A_Z && v[j]>v[i])
          swap(v[i], v[j]);
}


void ordina_vettore_interi_senza_segno(unsigned long v[], int QUANTI_ELEMENTI, bool A_Z=true)
{
 //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 (A_Z && v[j]<v[i])
          swap(v[i], v[j]);
      else
        if (!A_Z && v[j]>v[i])
          swap(v[i], v[j]);
}

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();
}

//******************************************************************************


//MAIN VERSIONE STRINGHE (A SEGUIRE QUELLO PER GLI INTERI)
//main.cpp
//scansione lineare ma a passo due

#include <iostream>
#include <chrono>
#include <ctime>
#include <random>

using namespace std;
#include "../utility_vettori.h"



string cerca_stringa_min_max(string v[], int dimensione)
{
  string stringa_max = v[0];
  string stringa_min = v[0];

  for (int i=1; i<dimensione; i++)
    if (v[i]>stringa_max)
      stringa_max = v[i];
    else
      if (v[i]<stringa_min)
        stringa_min = v[i];

  return stringa_min + "/" + stringa_max;
}


string cerca_stringa_min_max_SMART(string v[], int dimensione)
{

  string stringa_max = "";
  string stringa_min = "";
  int inizia_da = -1;

  //ipotesi semplificatica: il numero di elementi è pari
//  if (dimensione%2 ==  0)  //numero pari di elementi
//  {
//    if (v[0]<v[1])
//    {
//      stringa_min = v[0];
//      stringa_max = v[1];
//    }
//    else
//    {
//      stringa_min = v[1];
//      stringa_max = v[0];
//    }
//    inizia_da = 2;
//  }
//  else  //numero dispari di elementi
//  {
//    stringa_max = v[0];
//    stringa_min = v[0];
//
//    inizia_da = 1;
//  }

  if (v[0]<v[1])
  {
    stringa_min = v[0];
    stringa_max = v[1];
  }
  else
  {
    stringa_min = v[1];
    stringa_max = v[0];
  }
  inizia_da = 2;

  for (int i=inizia_da; i<dimensione-1; i+=2)
    if (v[i]<v[i+1])
    {
      if (v[i] < stringa_min)
        stringa_min = v[i];

      if (v[i+1] > stringa_max)
        stringa_max = v[i+1];
    }
    else
    {
      if (v[i] > stringa_max)
        stringa_max = v[i];

      if (v[i+1] < stringa_min)
        stringa_min = v[i+1];
    }


  return stringa_min + "/" + stringa_max;
}

const int QUANTI_ELEMENTI = 500;
const int LUNGHEZZA = 10000;
string v[QUANTI_ELEMENTI];

int main()
{

  carica_vettore_stringhe(v, QUANTI_ELEMENTI, LUNGHEZZA);

  //sbilancio in favore di questo algoritmo
  for (int i=0; i<QUANTI_ELEMENTI; i++)
    v[i].replace(0, 5000, string(5000, 'M'));
//
//  v[rand()%QUANTI_ELEMENTI].replace(LUNGHEZZA - 100, 10, string(10, '0'));
//  v[rand()%QUANTI_ELEMENTI].replace(LUNGHEZZA - 100, 10, string(10, 'z'));
  ordina_vettore_stringhe(v, QUANTI_ELEMENTI, false); //false -> in ordine decrescente

  int numero_run = 1;
  int ripetizioni_per_run = 10000;

  string s="";
  Cronometro(Stato::START);

  for(int conta_run =0; conta_run<numero_run; conta_run++)
    for (int conta=0; conta<ripetizioni_per_run; conta++)
      s = cerca_stringa_min_max(v, QUANTI_ELEMENTI);

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


  Cronometro(Stato::START);

  for(int conta_run =0; conta_run<numero_run; conta_run++)
    for (int conta=0; conta<ripetizioni_per_run; conta++)
      s = cerca_stringa_min_max_SMART(v, QUANTI_ELEMENTI);

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


  return 0;
}
//*************************************************

//VERSIONE CON GLI INTERI
//main.cpp
//scansione lineare ma a passo due

#include <iostream>
#include <chrono>
#include <ctime>
#include <random>

using namespace std;
#include "../utility_vettori.h"

string cerca_int_min_max(unsigned long v[], long dimensione)
{
  unsigned long int_max = v[0];
  unsigned long int_min = v[0];

  for (long i=1; i<dimensione; i++)
    if (v[i]>int_max)
      int_max= v[i];
    else
      if (v[i]<int_min)
        int_min = v[i];

  return to_string(int_min) + "/" + to_string(int_max);
}

string cerca_int_min_max_SMART(unsigned long v[], long dimensione)
{

  unsigned long int_max;
  unsigned long int_min;
  long inizia_da = -1;


//  if (dimensione%2 ==  0)  //numero pari di elementi
//  {
//    if (v[0]<v[1])
//    {
//      int_min = v[0];
//      int_max = v[1];
//    }
//    else
//    {
//      int_min = v[1];
//      int_max = v[0];
//    }
//    inizia_da = 2;
//  }
//  else  //numero dispari di elementi
//  {
//    int_max = v[0];
//    int_min = v[0];
//
//    inizia_da = 1;
//  }


  if (v[0]<v[1])
  {
    int_min = v[0];
    int_max = v[1];
  }
  else
  {
    int_min = v[1];
    int_max = v[0];
  }
  inizia_da = 2;

  for (long i=inizia_da; i<dimensione-1; i+=2)
    if (v[i]<v[i+1])
    {
      if (v[i] < int_min)
        int_min = v[i];

      if (v[i+1] > int_max)
        int_max = v[i+1];
    }
    else
    {
      if (v[i] > int_max)
        int_max = v[i];

      if (v[i+1] < int_min)
        int_min = v[i+1];
    }


  return to_string(int_min) + "/" + to_string(int_max);
}

const long QUANTI_ELEMENTI = 50000;
unsigned long v[QUANTI_ELEMENTI];

int main()
{
  carica_vettore_interi(v, QUANTI_ELEMENTI);
  ordina_vettore_interi_senza_segno(v, QUANTI_ELEMENTI, false);

  long numero_run = 1;
  long ripetizioni_per_run = 10000;

  string s="";
  Cronometro(Stato::START);

  for(long conta_run =0; conta_run<numero_run; conta_run++)
    for (long conta=0; conta<ripetizioni_per_run; conta++)
      cerca_int_min_max(v, QUANTI_ELEMENTI);

  cout << "Tempo impiegato: " << Cronometro(Stato::STOP) << endl;
  //cout << "MIN/MAX: " << s << endl;


  Cronometro(Stato::START);

  for(long conta_run =0; conta_run<numero_run; conta_run++)
    for (long conta=0; conta<ripetizioni_per_run; conta++)
      cerca_int_min_max_SMART(v, QUANTI_ELEMENTI);

  cout << "Tempo impiegato (SMART): " << Cronometro(Stato::STOP) << endl;
  //cout << "MIN/MAX: " << s << endl;

  return 0;
}