Was ist der schnellste Weg, um spärliche boolesche Matrizen darzustellen und zu multiplizieren?

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 2-4 Nicht-Nullen in den meisten Zeilen und Spalten) und meine Laufzeit wird stark von deren dominiert Multiplikation.Was ist der schnellste Weg, um spärliche boolesche Matrizen darzustellen und zu multiplizieren?

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 von 64-Bit-Longs) zeilenweise und multipliziere sie mit im Grunde dem Standardalgorithmus, beschleunigte nur mit dem schnellen Vorgang der Lokalisierung des nächsten Satzes Bit in einem Wort und mit Vektorisierung durch Bitmask-Operationen.

Sollte ich vielleicht tatsächlich eine spärliche Darstellung verwenden?

Quelle

2010-09-05 jkff

Was meinst du mit "Dimension ist in der Regel ein paar Dutzend bis ein paar hundert"? Das klingt mehr wie eine Anzahl von Elementen (oder die Länge einer Dimension) als die Dimension (d. H. Die Anzahl der Koordinaten, die Sie angeben müssen, um ein Element auszuwählen). –

Ich denke, es ist sinnvoll, eine spärliche Darstellung zu verwenden. Selbst mit etwas so Einfachem wie einem Satz von Indizes, die nicht Null sind, denke ich, dass Sie eine bessere Leistung erhalten werden.

Für eine 100 × 100-Matrix mit 300 Elementen ungleich Null, die 2D-Array-Darstellung verwenden, erfordert die Multiplikation beispielsweise 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.)

Quelle

2010-09-05 16:02:01 svick

Ja, das ist der Punkt: Diese Operationen sind wirklich nicht direkt vergleichbar, weil es überhaupt nicht offensichtlich ist, dass 90000 Operationen an Indexsätzen schneller als 1000000 vektorisierte Operationen an 64-Bit Masken sind. Ich denke, ich muss es einfach implementieren und sehen. – jkff

Eine Liste der 1er x's und y's. Zum Beispiel:

[0,2,0,12,0,60,1,2,1,39 ... etc]

Was bedeutet, dass es bei 0,2 a 1 bei 0 a 1 ist , 12, etc.

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.

Quelle

2010-09-05 17:06:55 TaslemGuy

Ich denke, dass das Erstellen neuer Datentypen viel sauberer und einfacher zu arbeiten ist. – svick

Das ist der Punkt: Ich bin nicht sicher, dass es schneller sein wird, wenn man bedenkt, dass die aktuelle Implementierung sehr effizient ist, da sie durch Vektoroperationen auf 64-Bit-Bitmasken funktioniert. Sieht so aus, als müsste ich es einfach implementieren. – jkff

Sie könnten die Verwendung einer Quadtree-Darstellung in Betracht ziehen. 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 (montageoptimierte?) 64-Bit-64-Bit-Operation implementieren können.

Quelle

2010-09-05 23:47:09

Was ist der schnellste Weg, um spärliche boolesche Matrizen darzustellen und zu multiplizieren?

Antwort

Verwandte Themen