Punto informatico Network
Login Esegui login | Non sei registrato? Iscriviti ora (è gratuito!)
Username: Password:
  • Annuncio Pubblicitario

[C++] Chi mi sa ottimizzare questo Algoritmo?

Il forum per tutti i developer. Leggere attentamente il regolamento di sezione prima di postare.

[C++] Chi mi sa ottimizzare questo Algoritmo?

Messaggioda M@ttia » ven dic 22, 2006 2:19 pm

Come Serie di esercizi di "Algorithmen und Komplexität" qui al Poly, ho ricevuto il compito di dover implementare in C++ l'Algoritmo di Kruskal (che, dato un Grafico con i Lati "pesati" ne calcola l'albero d'espansione con Peso Complessivo minimale)
[Magari a molti suona Arabo, l'ho scritto casomai l'aveste gia' fatto cosi' sapete di cosa si tratta].

Io il mio Codice l'ho scritto (allegato qui sotto), abbiamo dei Grafici-Test di input dei quali si conosce la soluzione (cosi' da testare se il nostro algoritmo funziona) e il mio Algoritmo funziona alla perfezione [applauso+].

Un'ulteriore richiesta è pero' quella di scrivere l'algoritmo più performante possibile, ovvero che impieghi il minor tempo possibile di esecuzione.
Mi chiedevo se qualcuno di voi potesse analizzarmi il mio Codice qui sotto e magari trovare alcuni punti dove secondo voi il codice può essere migliorato/snellito al fine di impiegare il minor tempo possibile...
Se servissero delucidazioni o ulteriori spiegazioni scrivete pure... [:)]

Programma:

Il Grafico di input e' un file Grafico.dat, strutturato nel seguente modo:

Codice: Seleziona tutto
7                      <-- N° di Punti
12                     <-- N° di Lati
1 2 10                 <-- Lato nel formato:  "P.to Iniz." "P.to Fin" "Valore Lato"
1 3 5
1 4 8
2 4 1
2 5 4
3 4 6
3 6 7
4 5 2
4 6 3
4 0 9
5 0 11
6 0 12


Nella Shell il programma viene richiamato con:

Codice: Seleziona tutto
./Kruskal Grafico.dat


Ed infine il Codice-Sorgente del mio Programma-Algoritmo che vorrei nel limite del possibile ancora ottimizzare (questo è il mio meglio) è:

Codice: Seleziona tutto
/* @======================================================@
   ¦ Program:     Kruskal.C                               ¦
   ¦ ---------------------------------------------------- ¦
   ¦ Description: Implementation of the Kruskal-Algorithm ¦
   ¦              with a Find-Union Structure             ¦
   ¦ ---------------------------------------------------- ¦
   ¦ Author:      Mattia Bergomi - Gruppe A               ¦
   @======================================================@  */


#include <iostream>  // For Input-Output [cin / cout]
#include <fstream>   // For File-Reading [ifstream&]
#include <vector>    // For Array-Type   [vector<.>]

using namespace std;


// Structures (Classes):

class Edge
{
  public:

  int v1, v2;        // Vertices
  int w;             // Weight

  // Compare two Edges
  bool operator< (const Edge& b) const
  { return w < b.w;  }

  bool operator<= (const Edge& b) const
  { return w <= b.w; }
};

class Vertex
{
  public:

  Vertex* Next;         // Pointer in Tree to Next Vertex
  unsigned int Number;  // Number of the Vertex [0..n-1]

  Vertex()              // Default Constructor
  {
    Next = NULL;
    Number = 0;
  }

  unsigned int Find(vector<Vertex>& C)
  {
    Vertex Find = *this;

    while(Find.Next != NULL){ Find = *Find.Next; }
    unsigned int Root = Find.Number;


    // Path Compression

    Find = *this;
    while(Find.Next != NULL)
    {
      C[Find.Number].Next = &C[Root];
      Find = *Find.Next;
    }

    return Root;
  }
};



