Dynamisch wachsende dünn besiedelte Matrizen in Java

Rolf Jufer

13. Jan. 2025 • 7 min read

In meinem vorherigen Blog-Beitrag habe ich die statische Implementierung einer dünn besiedelten Matrix in Java vorgestellt. Diese Struktur eignet sich hervorragend für Anwendungen, bei denen die Grösse der Matrix vorab feststeht. Doch was passiert, wenn die Dimensionen einer Matrix zur Laufzeit variieren müssen? In diesem Beitrag zeige ich, wie eine dynamisch wachsende dünn besiedelte Matrix implementiert werden kann, indem wir die SOLID Prinzipien anwenden und Optimierungen wie die Verwendung eines Coordinates Objekts als Schlüssel vornehmen. Zudem erläutere ich praxisnahe Anwendungsbeispiele, die den Nutzen dieser optimierten Datenstruktur verdeutlichen.

Wozu dienen dynamisch wachsende dünn besiedelte Matrizen?

Während statische dünn besiedelte Matrizen für viele Anwendungen ausreichend sind, stossen sie an ihre Grenzen, wenn die Matrixgrösse flexibel angepasst werden muss. Eine dynamisch wachsende Matrix ermöglicht es, Zeilen und Spalten zur Laufzeit hinzuzufügen oder zu entfernen, ohne die gesamte Datenstruktur neu erstellen zu müssen. Dies ist besonders in Szenarien wichtig, in denen die Anzahl der Elemente nicht im Voraus bekannt ist oder sich kontinuierlich ändert, wie beispielsweise in dynamischen Netzwerken oder Echtzeitsimulationen.

Implementierung einer dynamische wachsenden dünn besiedelten Matrix in Java

IMutableMatrix -Interface
Dieses Interface definiert die grundlegenden Methoden für eine veränderliche Matrix, einschliesslich des Setzens und Abrufens von Werten sowie der Möglichkeit, Zeilen und Spalten hinzuzufügen oder zu entfernen.

/**
 * An interface for basic matrix operations that support dynamic 
 * size adjustment (adding and removing rows/columns).
 */
interface IMutableMatrix {

    // Sets a value in the matrix at the specified row and column.
    void set(int row, int col, double value);

    // Retrieves a value from the matrix at the specified row and column.
    double get(int row, int col);

    // Returns the current number of rows in the matrix.
    int getNumRows();

    // Returns the current number of columns in the matrix.
    int getNumCols();

    // Adds a new row to the matrix, increasing the row count by one.
    void addRow();

    // Adds a new column to the matrix, increasing the column count by one.
    void addColumn();

    // Removes the specified row from the matrix and shifts subsequent rows up.
    void removeRow(int row);

    // Removes the specified column from the matrix and shifts subsequent columns left.
    void removeColumn(int col);
}

Dieses Interface definiert die grundlegenden Methoden für eine veränderliche Matrix.

Coordinates Record
Dieser Record repräsentiert ein Koordinatenobjekt zur Kapselung der Zeilen- und Spaltenindizes.

/**
 * A record representing (row, col) coordinates for use as a key in a HashMap.
 */
 public record Coordinates(int row, int col) {
    public int getRow() {
        return row;
    }
    public int getCol() {
        return col;
    }
}

Seit Java 16 ist es möglich, in einem Record explizite Zugriffsmethoden zu definieren, beispielsweise getCol(), wenn man die gewohnte Getter-Syntax beibehalten möchte. Dabei werden die automatisch generierten row(), col() Methoden nicht überschrieben, sondern lediglich durch weitere Methoden ergänzt, die dieselben Werte zurückgeben.

SparseMatrix Klasse
Die SparseMatrix Klasse implementiert das IMutableMatrix Interface. Sie nutzt eine einzige HashMap<Coordinates, Double> für die Speicherung nicht-null Werte und ermöglicht das dynamische Hinzufügen und Entfernen von Zeilen und Spalten.

import java.util.HashMap;
import java.util.Map;

/**
 * A dynamic sparse matrix implementation using a single HashMap 
 * with (row, col) coordinates as keys.
 */
public class SparseMatrix implements IMutableMatrix {
    private int numRows;
    private int numCols;
    private Map<Coordinates, Double> matrix;

