Als Lernerfahrung habe ich kürzlich versucht, Quicksort mit 3-Wege-Partitionierung in C # zu implementieren.
Abgesehen von der Notwendigkeit, vor dem rekursiven Aufruf eine zusätzliche Bereichsüberprüfung der Variablen links / rechts hinzuzufügen, scheint es recht gut zu funktionieren.
Ich wusste vorher, dass das Framework eine integrierte Quicksort-Implementierung in List & lt; & gt bereitstellt ; .Sort (über Array.Sort). Also habe ich ein paar grundlegende Profilerstellungen gemacht, um die Leistung zu vergleichen. Ergebnisse: Die integrierte List & lt; & gt; .Sort-Methode, die auf denselben Listen ausgeführt wird, ist etwa 10-mal schneller als meine eigene manuelle Implementierung.
Mit reflector habe ich festgestellt, dass die eigentliche Sortierung in List & lt; & gt; .Sort in externem Code implementiert ist, nicht in IL (in einer Funktion namens tryszsort ()).
Wenn ich meine eigene Quicksort-Implementierung anschaue, würde ich erwarten, dass das Ersetzen der rekursiven Aufrufe durch Iteration eine gewisse Verbesserung bringt. Auch das Deaktivieren der Überprüfung der Array-Grenzen (wenn möglich) könnte ebenfalls einige Vorteile bringen. Vielleicht würde das der eingebauten Implementierung etwas näher kommen, aber ich bin nicht zuversichtlich.
Also meine Frage: Ist es realistisch zu erwarten, dass die Leistung in einem optimierten Algorithmus (geschrieben in .NET IL, Jitted zu nativem Code) mit der Leistung eines extern implementierten Algorithmus konkurrieren kann?
Noch einmal, ich merke, Quicksort ist Teil des Frameworks, das war nur eine Lernerfahrung für mich. Allerdings gibt es auch viele Algorithmen (CRC32 kommt in den Sinn), die nicht zur Verfügung gestellt werden, aber immer noch von großem Wert für viele Anwendungen sein könnten. Hier ist eine verwandte Frage bezüglich der Implementierung von CRC32 in .NET und Leistungsprobleme.
Wenn Sie also einen solchen Algorithmus in .NET implementieren müssen, was sind die wichtigsten Leistungsaspekte, die Sie verstehen müssen, damit Ihr Algorithmus mindestens die Leistung von externem Code erreichen kann?
[Aktualisieren]
Ich habe die Ausführungsgeschwindigkeit auf etwa 10% des eingebauten Array.Sorts verbessert, indem ich den Algorithmus so geändert habe, dass er auf einem einfachen Array von Int anstelle von List operiert. In Reflector kann ich sehen, dass dies eine Callvirt () - Operation bei jedem Get oder in der Liste verhindert. Ich dachte, dies könnte Dinge verbessern, aber ich bin überrascht, wie viel.
Durch die Verwendung von nicht-rekursivem Code und insbesondere durch Verwendung von "unsicheren" Blöcken und Zeigerarithmetik (falls anwendbar) könnte tatsächlich einen x5 oder x10 Leistungsgewinn mit einem in C # geschriebenen Algorithmus sehen. Wie immer mit Leistung (und noch mehr, wenn Sie mit einer verwalteten Umgebung zu tun haben), wissen Sie nie genau, bis Sie es ausprobieren und es Benchmarking.
Im Allgemeinen sollten Sie hauptsächlich Dinge in C # schreiben, dann optimieren, noch mehr optimieren, und wenn es immer noch nicht gut genug ist, identifizieren Sie den genauen kritischen Teil des Codes und portieren ihn nach C ++ (dabei vorsichtig sein) Begrenzung der Anzahl der verwalteten / nativen Anrufgrenzen).
Stellen Sie sicher, dass Sie Äpfel und Äpfel miteinander vergleichen.
Beim Sortieren ist es möglich, dass die Compare-Funktion dominant ist und sich in den Implementierungen unterscheiden kann.
Wenn man annimmt, dass die Compare-Funktion in beiden Fällen schnell genug ist, um kein Problem zu sein, dann kann die Zeit von Dingen wie der Überprüfung von Array-Grenzen dominiert werden, was leicht einen großen Unterschied machen kann.
Durch die Verwendung von nicht-rekursivem Code und insbesondere durch Verwendung von "unsicheren" Blöcken und Zeigerarithmetik (falls anwendbar) könnte tatsächlich einen x5 oder x10 Leistungsgewinn mit einem in C # geschriebenen Algorithmus sehen. Wie immer mit Leistung (und noch mehr, wenn Sie mit einer verwalteten Umgebung zu tun haben), wissen Sie nie genau, bis Sie es ausprobieren und es Benchmarking.
Im Allgemeinen sollten Sie hauptsächlich Dinge in C # schreiben, dann optimieren, noch mehr optimieren, und wenn es immer noch nicht gut genug ist, identifizieren Sie den genauen kritischen Teil des Codes und portieren ihn nach C ++ (dabei vorsichtig sein) Begrenzung der Anzahl der verwalteten / nativen Anrufgrenzen).
Als Lernerfahrung habe ich kürzlich versucht, Quicksort mit 3-Wege-Partitionierung in C # zu implementieren.
Abgesehen von der Notwendigkeit, vor dem rekursiven Aufruf eine zusätzliche Bereichsüberprüfung der Variablen links / rechts hinzuzufügen, scheint es recht gut zu funktionieren.
Ich wusste vorher, dass das Framework eine integrierte Quicksort-Implementierung in List & lt; & gt bereitstellt ; .Sort (über Array.Sort). Also habe ich ein paar grundlegende Profilerstellungen gemacht, um die Leistung zu vergleichen. Ergebnisse: Die integrierte List & lt; & gt; .Sort-Methode, die auf denselben Listen ausgeführt wird, ist etwa 10-mal schneller als meine eigene manuelle Implementierung.
Mit reflector habe ich festgestellt, dass die eigentliche Sortierung in List & lt; & gt; .Sort in externem Code implementiert ist, nicht in IL (in einer Funktion namens tryszsort ()).
Wenn ich meine eigene Quicksort-Implementierung anschaue, würde ich erwarten, dass das Ersetzen der rekursiven Aufrufe durch Iteration eine gewisse Verbesserung bringt. Auch das Deaktivieren der Überprüfung der Array-Grenzen (wenn möglich) könnte ebenfalls einige Vorteile bringen. Vielleicht würde das der eingebauten Implementierung etwas näher kommen, aber ich bin nicht zuversichtlich.
Also meine Frage: Ist es realistisch zu erwarten, dass die Leistung in einem optimierten Algorithmus (geschrieben in .NET IL, Jitted zu nativem Code) mit der Leistung eines extern implementierten Algorithmus konkurrieren kann?
Noch einmal, ich merke, Quicksort ist Teil des Frameworks, das war nur eine Lernerfahrung für mich. Allerdings gibt es auch viele Algorithmen (CRC32 kommt in den Sinn), die nicht zur Verfügung gestellt werden, aber immer noch von großem Wert für viele Anwendungen sein könnten. Hier ist eine verwandte Frage bezüglich der Implementierung von CRC32 in .NET und Leistungsprobleme.
Wenn Sie also einen solchen Algorithmus in .NET implementieren müssen, was sind die wichtigsten Leistungsaspekte, die Sie verstehen müssen, damit Ihr Algorithmus mindestens die Leistung von externem Code erreichen kann?
[Aktualisieren]
Ich habe die Ausführungsgeschwindigkeit auf etwa 10% des eingebauten Array.Sorts verbessert, indem ich den Algorithmus so geändert habe, dass er auf einem einfachen Array von Int anstelle von List operiert. In Reflector kann ich sehen, dass dies eine Callvirt () - Operation bei jedem Get oder in der Liste verhindert. Ich dachte, dies könnte Dinge verbessern, aber ich bin überrascht, wie viel.
Stellen Sie sicher, dass Sie Äpfel und Äpfel miteinander vergleichen.
Beim Sortieren ist es möglich, dass die Compare-Funktion dominant ist und sich in den Implementierungen unterscheiden kann.
Wenn man annimmt, dass die Compare-Funktion in beiden Fällen schnell genug ist, um kein Problem zu sein, dann kann die Zeit von Dingen wie der Überprüfung von Array-Grenzen dominiert werden, was leicht einen großen Unterschied machen kann.
Tags und Links algorithm .net performance quicksort