// Merge-Sort Implementation for using with all Type (for us: Edges)

template<class Typ>
void Merge(vector<Typ>& A, unsigned int i1, unsigned int f1, unsigned int f2)
{
  unsigned int i1_ = i1;

  // X is an Auxiliary Array of Lenght f2- i1 + 1
  vector<Typ> X(f2 - i1 + 1);

  unsigned int i  = 0;
  unsigned int i2 = f1 + 1;

  while (i1 <= f1 && i2 <= f2)
  {
    if (A[i1] <= A[i2])
    {
      X[i] = A[i1];
      ++i; ++i1;
    }
    else
    {
      X[i] = A[i2];
      ++i; ++i2;
    }
  }

  if (i1 <= f1)
  {
    // Copy A[i1; f1] to the End of X
    for (unsigned int j = i1; j <= f1; ++j, ++i) X[i] = A[j];
  }
  else
  {
    // Copy A[i1; f2] to the End of X
    for (unsigned int j = i2; j <= f2; ++j, ++i) X[i] = A[j];
  }

  // Copy X in A[i1; f2]
  for (unsigned int j = 0; j < X.size(); ++j, ++i1_) A[i1_] = X[j];
}

template<class Typ>
void MergeSort(vector<Typ>& A, unsigned int i, unsigned int f)
{
  if (i >= f) return;
  unsigned int m = (i + f)/2;
  MergeSort(A, i, m);
  MergeSort(A, m+1, f);
  Merge(A, i, m, f);
}


// Function for Input/Output:

vector<Edge> ReadData(ifstream& Input, unsigned int& m, unsigned int& n)
{
  Input >> n >> m;           // Read #(Edges) and #(Vertices)
  vector<Edge> Edges(m);

  for (unsigned int i=0; i<m; ++i)
  {
    Input >> Edges[i].v1 >> Edges[i].v2 >> Edges[i].w;
  }

  return Edges;
}


// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
// Kruskal-Function: (Edges of Input must already be Sorted!)
// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

unsigned int Kruskal(vector<Edge> Edges, unsigned int m, unsigned int n)
{
  unsigned int Weight = 0; // Weight of the Minimal "Spannbaum"

  vector<Vertex> C(n);     // Array with all Vertices
  for(unsigned int j=0; j<n; ++j){ C[j].Number = j; }
 
  for(unsigned int j=0; j<m; ++j)
  {
    unsigned int Root1 = C[Edges[j].v1].Find(C);
    unsigned int Root2 = C[Edges[j].v2].Find(C);

    if(Root1 != Root2)           // Different Trees => No Circles!
    {
      Weight += Edges[j].w;
      C[Root1].Next = &C[Root2]; // UNION of the Two Trees!
    }
  }

  return Weight;
}



int main (int argc, char *argv[]) // #(Arguments) & Array with Them
{
  unsigned int m;                 // Number of Edges    (First  Line of Input)
  unsigned int n;                 // Number of Vertices (Second Line of Input)

  vector<Edge> Edges;             // Array-Vector for all the Edges

  // Read Graph from File
  if (argc>1)
  {
    ifstream Input (argv[1]);     // argv[1] = FileName (ex: Graph0.dat)
    Edges = ReadData(Input, m, n);
  }
  else
  {
    cout << "Wrong Syntax! Usage is: " << argv[0] << " <input-file>\n";
    return -1;
  }

  MergeSort(Edges, 0, m-1);       // Sort Edges [Now: w(1) < ... <w(m)]

  // Compute with Kruskal and Print Output
  cout << "\nThe minimal \"Spannbaum\" has a Weight of: " << Kruskal(Edges, m, n) << "\n\n";

  return 0;
}
Ultima modifica di M@ttia il dom dic 31, 2006 4:05 pm, modificato 3 volte in totale.
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda Ices_Eyes » ven dic 22, 2006 8:33 pm