    // Constructor: Initializes the sparse matrix with specified rows and columns.
    public SparseMatrix(int numRows, int numCols) {
        if (numRows < 0 || numCols < 0) {
            throw new IllegalArgumentException("Number of rows and columns must be non-negative");
        }
        this.numRows = numRows;
        this.numCols = numCols;
        this.matrix = new HashMap<>();
    }

    // Sets a value in the matrix at the specified row and column.
    @Override
    public void set(int row, int col, double value) {
        validateIndices(row, col);

        Coordinates coord = new Coordinates(row, col);
        if (value != 0.0) {
            matrix.put(coord, value);
        } else {
            matrix.remove(coord);
        }
    }

    // Retrieves a value from the matrix at the specified row and column.
    @Override
    public double get(int row, int col) {
        validateIndices(row, col);

        Coordinates coord = new Coordinates(row, col);
        return matrix.getOrDefault(coord, 0.0);
    }

    // Returns the current number of rows in the matrix.
    @Override
    public int getNumRows() {
        return numRows;
    }

    // Returns the current number of columns in the matrix.
    @Override
    public int getNumCols() {
        return numCols;
    }

    // Adds a new row to the matrix, increasing the row count by one.
    @Override
    public void addRow() {
        numRows++;
    }

    // Adds a new column to the matrix, increasing the column count by one.
    @Override
    public void addColumn() {
        numCols++;
    }

    // Removes the specified row from the matrix and shifts subsequent rows up.
    @Override
    public void removeRow(int row) {
        if (row < 0 || row >= numRows) {
            throw new IndexOutOfBoundsException("Invalid row index: " + row);
        }

        // Remove all entries in the target row
        matrix.keySet().removeIf(coord -> coord.getRow() == row);

        // Shift rows above the removed row
        Map<Coordinates, Double> updatedMatrix = new HashMap<>();
        for (Map.Entry<Coordinates, Double> entry : matrix.entrySet()) {
            Coordinates coord = entry.getKey();
            if (coord.getRow() > row) {
                updatedMatrix.put(new Coordinates(coord.getRow() - 1, coord.getCol()), entry.getValue());
            } else {
                updatedMatrix.put(coord, entry.getValue());
            }
        }
        matrix = updatedMatrix;
        numRows--;
    }

    // Removes the specified column from the matrix and shifts subsequent columns left.
    @Override
    public void removeColumn(int col) {
        if (col < 0 || col >= numCols) {
            throw new IndexOutOfBoundsException("Invalid column index: " + col);
        }

        // Remove all entries in the target column
        matrix.keySet().removeIf(coord -> coord.getCol() == col);

        // Shift columns to the left for all entries to the right of the removed column
        Map<Coordinates, Double> updatedMatrix = new HashMap<>();
        for (Map.Entry<Coordinates, Double> entry : matrix.entrySet()) {
            Coordinates coord = entry.getKey();
            if (coord.getCol() > col) {
                updatedMatrix.put(new Coordinates(coord.getRow(), coord.getCol() - 1), entry.getValue());
            } else {
                updatedMatrix.put(coord, entry.getValue());
            }
        }
        matrix = updatedMatrix;
        numCols--;
    }

    // Validates the row and column indices to ensure they are within bounds.
    private void validateIndices(int row, int col) {
        if (row < 0 || row >= numRows) {
            throw new IndexOutOfBoundsException("Invalid row index: " + row);
        }
        if (col < 0 || col >= numCols) {
            throw new IndexOutOfBoundsException("Invalid column index: " + col);
        }
    }
}

Die SparseMatrix Klasse implementiert das IMutableMatrix Interface.

IMatrixDisplay Interface
Dieses Interface legt fest, wie eine beliebige Implementierung von MutableMatrix dargestellt werden kann. Damit wird das Single Responsibility Principle gestärkt, indem die Anzeigelogik getrennt von der Datenhaltung ist.

/**
 * An interface for displaying a matrix in various formats.
 */
interface IMatrixDisplay {

    // Displays the matrix with a specific strategy (e.g., grid lines, highlighting).
    void display(IMutableMatrix matrix);
}

Ein Interface zur Anzeige einer Matrix in verschiedenen Formaten.

MatrixDisplay Klasse
Die MatrixDisplay Klasse kümmert sich ausschließlich um die Darstellung der Matrix. Sie erzeugt Gitternetzlinien, kann Werte ausrichten und optional farblich hervorheben.

