Sind Monoide bei der Optimierung nützlich?

7

Viele übliche Operationen sind Monoide . Haskell hat diese Beobachtung genutzt, um viele Funktionen höherer Ordnung allgemeiner zu gestalten ( Foldableein Beispiel).

Es gibt eine offensichtliche Möglichkeit, mit Monoiden die Leistung zu verbessern: Die Programmierer behaupten die Assoziativität der Operation, sodass Operationen parallelisiert werden können.

Ich bin gespannt, ob es noch andere Möglichkeiten gibt, wie ein Compiler den Code optimieren kann, da er weiß, dass es sich um ein Monoid handelt.

optimization compilers category-theory Xodarap
quelle

Zufälligerweise hat der Autor der HLearn-Bibliothek jetzt eine Reihe von Beiträgen dazu.

Xodarap

7

Der Compiler kann die Exponentiation mit Monoiden optimieren. Lassen $\oplus$ ein binärer Operator sein, der in konstanter Zeit so berechnet werden kann, dass $\oplus$ und $a_1, a_2, ... \in A$ bilden ein Monoid. Dann die Operation

⨁_{[1.. n]} a_{k} = \underset{n times}{\underset{⏟}{a_{k} \oplus a_{k} \oplus \dots \oplus a_{k}}}

$\bigoplus_{[1..n]} a_k = \underbrace{a_k \oplus a_k \oplus \dots \oplus a_k}_{\text{$n$ times}}$

was normalerweise dauert $\cal O(n)$ Die Zeit kann nur mit dem Quadrat- und Multiplikationsalgorithmus ausgewertet werden $\cal O(\log n)$ Zeit, wenn der Compiler das weiß $\oplus$ gehorcht den monoiden Gesetzen.

FUZxxl
quelle

1

Schöne Beobachtung. Vielleicht sollten Sie angeben, dass Sie das annehmen

a_{k} \oplus a_{k}

$a_k \oplus a_k$ kann in berechnet werden

O (1)

$O(1)$ Zeit.

Zach Langley

0

Wenn Sie sich im Schritt der konstanten Faltung / konstanten Ausbreitung befinden, können Sie die Identität des Monoids immer dann ignorieren, wenn Sie andere nicht konstante Ausdrücke multiplizieren.

Roberto Mizzoni
quelle

Ich habe darüber nachgedacht - weißt du, ob es tatsächlich schneller ist?

Xodarap

Dies kann beispielsweise innerhalb einer Schleife einen Unterschied machen.

Roberto Mizzoni

Sind Monoide bei der Optimierung nützlich?

Antworten: