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

[M@ttia]

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 .

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


[Ices_Eyes]

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...

[M@ttia]

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! ).


[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 ).

[M@ttia]

Ok, ho corretto il codice sopra con l'ultima versione: con il Path-Compression (che mi ero dimenticato! ) è tutto ridotto a 3-4 sec. per il risultato!
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

[Lando]

Per vie traverse inoltre sono riuscito ad avere la soluzione "esatta" scritta dal capoassistente

Cominci nel migliore dei modi l'anno nuovo!

[M@ttia]

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...