Datenstruktur zum Arbeiten mit matrixbasierten Problemen

Question

Oft bin ich unsicher, welche Datenstruktur für matrixbasierte Algorithmen besser ist.

Mit "Matrix-based Algoritm" meine ich Algorithmen wie Needleman-Wunsh alignment. Es gibt viele Algorithmen, die visuell mit einer Matrix dargestellt werden.

ich was fragen, soll ich wählen:

• Array von Arrays
• Linked-Liste der verknüpften Listen
• Hash-Tabelle, wo Key ist ein Tupel wie (Zeile, Spalte)
• etc

Was muss ich bei dieser Sackgasse beachten?

Obs: Meine Frage ist "Sprache offen". Sie können jede Programmiersprache in Ihrer Antwort verwenden.

Answer 1

Welche Datenstruktur verwendet werden soll, hängt von Ihrem Algorithmus ab und davon, wie Sie auf diese Matrix zugreifen. Wenn zum Beispiel die Größe fest ist und ein schneller Zugriff erforderlich ist, ist es besser, ein zweidimensionales Array zu verwenden, denn egal, was Sie verwenden, Sie müssen diesen Speicherplatz trotzdem zuweisen. Wenn die Größe der Matrix dynamisch bestimmt wird, dann wahrscheinlich Vektor des Vektors (oder ähnliche Datenstruktur abhängig von der Sprache). Eine andere Frage ist, ob Ihre Matrix sehr dünn und extrem groß ist (wie in digitalen Geometriealgorithmen) und Sie sehr oft arithmetische Operationen an dieser Matrix durchführen müssen, dann könnten dreifache Datenstrukturen nützlich sein, zum Beispiel komprimierte Zeilenspeicher, die erstellt werden könnten Verwenden von 3 Vektoren. Sie können mehr in diesem Link lesen https://de.wikipedia.org/wiki/Compressed_Row_Storage Ich hoffe, es hilft