Bhè, di spazio di ottimizzazione mi pare non ce ne sia molto...
L'unica cosa che mi viene in mente potrebbe essere quella di sostituire il mergesort con un quick sort, di gran lunga più performante, ma non ho guardato molto il codice, forse non puoi per altr motivi... [:)]
Avatar utente
Ices_Eyes
Membro Ufficiale (Gold)
Membro Ufficiale (Gold)
 
Messaggi: 5543
Iscritto il: ven ott 24, 2003 10:37 am
Località: Prov. di Venezia

Messaggioda M@ttia » ven dic 22, 2006 9:39 pm

Eh ero indeciso fra i due e poi ho implementato con il Mergesort.

Comunque gli altri due Grafici di Test che abbiamo sono sull'ordine dei 100000 Punti e 350000 Lati, e il mergesort e basta per quelli durava sì e no 3 sec., mentre l'Intero algoritmo durava (sul mio PC) 1 min e 35 sec., che possono essere moltissimi come possono essere pochissimi per un grafico simile (non ho la minima idea di quanto ci metterebbe il "miglior" algoritmo), quindi ev. posso dare un'occhiatina anche all'Implementazione con Quicksort [^], anche se la botta migliorativa me la aspetterei dopo quei 2-3 sec. del Sorting [:)]

(comunque grazie che ti sei letto tutto il codice! [brindisi] [grazie]).


[P.S. domani sera me ne torno in Ticino per Natale dove non avrò il PC e tornerò il 1 gennaio, quindi se postaste risposte in questo periodo e non vi rispondo non me ne vogliate male, ma in Ticino non ho nessun PC attualmente [std]).
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero


Messaggioda M@ttia » dom dic 31, 2006 4:02 pm

Ok, ho corretto il codice sopra con l'ultima versione: con il Path-Compression (che mi ero dimenticato! [:-H]) è tutto ridotto a 3-4 sec. per il risultato! [applauso+]
Per vie traverse inoltre sono riuscito ad avere la soluzione "esatta" scritta dal capoassistente e, seppur molto simile, è strutturata con il new/delete che porta il tempo totale a 1.63 sec., ma non credo di aver voglia di riscrivere il tutto per il new/delete... Se a qualcuno interessasse lo potrei anche postare, ma per meno di 1.5 sec. di differenza dal migliore preferisco il mi oche mi sono scritto partendo da zero [^]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero

Messaggioda Lando » mar gen 02, 2007 10:32 am

M@ttia ha scritto:Per vie traverse inoltre sono riuscito ad avere la soluzione "esatta" scritta dal capoassistente

[:D] [:D] Cominci nel migliore dei modi l'anno nuovo!
Avatar utente
Lando
Bronze Member
Bronze Member
 
Messaggi: 576
Iscritto il: sab mar 25, 2006 10:40 am
Località: Switzerland

Messaggioda M@ttia » mar gen 02, 2007 11:11 am

[bleh] No beh a dire il vero l'ho cercata solo x confrontare i tempi di esecuzione e farmi un'idea di quanto dovesse metterci più o meno, il mio lo avevo già, e poi essendo strutturato in altro modo mi tengo il mio... [std]
</IE><FIREFOX>
Avatar utente
M@ttia
Moderatore
Moderatore
 
Messaggi: 8363
Iscritto il: lun giu 09, 2003 2:18 pm
Località: Ticino - Estero


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 4 ospiti

Powered by phpBB © 2002, 2005, 2007, 2008 phpBB Group
Traduzione Italiana phpBB.it

megalab.it: testata telematica quotidiana registrata al Tribunale di Cosenza n. 22/09 del 13.08.2009, editore Master New Media S.r.l.; © Copyright 2008 Master New Media S.r.l. a socio unico - P.I. 02947530784. GRUPPO EDIZIONI MASTER Spa Tutti i diritti sono riservati. Per la pubblicità: Master Advertising