Also verwende ich boolesche Matrizen, deren Dimension in der Regel ein paar Dutzend bis ein paar hundert ist, sie sind normalerweise ziemlich spärlich (nur ein paar 2-4 Nicht-Nullen in den meisten Zeilen und Spalten) und meine Laufzeit wird stark von dominiert ihre Multiplikation.
Welche Datenstruktur eignet sich am besten für die Beschleunigung der Multiplikation unter diesen Umständen?
Momentan speichere ich jede Matrix in einem zusammenhängenden Bitset (Array mit 64 Bit Länge) und vervielfältige sie im Grunde mit dem Standardalgorithmus. Ich beschleunige nur mit der schnellen Operation des Lokalisierens des nächsten gesetzten Bits in einem Wort und mit Vektorisierung durch Bitmask-Operationen.
Sollte ich vielleicht tatsächlich eine spärliche Darstellung verwenden?
Sie sollten in Erwägung ziehen, eine Quadtree-Repräsentation zu verwenden. Der Quadtree kann eine dünn besetzte Matrix ziemlich gut kodieren und eignet sich für eine ziemlich einfache (und Cache-effiziente) rekursive Multiplikationsimplementierung. Machen Sie den Basisfall zu einer 8x8-Matrix, so dass Sie die Multiplikation als (assembly-optimiertes?) 64-Bit-64-Bit-Operation implementieren können.
Ich halte es für sinnvoll, eine spärliche Darstellung zu verwenden. Selbst mit etwas so Einfachem wie einer Reihe von Indizes, die nicht Null sind, denke ich, dass Sie eine bessere Leistung erhalten werden.
Zum Beispiel erfordert eine Multiplikation für eine 100 × 100-Matrix mit 300 von Null verschiedenen Elementen unter Verwendung einer 2D-Array-Darstellung 100 × 100 × 100 = 1.000.000 "Operationen". Die Verwendung eines Indexsatzes erfordert nur 300 × 300 = 90.000 Operationen. (Natürlich sind diese Operationen nicht direkt vergleichbar.)
Eine Liste der 1er x's und y's. Zum Beispiel:
[0,2,0,12,0,60,1,2,1,39 ... usw.]
Was bedeutet, dass es eine 1 bei 0,2 a 1 bei 0,12 usw. gibt.
Der nette Teil ist, dass Sie nicht wirklich einen neuen Datentyp brauchen, und es ist ziemlich einfach zu analysieren.
Um zu multiplizieren, würden Sie alle übereinstimmenden / teilweise übereinstimmenden Indizes nachschlagen.
Tags und Links algorithm performance data-structures bit-manipulation matrix