Hausübung 1 – Speicherung dünn besetzter Matrizen

 

Es soll eine Klasse programmiert werden, mit der dünn besetzte Matrizen günstig gespeichert werden können.
Es sind außerdem Routinen zum Laden und Speichern und zum Addieren und Mischen von Elementen zu implementieren.

Hier der Programmtext:

Datenstruktur Element

public class Element
{
   // Klassenvariablen:
   private int iPosX, iPosY;  // Position in der Matrix
   private double dValue;     // Wert des Elements

   public Element (int iPosX, int iPosY, double dValue)
   { // Konstruktor: Element MUSS mit vollständigem Wertesatz
     // initialisiert werden
      this.iPosX = iPosX;
      this.iPosY = iPosY;
      this.dValue = dValue;
   } // end Konstruktor

   // get- und set- Funktionen
   public int getX()
   {
      return this.iPosX;
   }

   public int getY()
   {
      return this.iPosY;
   }

   public double getValue()
   {
      return this.dValue;
   }

   public void setValue(double dValue)
   {
      this.dValue = dValue;
   }
} // end class Element

Datenstruktur Matrix

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Locale;
import java.util.Scanner;
import java.util.Vector;

public class Matrix
{
   // Klassenvariablen:
   public static int stop = 0;
   private int iDim;                      // Dimension
   private Vector<Element> elmElemente;   // Vektor der Elemente

   // Konstruktoren:

   public Matrix()
   { // Standardkonstruktor
      elmElemente = new Vector<Element>();
   }

   public Matrix(int iDim)
   { // Konstruktor mit fester Dimension der Matrix
      elmElemente = new Vector<Element>();
      this.iDim = iDim;
   }

   public int getDim()
   {
      return this.iDim;
   }

   public void einlesen(String sDateiName)
   { // Matrix wird aus Datei mit übergebenem Dateinamen geladen
      try
      {
         Scanner scnEingabe = new Scanner(new File(sDateiName));
         this.iDim = scnEingabe.nextInt();
         scnEingabe.useLocale(Locale.ENGLISH);

         while (scnEingabe.hasNext())
            elmElemente.add(new Element(scnEingabe.nextInt(),
                  scnEingabe.nextInt(), scnEingabe.nextDouble() ));
      }
      catch (FileNotFoundException e)
      {
         System.out.println("Datei nicht gefunden!");
         e.printStackTrace();
      }
   } // end einlesen

   public void addiereElement(Element e)
   { // fügt neues Element e ein. Prüft zunächst, ob bei dem Index schon ein
     // Element vorhanden ist und addiert dieses gegebenenfalls
      boolean bDone = false;
      for (int i = 0; i < this.elmElemente.size(); ++ i)
         if (this.elmElemente.elementAt(i).getX() == e.getX())
            if (this.elmElemente.elementAt(i).getY() == e.getY())
            {
               this.elmElemente.elementAt(i).setValue(
                     this.elmElemente.elementAt(i).getValue()+e.getValue());
               bDone = true;
            }
      if (!bDone)
         this.elmElemente.add(e);
   } // end addiereElement

   public void addiereMatrix(Matrix B)
   { // addiert zur ursprünglichen Matrix die übergebene Matrix B,
     // indem alle Elemente von B einzeln addiert werden
      if (Matrix.gleicheDimension(this, B))
         for (int i = 0; i < B.elmElemente.size(); ++ i)
            this.addiereElement(B.elmElemente.elementAt(i));
   } // end addiereMatrix

   public static void mische(Element[] elmListe)
   { // Zufällige Neusortierung der Elemente
      for (int i = 0; i < elmListe.length; ++ i)
      {
         int iAlt = i;
         int iNeu = i+(int)(Math.random() * elmListe.length-i);
         Element temp = elmListe[iAlt];
         elmListe[iAlt] = elmListe[iNeu];
         elmListe[iNeu] = temp;
      }
   }