import java.util.HashMap;
import java.util.Map;

/**
 * A class that displays the matrix with grid lines and optional highlighting 
 * for non-zero values.
 */
class MatrixDisplay implements IMatrixDisplay {

    /**
     * Displays the matrix with grid lines and improved formatting.
     * Non-zero values are optionally highlighted in green (works in most terminals).
     *
     * @param matrix The matrix to display.
     */
    @Override
    public void display(IMutableMatrix matrix) {
        if (matrix.getNumRows() == 0 || matrix.getNumCols() == 0) {
            System.out.println("Empty Matrix.");
            return;
        }

        // Determine the maximum length of the numbers for cell formatting
        int maxNumberLength = 0;
        for (int row = 0; row < matrix.getNumRows(); row++) {
            for (int col = 0; col < matrix.getNumCols(); col++) {
                String valueStr = String.format("%.2f", matrix.get(row, col));
                if (valueStr.length() > maxNumberLength) {
                    maxNumberLength = valueStr.length();
                }
            }
        }

        // Set minimum cell width
        int cellWidth = Math.max(5, maxNumberLength + 2); // +2 for padding

        // Create the separator line
        StringBuilder separator = new StringBuilder();
        for (int col = 0; col < matrix.getNumCols(); col++) {
            separator.append("+");
            for (int i = 0; i < cellWidth; i++) {
                separator.append("-");
            }
        }
        separator.append("+");

        // ANSI color codes for highlighting (optional)
        final String ANSI_RESET = "\u001B[0m";
        final String ANSI_GREEN = "\u001B[32m";

        // Print the matrix with grid lines
        for (int row = 0; row < matrix.getNumRows(); row++) {
            // Print separator before each row
            System.out.println(separator.toString());

            // Build the row string
            StringBuilder rowBuilder = new StringBuilder();
            for (int col = 0; col < matrix.getNumCols(); col++) {
                rowBuilder.append("| ");
                double value = matrix.get(row, col);
                String formattedValue = String.format("%.2f", value);

                // Right-align the value within the cell
                if (value != 0.0) {
                    // Highlight non-zero values in green
                    rowBuilder.append(String.format(ANSI_GREEN + "%" + (cellWidth - 2) + "s " + ANSI_RESET, formattedValue));
                } else {
                    rowBuilder.append(String.format("%" + (cellWidth - 2) + "s ", formattedValue));
                }
            }
            rowBuilder.append("|");
            System.out.println(rowBuilder.toString());
        }

        // Print the final separator
        System.out.println(separator.toString());
    }
}

Eine Klasse, die die Matrix mit Gitterlinien und optionaler Hervorhebung anzeigt.

Praktisches Anwendungsbeispiel

Stellen Sie sich vor, Sie entwickeln ein dynamisches soziales Netzwerk, in dem ständig neue Benutzer hinzukommen und Verbindungen zwischen ihnen hergestellt oder gelöscht werden. Eine dynamisch wachsende dünn besiedelte Matrix ist hier ideal geeignet, um die Beziehungen (Freundschaften) effizient zu verwalten.

public class SocialNetworkDemo {
    public static void main(String[] args) {
        // Initialize the SparseMatrix with 3 users
        IMutableMatrix network = new SparseMatrix(3, 3);

        // User 0 is connected to user 1
        network.set(0, 1, 1.0);

        // User 1 is connected to user 2
        network.set(1, 2, 1.0);

        IMatrixDisplay display = new MatrixDisplay();
        System.out.println("Initial Social Network:");
        display.display(network);

        // Add a new user and a new connection
        network.addRow();
        network.addColumn();
        network.set(3, 0, 1.0); // User 3 is connected to user 0
        System.out.println("\nAfter adding a new user and connection:");
        display.display(network);

        // Remove a user and their connections
        network.removeRow(1);
        network.removeColumn(2);
        System.out.println("\nAfter removing a user and their connections:");
        display.display(network);
    }
}

Diese Klasse demonstriert die Verwendung von SparseMatrix und MatrixDisplay.

Output:

Initial Social Network:
+-------+-------+-------+
| 0.00  | 1.00  | 0.00  |
+-------+-------+-------+
| 0.00  | 0.00  | 1.00  |
+-------+-------+-------+
| 0.00  | 0.00  | 0.00  |
+-------+-------+-------+

