Effiziente (Zeit- und Raumkomplexität) Datenstruktur für dichte und spärliche Matrix

Question

Ich muss eine Datei lesen, in der eine Matrix mit Autos gespeichert ist (1 = BlueCar, 2 = RedCar, 0 = Leer).

ich benötigen schreiben einen Algorithmus, um die Autos der Matrix auf diese Weise zu bewegen:

• blaue bewegen nach unten;
• rote bewegen nach rechts;
• gibt es eine Umdrehung, in der alle blauen sich bewegen und eine Umdrehung, um alle roten zu bewegen.

Bevor die Datei, die ich weiß nicht, die Größe Matrix gelesen wird, und wenn es dicht oder spärlich, so habe ich zwei Datenstrukturen (eine für dichte und eine für spärliche) und zwei Algorithmen implementieren.

Ich muss die beste Zeit und Raum Komplexität möglich erreichen.

Aufgrund der unbekannten Matrixgröße denke ich, die Daten auf dem Heap zu speichern.

Wenn die Matrix dicht, glaube ich, etwas zu verwenden wie:

short int** M = new short int*[m]; 
short int* M_data = new short int[m*n]; 

for(int i=0; i< m; ++i) 
{ 
    M[i] = M_data + i * n; 
} 

diese Struktur mit mir einen zusammenhängenden Raum von Speicher zuordnen kann, und es ist auch einfach mit M[i][j] zugegriffen werden.

Jetzt ist das Problem die Struktur für den spärlich Fall zu wählen, und ich habe auch überlegen, wie ich die Autos durch den Algorithmus auf einfachste Weise bewegen kann: zum Beispiel, wenn ich ein Auto zu bewerten, muß ich leicht finden, wenn in der nächsten Position (nach unten oder nach rechts) ein anderes Auto ist oder wenn es leer ist.

Zuerst dachte ich, um BlueCar und RedCar Objekte zu definieren, die vom allgemeinen Auto-Objekt erben. In diesen Objekten kann ich die Matrix Koordinaten speichern und sie dann in setzen:

std::vector<BluCar> sparseBlu; 
std::vector<RedCar> sparseRed; 

Ansonsten ich so etwas tun können:

vector< tuple< row, column, value >> sparseMatrix 

Aber das Problem zu finden, was in der nächste Position ist immer noch bleibt.

Wahrscheinlich ist dies nicht der beste Weg, dies zu tun. Wie kann ich den Sparse Case also effizient implementieren? (auch mit einer einzigartigen Struktur für spärliche)

Answer 1

Warum nicht einfach eine memory mapping direkt über die Datei erstellen? (Angenommen, Ihre Daten 0,1,2 sind in zusammenhängenden Bytes (oder Bits) in der Datei gespeichert, und die Position dieser Bytes stellt auch die Koordinaten der Autos dar)

Auf diese Weise müssen Sie nicht extra zuweisen Speicher und lesen Sie alle Daten ein, und die Daten können einfach und effizient mit M[i][j] zugegriffen werden.

Das Übergehen der Zeilen wäre L1-Cache-freundlich.

Bei sehr spärlichen Daten könnten Sie die Daten einmal durchsehen und eine Liste der leeren Bereiche/Blöcke im Speicher behalten (nur Startpos und Größe speichern), die Sie dann überspringen (und ggf. anpassen können)) in weiteren Läufen.

Bei der Speicherzuordnung werden nur häufig verwendete Seiten im Speicher gehalten. Das bedeutet, dass nach der Suche nach den leeren Bereichen nur noch Speicher für die nicht-leeren Bereiche zugewiesen werden, die häufig aufgerufen werden (dies wird automatisch vom Kernel erledigt - Sie müssen nicht selbst nachsehen).

Ein weiterer Vorteil besteht darin, dass Sie direkt auf den Betriebssystemdatenträgercache zugreifen. Es ist also nicht notwendig, Daten zwischen dem Kernel-Space und dem User-Space zu kopieren und zu verschieben.

Um Speicherplatz und Speicherverbrauch weiter zu optimieren, könnten die Autos in 2 Bits in der Datei gespeichert werden.

aktualisieren:

Ich werde Autos mit OpenMP und MPI bewegen muß ... Wird die Speicherzuordnung Arbeit auch mit gleichzeitigen Threads?

Sie sicherlich Multithreading nutzen könnten, aber nicht sicher, ob OpenMP die beste Lösung wäre hier, denn wenn man sich gleichzeitig auf verschiedene Teile der Daten arbeiten, können Sie einige überlappende Bereiche überprüfen müssen (dh ein Auto könnte von einem Block zum anderen bewegen).

Oder Sie könnten die Threads auf die mittleren Teile der Blöcke arbeiten lassen und dann andere Threads starten, um die Grenzen zu setzen (mit roten Autos, die ein Byte wären, mit blauen Autos eine ganze Reihe).

Sie benötigen auch einen Sperrmechanismus, um die Liste der dünn besetzten Regionen anzupassen. Ich denke, der beste Weg wäre, separate Threads zu starten (abhängig von der Größe der Daten natürlich).

Answer 2

In einer etwas ähnlichen Aufgabe habe ich einfach Compressed Row Storage verwendet.

Die komprimierte Zeile und Spalte (im nächsten Abschnitt) Speicherformate sind die allgemeinste: sie absolut keine Annahmen über die sparsity Struktur der Matrix zu machen, und sie speichern keine unnötigen Elemente. Andererseits sind sie nicht sehr effizient und benötigen einen indirekten Adressierungsschritt für jede einzelne skalare Operation in einem Matrix-Vektor-Produkt oder Vorkonditionierer-Lösung.

Sie müssen etwas genauer über die Anforderungen an Zeit- und Platzkomplexität sein. CSR erfordert einen zusätzlichen Indizierungsschritt für einfache Operationen, aber das ist ein kleiner Aufwand, wenn Sie nur einfache Matrixoperationen durchführen.

There's already an existing C++ implementation available online as well.