   public void sortiere()
   { // sortiert die Elemente der Matrix aufsteigend nach Zeile (Quicksort),

      // höhere Geschwindigkeit durch Nutzung eines statischen Arrays
      Element[] elmListe =
               elmElemente.toArray(new Element[elmElemente.size()]);

      // Optimierung: Liste wird vor der sortierung gemischt:
      mische(elmListe);

      // Aufruf der rekursiven Sortierfunktion mit Startwerten
      quickSort(elmListe, 0, elmListe.length-1, 1);

      // Sortieren der Zeilenblöcke
      int j = -1;
      for (int i = 1; i < this.iDim; ++ i)
      {
         System.out.println(" i "+i);
         int jAlt = j;
         while (elmListe[j+1].getX() == i)
         {
            ++ j;
            System.out.println("j  "+j);
         }
         if (j > jAlt+1)
         {
            System.out.println("[ "+(int)(jAlt+1)+" , "+j+" ]");
            quickSort(elmListe, jAlt+1, j, 2);
         }
      }

      // Array wird wieder in Vector umgewandelt
      elmElemente.clear();
      for (int i = 0; i < elmListe.length; ++ i)
         elmElemente.add(elmListe[i]);
   } // end sortiere

   public static void quickSort(Element[] elmListe, int iLinks, int iRechts,
         int iTyp)
   { // Rekursive Funktion sortiert Arrayelemente im übergebenen Intervall
      if (iLinks < iRechts)
      {
         int p = partition(elmListe, iLinks, iRechts, iTyp);
         quickSort(elmListe, iLinks, p-1, iTyp);
         quickSort(elmListe, p+1, iRechts, iTyp);
      }
   } // end quickSort

   public static int partition(Element[] elmListe, int iLinks, int iRechts,
         int iTyp)
   {
      int iPivot;
      int iTauschI = 0;

      if (iTyp == 1) // es wird nach Zeilen sortiert
      {
         int iWert1 = elmListe[iLinks].getX();
         int iWert2 = elmListe[iRechts].getX();
         int iWert3 = elmListe[(iLinks+iRechts) / 2].getX();

         // Pivot wird mit "Median-of-three" ermittelt
         if ((iWert1 >= iWert2 && iWert1 <= iWert3)
                  || (iWert1 <= iWert2 && iWert1 >= iWert3))
            iPivot = iLinks;
         else if ((iWert2 >= iWert1 && iWert2 <= iWert3)
                  || (iWert2 <= iWert1 && iWert2 >= iWert3))
            iPivot = iRechts;
         else
            iPivot = (iLinks+iRechts) / 2;

         int i = iLinks-1; // damit die erste Schleife ganz links anfängt
         int j = iRechts+1; // damit die zweite Schleife ganz rechts anfängt

         while (i < j)
         {
            while (elmListe[++ i].getX() <= elmListe[iPivot].getX())
               if (i == iRechts)
                  break;

            while (elmListe[iPivot].getX() <= elmListe[-- j].getX())
               if (j == iLinks)
                  break;

            if (i < j)
            { // zwei Elemente werden vertauscht
               Element temp = elmListe[i];
               elmListe[i] = elmListe[j];
               elmListe[j] = temp;
            } // end if
         } // end while

         // neue Position iTauschI für das Pivotelement wird ermittelt

         for (int a = iLinks; a <= iRechts; ++ a)
            if (elmListe[a].getX() > elmListe[iPivot].getX())
            {
               if (iPivot > a)
                  iTauschI = a;
               else if (iPivot < a)
                  iTauschI = a-1;
               break;
            } // end if
      } // end if
      else
      { // Elemente der Zeilen werden nach Spalten sortiert
         int iWert1 = elmListe[iLinks].getY();
         int iWert2 = elmListe[iRechts].getY();
         int iWert3 = elmListe[(iLinks+iRechts) / 2].getY();

         // Pivot wird mit "Median-of-three" ermittelt
         if ((iWert1 >= iWert2 && iWert1 <= iWert3)
                  || (iWert1 <= iWert2 && iWert1 >= iWert3))
            iPivot = iLinks;
         else if ((iWert2 >= iWert1 && iWert2 <= iWert3)
                  || (iWert2 <= iWert1 && iWert2 >= iWert3))
            iPivot = iRechts;
         else
            iPivot = (iLinks+iRechts) / 2;

         int i = iLinks-1; // damit die erste Schleife ganz links anfängt
         int j = iRechts+1; // damit die zweite Schleife ganz rechts anfängt

         while (i < j)
         {
            while (elmListe[++ i].getY() <= elmListe[iPivot].getY())
               if (i == iRechts)
                  break;

            while (elmListe[iPivot].getY() <= elmListe[-- j].getY())
               if (j == iLinks)
                  break;

            if (i < j)
            { // zwei Elemente werden vertauscht
               Element temp = elmListe[i];
               elmListe[i] = elmListe[j];
               elmListe[j] = temp;
            } // end if
         } // end while

         // neue Position iTauschI für das Pivotelement wird ermittelt
         for (int a = iLinks; a <= iRechts; ++ a)
            if (elmListe[a].getY() > elmListe[iPivot].getY())
            {
               if (iPivot > a)
                  iTauschI = a;
               else if (iPivot < a)
                  iTauschI = a-1;
               break;
            } // end if
      }
      if (iTauschI == 0)
         iTauschI = iRechts;

      Element temp = elmListe[iPivot];
      elmListe[iPivot] = elmListe[iTauschI];
      elmListe[iTauschI] = temp; 

      return iTauschI;
   } // end partition

   public void speichere(String sDateiName, boolean bSortiert)
   { // speichert die Matrix unter übergebenem Dateinamen
      try
      {
         PrintStream pstAusgabe = new PrintStream(new File(sDateiName));
         pstAusgabe.println(this.getDim());

         if (bSortiert)
         { // wenn gewünscht, wird die Matrix zuerst sortiert
            pstAusgabe.println(this.anzahlDerElemente());
            this.sortiere();
         }

         for (int i = 0; i < this.elmElemente.size(); ++ i)
            pstAusgabe.println(this.elmElemente.elementAt(i).getX()+" "
                 +this.elmElemente.elementAt(i).getY()+" "
                 +this.elmElemente.elementAt(i).getValue());
      } // end try
      catch (FileNotFoundException e)
      {
         System.out.println("Datei konnte nicht geschrieben werden!");
         e.printStackTrace();
      }
   } // end speichere

   public double summeDerElemente()
   { // berechnet die Summe aller Matrixelemente
      double dSumme = 0;
      for (int i = 0; i < this.elmElemente.size(); ++ i)
         dSumme += this.elmElemente.elementAt(i).getValue();
      return dSumme;
   } // end summeDerElemente

   public int anzahlDerElemente()
   { // ermittelt die Anzahl der Matrixelemente
      return this.elmElemente.size();
   } // end anzahlElemente

   public static boolean gleicheDimension(Matrix A, Matrix B)
   { // prüft zwei quadratische Matrizen auf Dimensionsgleichheit
      return (A.getDim() == B.getDim());
   } // end gleicheDimension

   public static Matrix zufallsMatrix(int iDim, int iElemente, double dMax)
   { // erstelle eine zufällige Matrix mit übergebenen Spezifikationen
      Matrix mZufall = new Matrix(iDim);
      for (int i = 0; i < iElemente; ++ i)
      {
         while (true)
         {
            int iX = (int)(Math.random() * (iDim-1))+1;
            int iY = (int)(Math.random() * (iDim-1))+1;

            // es wird geprüft, ob der zufällige Index schon vorhanden ist:
            boolean bDone = true;
            for (int j = 0; j < mZufall.elmElemente.size(); ++ j)
               if (mZufall.elmElemente.elementAt(j).getX() == iX)
                  if (mZufall.elmElemente.elementAt(j).getY() == iY)
                     bDone = false;

            if (bDone)
            { // Wenn der Index noch nicht benutzt wurde:
               double dV = Math.random() * dMax;
               mZufall.elmElemente.add(new Element(iX, iY, dV));
               break;
            } // end if
         } // end while
      } // end for
      return mZufall;
   } // end zufallsMatrix
} // end class Matrix

Testprogramm

public class MatrixTest
{
   public static void main(String args[])
   {
      long lStartMS = System.nanoTime();

      Matrix A = new Matrix();
      A.einlesen("A.txt");

      System.out.println("Matrix 1: Summe der "+A.anzahlDerElemente()
           +" Elemente: "+A.summeDerElemente());

      Matrix B = new Matrix();
      B.einlesen("B.txt");
      System.out.println("Matrix 2: Summe der "+B.anzahlDerElemente()
           +" Elemente: "+B.summeDerElemente());

      A.addiereMatrix(B);
      System.out.println("Matrix 1+2: Summe der "+A.anzahlDerElemente()
        +" Elemente des Ergebnisses: "
           +A.summeDerElemente());

      A.speichere("AplusB.txt", true);

      long lEndMS = System.nanoTime();
      long lMS = lEndMS-lStartMS;
      System.out.println("  -> Rechenzeit: "+lMS);
   }
}