Ist es in C# nützlich, Demorans Theorem zu wenden, um boolesche Ausdrücke in bedingten Aussagen manuell zu optimieren (z. B. wenn Bedingungen)

Question

Am Tag, an dem ich den größten Teil meiner Arbeit in C und C ++ erledigte, würde ich mir natürlich manuell bewerben Demorgans Theorem Optimieren von nicht trivialen booleschen Ausdrücken.

Ist es nützlich, dies in C# zu tun, oder macht der Optimierer dies unnötig?

Answer 1

Bei den so schnellen Prozessoren ist es praktisch unmöglich, boolesche Ausdrücke neu zu ordnen, um einen tatsächlichen Geschwindigkeitsunterschied zu machen. Und der C# Compiler ist sehr schlau, er wird es auch optimieren. Optimieren Sie für Lesbarkeit und Klarheit!

Answer 2

Ihr erstes Ziel sollte es sein, solche Aussagen für das Verständnis des Entwicklers und die einfache Wartung zu optimieren.

Der Theorem von Demorgan kann ein nützliches Werkzeug dafür sein.

Answer 3

Die Optimierung in der JIT in seiner aktuellen Form optimiert dies nicht (nach dem, was ich gelesen habe) dies für Sie. Wenn Sie es optimieren müssen, müssten Sie dies trotzdem berücksichtigen.

Davon abgesehen ist dies eine ziemlich kleine Mikrooptimierung. Im Allgemeinen würde ich es vorziehen, Ihre "nicht trivialen booleschen Ausdrücke" in einer ausdrucksvolleren Form zu schreiben, damit sie leichter zu verstehen sind. Für mich ist dies wertvoller als jede sehr kleine Optimierung, die Sie durch die Anwendung des Demorgan -Theorems erhalten.

Answer 4

Ich glaube, dass die richtige Antwort auf diese Frage lautet, dass der Compiler die booleschen Bewertungen (normalerweise) nicht optimiert, einfach aufgrund des logischen Kurzschlusss, zum Beispiel:

if (GetFlagA() || GetFlagB())
{
   ...do something
}

Die Reihenfolge der Bewertung kann wirklich wichtig sein, wenn das Aufrufen von Getflaga etwas verändert, auf das GetFlagb angewiesen ist (zugegeben, dies ist wirklich schlechte Codepraxis, aber das ist ein anderes Thema für einen anderen Thread.) Das Problem hier ist logisch, wenn Getflaga ausgeführt wird und Getflaga ausführt und Rendits true, Getflagb wird niemals ausgeführt, wie hier das Ergebnis von getFlagb für die Bewertung der Aussage nicht beantwortet wird.

A | B | =

F | F | F

F | T | T

T | F | T wahr, unabhängig von Bs Rückkehr Val.

T | T | T wahr, unabhängig von Bs Rückkehr Val.

Zusammenfassend ist es so, dass Sie sich mit Demorgans oder irgendetwas so optimieren können, wie Sie den Rest von Informatik und Software -Engineering verwenden können. "Es hängt davon ab, ob." Wenn Sie eine nicht funktionsfähige Bewertung verwenden, kann dies wahrscheinlich optimiert werden. Ehrlich gesagt, Sie sprechen ein paar Operationen auf einer wahnsinnig schnellen Plattform.

Ich hoffe das hilft.

Answer 5

Das einzige Mal, dass Sie sich neu anordnen, Boolesche Algebra oder Demorgans, ist, wenn die Logik zu komplex ist, um dies anders zu tun. Wenn es nicht zu komplex ist, halten Sie es lesbar. Es gibt einen Fall zur Vereinfachung der Logik.

Manchmal, wenn die Logik schwierig ist, muss ich a erstellen Karnaugh -Karte Um die Logik auf etwas zu vereinfachen, das ich überhaupt aufschreiben kann. Oft kann die Verwendung von K-Maps Ihnen helfen, prägnantere Wege zu finden, um Ihre Logik auszudrücken. Das Ergebnis kann sinnvoll sein oder nicht, aber es wird gleichwertig sein.

Und ich würde auch sagen, dass Demorgan selbst wirklich keine Optimierung ist, die einen Unterschied macht. Wenn mehr als die Hälfte der Begriffe (nicht) negativ sind, werden Sie bestenfalls die Leistung des Entfernens einiger Nichts erhalten, was eine einzige ist Anweisung für eine CPU pro Nicht. Im schlimmsten Fall können Sie so viele Nots hinzufügen, wie Sie wegnehmen, und wenn Sie Demorgans nicht verwenden sollten, erhalten Sie mehr Nots als Sie überhaupt hatten.

Wenn Sie die Logik optimieren möchten, verwenden Sie eine Boolesche Algebra oder meinen persönlichen Favoriten K-Maps Um die Anzahl der Begriffe zu reduzieren (wenn möglich). Bewegen Sie nicht nur die Booleschen Betreiber, es ist albern.

Answer 6

Ich denke, der Compiler wird das schon tun. Sie können den Test durchführen und das kompilierte IL über Reflektor betrachten.

Optimieren Sie die Lesbarkeit und Wartbarkeit. Fragen Sie sich, ob Sie Ihre clevere Optimierung in einem Jahr verstehen. Wenn Sie denken, kann der Code einige Kommentare verwenden. Machen Sie den Code selbstdokumentieren.

Answer 7

Da die Bewertung der Booleschen Ausdrücke die Verknüpfungssemantik verwendet, können Sie Suberxpressionen verschieben, die billiger sind, um nach vorne zu berechnen:

if (CountAllFilesOnDrive('C:\') > 7 && useFileScan) { ... }

Wird den teuren Anruf jederzeit ausgeführt, wenn der Ausdruck bewertet wird, auch wenn er nicht benötigt wird. Das Umschalten dieser Anweisung überspringt die Datei, die überprüft wird, ob useFileScan ist falsch:

if (useFileScan && CountAllFilesOnDrive('C:\') > 7) { ... }

Demorgans könnte Ihnen helfen, "frühe Ausgänge" nach vorne zu bewegen und somit eine bessere durchschnittliche Leistung zu erzielen.

Beachten Sie, dass der Optimierer aufgrund der Garantie für die Bewertung von links nach rechts nicht viel Freiheit hat, den Ausdruck zu ändern.

Answer 8

Berücksichtigung der Lesbarkeit und Wartung. Wenn Sie eine ziemlich komplexe Reihe von booleschen Ausdrücken haben, die schwer zu lesen sind, ist Demorgans Theorm möglicherweise ein großartiger Ansatz, um den Ausdruck auf etwas zu reduzieren, das leichter zu lesen/aufrechterhalten wird, aber das ist immer noch gültig/überein mit dem ursprünglichen Express.

Wenn andererseits ein ausführlicherer Ausdruck viel einfacher zu lesen und den Ausdruck zu reduzieren ist, zwar logisch gleichlebig, es schwieriger zu verstehen, lassen Sie ihn so, wie es ist.

Answer 9

In fast allen praktischen Fällen, die ich mir vorstellen kann, hat die Anordnung der Booleschen Betreiber keinen merklichen Einfluss auf die Gesamtleistung. Wenn Ihr Programm auf die Datenbank, das Netzwerk usw. wartet, wird es dort mit weit mehr Zeit als in diesen winzigen Vorgängen verbringen. Sollten Sie ein Programm schreiben, in dem es wirklich einen Unterschied macht, überspringen Sie C# und verwenden Sie stattdessen C ++.

Answer 10

Demorgan von selbst kann bei Vorhandensein einer Kurzschlussbewertung völlig irrelevant sein.

return !(exp1 || exp2);
return !exp1 && !exp2;

werden zusammengestellt

if(   exp1 ) return !(true); else return !(exp2);
if(!(!exp1)) return   false; else return !(exp2);

mit dem notS Storniert und Konstanten gefaltet, diese sind identisch.

Der wichtigere Fall ist die Bewertung der Bewertung; Setzen Sie Cheeep -Dinge, die wahrscheinlich Kurzstrecken an der Vorderseite der Ausdrücke auslösen. Der Compiler kann dies nicht für Sie optimieren, da es schwierig ist, semantische Probleme wie Nebenwirkungen zu erkennen oder wenn spätere Ausdruck Annahmen auf der Grundlage früherer treffen:

return validState() && checkAssumuingValidState();

Answer 11

Ich stimme den allgemeinen Aussagen zu, dass Lesbarkeit und Wartbarkeit am wichtigsten sind, wenn es um die Optimierung von Booleschen Ausdrücken heutzutage geht. Daher ist Demorgans Theorem im Allgemeinen sehr nützlich.

Es gibt eine Ausnahme von dieser Regel. Wenn der boolesche Ausdruck den theoremoptimierten Ausdruck eines Demorgans ändert, ist es möglicherweise schwieriger, aufrechtzuerhalten. Betrachten Sie einen Ausdruck mit mehreren Eingaben, die optimiert wurden, um nur wenige boolesche Bedingungen zu zeigen. Eine Änderung der erforderlichen booleschen Logik könnte jemanden zwingen, alle möglichen booleschen Kombinationen erneut aufzulisten und dann wieder zu optimieren. Wäre der Ausdruck in einem nicht optimierten Format zurückgelassen worden, hätte eine Änderung weniger Schritte unternommen, um zu vervollständigen.

Mehr aus einer anekdotischen Perspektive, ich frage mich, ob die Aufklärung eines Teams über Demorgans Theorem- und Karnaugh -Karten usw. unnötige/ineffiziente boolesche Ausdrücke reduzieren würde. Wenn jemand diese Methoden ein gutes Verständnis hat, neigt er dazu, bessere Ausdrücke zu produzieren. Zum Beispiel bin ich kürzlich auf diesen booleschen Ausdruck im Code der Software gestoßen, die ich pflegte:

if ({boolean variable} != true && false)

Answer 12

Der C# Optimierer kann angesichts der Kurzschlussregeln für die logische Ausdrucksbewertung nicht zu viel tun. Die Anwendung des Demorgan -Gesetzes tut also nicht viel, es sei denn, Sie können andere nützliche Refaktorings sehen (und es kann natürlich dazu beitragen, Ihren Code klarer zu machen).

Es gibt jedoch Fälle, in denen Sie wesentliche Leistungsverbesserungen vornehmen können Sonstiges Arten der Expressionsoptimierung. Zum Beispiel sollten diese Bedingungen getauscht werden

if ( costly_boolean_function() && cheap_often_false_boolean_function() )

SQL-Abfrageoptimierer tun dies selbstverständlich, da SQL kein kurzfristiger Kreislauf hat. Ein Abfrageoptimierer wird die Konjunktive aggressiv neu ordnen, wenn Klausel Prädikate (der Form der Form c1 AND c2 AND ... cn) Um die kostengünstigsten Bedingungen zu erstellen, da sie bewerten können, um die teureren zu bewerten.

Answer 13

Zuerst mit Wartbarkeit umgehen, und hochrangige Optimierung.

Dann mit niedriger Optimierung umgehen.

Answer 14

Das Gesetz von De Morgan ist nützlich, um es auf eine normale Form zu reduzieren, z. B. disjunktive normale Form (DNF) oder konjunktive Normalform (CNF). Grundsätzlich bedeutet dies, dass es entweder ist

DNF: (a und b und c) oder (e und f und g) ...

oder

CNF: (a oder b oder c) und (e oder f oder g) ....

Sie können das nicht auf die niedrigste Ebene einwerfen.

Ich stimme den vorherigen Postern zu, die Sie für Lesbarkeit und Verständnis optimieren sollten.

Answer 15

Für alle uns Nicht-CS-Majors:

Wikipedia über de Morgans Gesetze:

Die Gesetze von De Morgan sind Regeln, die die logischen Operatoren in Verbindung bringen "und" und "oder" in Bezug auf einander durch Negation, nämlich:

Nicht (p oder q) = (nicht p) und (nicht q)
Nicht (p und q) = (nicht p) oder (nicht q)