After adding a new user and connection:
+-------+-------+-------+-------+
| 0.00  | 1.00  | 0.00  | 0.00  |
+-------+-------+-------+-------+
| 0.00  | 0.00  | 1.00  | 0.00  |
+-------+-------+-------+-------+
| 0.00  | 0.00  | 0.00  | 0.00  |
+-------+-------+-------+-------+
| 1.00  | 0.00  | 0.00  | 0.00  |
+-------+-------+-------+-------+

After removing a user and their connections:
+-------+-------+-------+
| 0.00  | 1.00  | 0.00  |
+-------+-------+-------+
| 1.00  | 0.00  | 0.00  |
+-------+-------+-------+
| 0.00  | 0.00  | 0.00  |
+-------+-------+-------+

Weitere Anwendungsbereiche von dynamisch wachsenden dünn besiedelten Matrizen

Graphenbasierte Anwendungen:
- Dynamische Netzwerke: Soziale Netzwerke und Verkehrsnetze, die ständig erweitert werden.
- Pfadsuche und Routing: Anpassung der Graphstruktur in Echtzeit.
Maschinelles Lernen und Datenanalyse:
- Online-Lernmodelle: Kontinuierliches Hinzufügen neuer Datenpunkte und Features.
- Empfehlungssysteme: Verwaltung ständig neuer Benutzer und Produkte.
Wissenschaftliche Simulationen:
- Echtzeitsimulationen: Anpassung an sich ändernde Systemparameter.
- Adaptive Finite-Elemente-Methoden: Flexible Netzstrukturen ohne vollständige Neuberechnung.
Informationsretrieval und Suchmaschinen:
- Dynamische Indizes: Aktualisierung von Term-Dokument-Matrizen mit neuen Inhalten.
- Latent Semantic Analysis (LSA): Kontinuierliche Anpassung semantischer Modelle.
Robotik und Computer Vision:
- Simultaneous Localization and Mapping (SLAM): Echtzeitkartierung und Positionsbestimmung.
- Merkmalsdetektion und -tracking: Flexible Verwaltung von Bildmerkmalen über Zeit.
Computational Finance:
- Portfolio-Optimierung: Verwaltung und Anpassung vielfältiger Finanzinstrumente.
- Risikomanagement: Echtzeit-Analyse sich ändernder Marktbedingungen.

Fazit

In diesem Blog-Beitrag habe ich gezeigt, wie eine dynamisch wachsende dünn besiedelte Matrix in Java implementiert werden kann, indem zunächst eine statische Version aus meinem vorherigen Beitrag um die Möglichkeit der dynamischen Anpassung von Zeilen und Spalten erweitert wurde. Durch die Verwendung eines Coordinates Objekts als Schlüssel wird die Datenhaltung effizienter und übersichtlicher. Gleichzeitig gewährleistet die Trennung von Datenverwaltung (SparseMatrix) und Darstellung (MatrixDisplay) eine klare Aufgabenteilung, ganz im Sinne der SOLID Prinzipien.

Ob in dynamischen Netzwerken, Echtzeitsimulationen oder datenintensiven Anwendungen – die dynamisch wachsende dünn besiedelte Matrix ist ein leistungsstarkes Werkzeug, das Speicherressourcen schont, Rechenleistung verbessert und sich flexibel an verändernde Anforderungen anpassen kann.

Schlussbetrachtung

Werden dünn besiedelte Matrizen über mehrere Server hinweg oder langfristig persistent benötigt, können Lösungen wie Redis oder eine (No)SQL-Datenbank sinnvoll sein. Redis bietet verteilte In-Memory-Strukturen mit optionaler Persistenz, während Datenbanken umfassende Abfrage- und Transaktionsfunktionen bereitstellen. Eine lokale HashMap punktet hingegen mit einfacher Handhabung, minimalem Overhead und extrem schnellen Zugriffen – vorausgesetzt, die Datenmenge passt in den verfügbaren RAM und es besteht keine Notwendigkeit für aufwendige Persistenz.
Die Wahl richtet sich somit stets nach Skalierungsbedarf, Persistenz-anforderungen und Komplexitätsgrad des Projekts.