Performance-Problem: Java vs C++

Habe ich immer gehört, dass C++ war viel effizienter als Java ist (und das ist der Grund, warum die meisten Spiele sind in C++ entwickelt).

Schrieb ich einen kleinen Algorithmus zur Lösung des "Acht Königinnen-Rätsel" in Java und C++, mit der exakt gleichen Algorithmus, und begann dann, Sie zu erhöhen, die Anzahl oder Quadrate.
Bei erreichen checkboards von 20*20 oder sogar 22*22, es wird angezeigt, Java ist viel effektiver (3 Sekunden vs 66 Sekunden für C++).

Ich habe keine Ahnung, warum, aber ich bin mir ziemlich Anfang mit C++, so dass es möglich ist, dass ich einige riesige performance-Fehler, so will ich gerne akzeptieren, alle Informationen, die mir helfen würden zu verstehen, was geschieht.

Unten ist der code, den ich verwenden in Java:

import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

public class HuitDames {

    /**
     * La liste des coordnnées des dames.
     */
    private static List<Point> positions = new ArrayList<>();

    /**
     * Largeur de la grille.
     */
    private static final int LARGEUR_GRILLE = 22;


    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int i = 1;
        placerDame(i);
        for (Point point : positions) {
            System.out.println("(" + point.x + "; " + point.y + ")");
        }
    }

    /**
     * Place une dame et return true si la position est bonne.
     * @param i le numéro de la dame.
     * @return si la position est bonne.
     */
    private static boolean placerDame(int i) {

        boolean bonnePosition = false;
        for (int j = 1; j <= LARGEUR_GRILLE && bonnePosition == false; j++) {
            Point emplacement = new Point(i, j);
            positions.add(emplacement);
            if (verifierPrise(emplacement) && (i == LARGEUR_GRILLE || placerDame(i + 1))) {
                bonnePosition = true;
            }
            else {
                positions.remove(i - 1);
            }
        }

        return bonnePosition;
    }

    /**
     * Vérifie que la nouvelle position n'est pas en prise avec une position déjà présente.
     * @param position la position de la nouvelle dame.
     * @return Si la position convient par rapport aux positions des autres dames.
     */
    private static boolean verifierPrise(Point position) {
        boolean nonPrise = true;
        for (Point point : positions) {
            if (!point.equals(position)) {
                //Cas où sur la même colonne.
                if (position.y == point.y) {
                    nonPrise = false;
                }
                //Cas où sur même diagonale.
                if (Math.abs(position.y - point.y) == Math.abs(position.x - point.x)) {
                    nonPrise = false;
                }
            }
        }

        return nonPrise;
    }
}

Und unten ist der code, der in C++:

#include <iostream>
#include <list>
#include <math.h>
#include <stdlib.h>

using namespace std;


//Class to represent points.
class Point {

    private:
        double xval, yval;

    public:
        //Constructor uses default arguments to allow calling with zero, one,
        //or two values.
        Point(double x = 0.0, double y = 0.0) {
                xval = x;
                yval = y;
        }

        //Extractors.
        double x() { return xval; }
        double y() { return yval; }
};

#define LARGEUR_GRILLE 22
list<Point> positions;


bool verifierNonPrise(Point emplacement) {
    bool nonPrise = true;
    for (list<Point>::iterator it = positions.begin(); it!= positions.end(); it++) {
        if (it->x() != emplacement.x()) {
            if (it->y() == emplacement.y()) {
                nonPrise = false;
            }
            if (abs(it->y() - emplacement.y()) == abs(it->x() - emplacement.x())) {
                nonPrise = false;
            }
        }
    }

    return nonPrise;
}

bool placerDame(int i) {
    bool bonnePosition = false;
    for (int j = 1; j <= LARGEUR_GRILLE && !bonnePosition; j++) {
        Point emplacement(i,j);
        positions.push_back(emplacement);
        if (verifierNonPrise(emplacement) && (i == LARGEUR_GRILLE || placerDame(i + 1))) {
            bonnePosition = true;
        }
        else {
            positions.pop_back();
        }
    }

    return bonnePosition;
}

int main()
{
    int i = 1;
    placerDame(i);
    for (list<Point>::iterator it = positions.begin(); it!= positions.end(); it++) {
        cout << "(" << it->x() << "; " << it->y() << ")" << endl;
    }
    return 0;
}
  • Hast du das kompilieren von C++-Code mit Optimierung aktiviert? Für gcc und clang hinzufügen -O3 auf der Kommandozeile.
  • verwenden Sie einen Vektor und nicht einer Liste...das Durchlaufen einer Liste in jeder Sprache ist schrecklich.
  • Erstens, nutzen std::vector<Point> statt std::list<Point>. Versuchen Sie dann, die übergabe per Referenz statt als Wert. Zum Beispiel bool verifierNonPrise(const Point& emplacement). Als Nächstes erstellen Sie nicht benannt Provisorien, sondern tun positions.emplace_back(i, j);. Es ist wahrscheinlich, es gibt viele andere Dinge, die Sie verbessern können.
  • "Ich habe immer gehört, dass C++ war viel effizienter als Java"-weil es allgemein ist.
  • Es ist überhaupt nicht ungewöhnlich für Java zu schlagen C++. Ein JITC-optimierte Java-Programm kann mehr dicht optimiert, als möglich unter Verwendung leicht Verfügbarer C++ - compiler/linker. ZB, ein JITC kann einfach inline-Operationen auf einen Punkt, während C++ können in der Regel nur tun, wenn die Funktionen deklariert sind, inlineable.
  • Als die Sprache näher an Maschinensprache (die tiefer liegenden Ebene eine Sprache ist), Sie haben mehr Knöpfe zur Steuerung Zeug und dies können Sie entweder machen oder brechen Sie Ihre code-je nachdem, wie Sie verwenden Sie diese regler. Wenn Sie nach oben schauen alle den Vergleich von Fällen, hier findest du viele Beispiele, wie schnelle C++ - code einen code, der ursprünglich langsam sehr schnell. Die meisten der Zeit, die Sie nicht tun können, die in höheren Sprachen. Dies bedeutet nicht, dass alle C++ - codes gehen, um schneller als JAVA, PYTHON ... es bedeutet nur, Sie machen den code schneller.
  • Nur ein kleiner Punkt, der wahrscheinlich nicht auf die Leistung sehr viel. Wenn alle Ihre point-Klasse hat halt x und y, und es gibt keine Invarianten aufrecht zu erhalten, könnte man genauso gut entfernen Sie die member-Funktionen und die Daten der Mitglieder der öffentlichkeit.
  • Beachten Sie, dass die Deklaration der Funktionen inlinable hat wirklich keine bearance, ob Sie inline. In diesem Beispiel Point's Methoden sind implizit inline. Aber Sie sind auch nicht notwendig. Die Daten sollten öffentlich sein.
  • In Java jede (nicht-native) Funktion inlined, wenn der JITC entscheidet, es lohnt sich. In C++, wenn eine Funktion in einer anderen compilation unit, es kann nur eingebettet, wenn der linker ist sehr, sehr smart, oder wenn der compiler effektiv kompiliert alles.
  • Und eine Folge ist, dass in der JITC-optimierte Java getter-und setter-Funktionen sind "frei" -- null-Kosten vs Zugriff auf die Variablen direkt.
  • Diesen Reglern werden in der JVM für Java, nicht für den compiler. Die Hotspot-Optionen kann einen sehr großen Unterschied.
  • Sicher, aber OP ' s code, alles inline. Der performance-hit ist wahrscheinlich die Verwendung von std::list. Für die Getter würden diese optimiert werden, auch wenn inlined, aber mit Ihnen könnte resultieren in zusätzlichen Kopien der Daten der Mitglieder aus, weil Sie semantisch Werte zurückgeben. Jedenfalls ist es schwer zu sehen, wie Java konnte-ausführen von C++ in solchen einfachen numerischen problem, wenn richtig codiert, die in beiden Sprachen. Ich würde nicht erwarten, dass C++ zu Massiv aus-ausführen Java entweder.
  • Ich habe nicht bedeuten, andere Sprachen haben nicht diese Kontrollen, ich meinte, wie Sie näher an der Maschine Sprache, die Sie haben, mehr von diesen kontrolliert. Aber Sie haben absolut Recht.
  • Und solche smart-linkers vorhanden. Jeder gute compiler wird heute Optionen für inter-Modul-Optimierung. Die großen Unterschiede kommen von anderen Dingen: für einige Arten von Anwendungen, wie zum Beispiel die garbage collection wird ein großer Sieg, für die anderen mit zuteilen, alles dynamisch wird Sie töten. (Ich würde erwarten, dass seine zu den letzteren; er hat keine dynamische Zuordnungen, was so überhaupt, außerhalb seiner Liste. Aber die Tatsache, dass jeder push_back und pop_back zuordnen muss/frei ist, und das fehlen von Lokalität sind Mörder.)
  • Wenn richtig codiert und kompiliert mit Optimierung. Mit Java, brauchen Sie sich keine sorgen über die optimziation; JIT entscheidet, Wann und wo. Mit C++, müssen Sie dem compiler zu optimieren. (Und während ich würde nicht erwarten, dass ein massiver Unterschied, die Tatsache, dass er sich dynamisch zuweisen und jeden Point in Java könnte einen signifikanten Unterschied machen. Ich weiß nicht, ob die neuesten JIT-würde in der Lage sein, die Beseitigung, die.)
  • Plus die JIT-tatsächlich zu laufen. Und der garbage collector auch. BTW, ich vergaß, dass die benutzerdefinierten Typen zugeordnet werden musste dynamisch in java. Ich dachte, der array-basierte Probleme. Ich würde auch erwarten, dass diese einen Effekt haben.
  • Läuft der JIT kann ein Problem sein, besonders für ein kleines Programm wie seine. (Versuchen Sie, seinem Beispiel zu eine Millionen mal, und Sie können Sie ignorieren, die JIT.)
  • Und je nach code, der garbage collector kann schneller sein als die manuelle Zuordnung und die erforderlichen befreit. In seinem code, ist es fast sicher, dass die Gesamtkosten einer Zuweisung in Java billiger sein wird, als in C++, da er nie verwendet, genügend Speicherplatz für das auslösen der Sammler. Und selbst wenn Sie sich wiederholen, eine million mal, dies wäre wahr, weil Sie im optimalen Fall für die GC. Aber selbst der Schnellste Zuteilung ist langsamer als keine dynamische Allokation.
  • Wenn ich sehe, wie push_back ich erschaudern. Es gibt so viele Dinge, die jedes Programm langsam, andere als die Wahl der Sprache. Einige Menschen, die "grün um die Kiemen" zu denken, dass die Optimierung ist alles über compiler-Optimierung, wenn in der Tat, das sollte die Letzte Sache, die Sie betrachten.
  • Etwas zu merken, ist, dass Ihre Wahl von einem compiler hat einen realen Einfluss auf die Leistung. In einigen benchmarks, C-code, kompiliert mit gcc nicht laufen alle schneller als Java kompiliert mit einem guten compiler. Finden Sie diese stefankrause.net/wp/?p=6 und das stefankrause.net/wp/?p=6 für mehr info
  • C++ - code verwenden können, eine benutzerdefinierte Zuweisung (die aggregierten Zuweisungen und tun, nur ein einzelnes, frei später.) Das ist sogar noch schneller. Oder lassen Sie das frei heraus ein Vertrauen auf OS cleanup verlassen.
  • Vielleicht. Das ist mehr oder weniger wie die garbage collection funktioniert. Als einfach verlassen, das frei heraus; das ist genau das, was passiert, wenn Sie nicht genug Speicher, um garbage collection auszulösen (mit dem zusätzlichen plus, dass die Zuteilung algorithmen rechnen, die garbage collection sind schneller in der Verteilung). Natürlich in C++, können Sie verwenden einen garbage collector auch für die Fälle, in denen es die bessere Lösung ist.
  • Eigentlich, mit diesem Teil habe ich gemeint: Verwenden Sie eine Zuweisung explizit nicht unterstützt Freigabe an alle: Schneller und effizienter als die normale manuelle Freigabe sowie alle Müll-Sammler, selbst wenn es nie löst. (Das ist eine Optimierung für eine wirklich kleine Nische mit anständigen Dividenden...)
  • Ich sage Ihnen etwas - wenn Sie nicht planen, machen advenced Methoden (zum Beispiel in der künstlichen Intelligenz), der sollte ultra "optimiert", und jede Millisekunde wichtig ist... oder erweiterte Berechnungen in Grafik-oder ... etc.. Es ist nicht nötig, sich zu kümmern "C++ schneller als Java" - ja ist es, aber heute haben wir mächtig genug computer, um Sie nicht kümmern über eine solche Leistung in jedem normalen programm (natürlich sage ich nicht, dass über tradicional Optimalisierung wie makind nicht benötigt-loops 😛 ).. Java ist mächtig, denn Sie können die Verwendung von java fast überall mit hudge Bibliotheken unterstützen 😉
  • Alle allocators, die ich gesehen habe, die keine Unterstützung für die Freigabe auf alle arbeiten sehr viel, wie die allocators ein kopieren garbage collector; die Zuteilung der Zeit ist sehr, sehr schnell. Wo die garbage collection Kosten mehr in solchen Fällen ist, wenn es ausgelöst wird, und wenn Sie reservieren, wenig genug, so dass Sie nicht brauchen, um freigeben, dann die garbage collection sollte nicht immer auslösen, und Sie enden mit der Ausführung im wesentlichen den gleichen code.
  • Es hängt davon ab. Java ist sehr schlecht für numerische Anwendungen, wo Sie eine Menge von sehr kleinen Arten mit Wert-Semantik. Der JIT-nicht immer finden alle die Fälle, wo Sie konnten", so dass Sie am Ende mit zusätzlichen Zuweisungen, etc. die Kosten signifikante Echtzeit. Natürlich, der wahre Grund für Java nie benutzt wird, in solchen Fällen ist, dass die Sprache nicht ausdrucksstark genug, um lesbaren code schreiben für Sie. Am Ende, Java ist nicht für große scale-Programmierung, und es ist sehr schwierig zu schreiben, lesbar, zuverlässig-code in Java.
  • Aber der GC muss Kenntnis von der Art und Größe des jede Zuordnung. Die C++ - Lösung braucht es nicht, überhaupt, so die Verringerung der Zeit, die für die Zuteilung und die Größe der Zuweisungen.
  • sicherlich tut es wissen müssen, oder zumindest die Größe, als wenn Sie verstreut Blöcke von freigegebenen Speicher unter Speicher zugewiesen ist, an einem gewissen Punkt (wenn kein zusammenhängender block groß genug für seine nächste Zuteilung) hat es zu unterbrechen (wie ein gc, obwohl aus einem anderen Grund) und kompakte Speicher?
  • dies zeigt, man braucht eine Lizenz zur Verwendung von C++ (wie Sie eine Lizenz für eine Pistole)
  • Sry, aber du bist fehlt den Punkt: Wenn es keine Freigabe, es gibt keine Fragmentierung, keine Notwendigkeit für die Verfolgung von Arten, Größen und dergleichen.
  • Es gibt keine Programmier-Lizenz noch. Wie auch immer, wer wäre kompetent, Willens und vertrauenswürdig zu bewerten die Kompetenz von PHP, Java, Perl, C#, C++, [insert Programmiersprache] Programmierer?
  • was ich meine ist, dass, um frei, dass der Speicher irgendwann (es sei denn, Sie verwenden ein Betriebssystem, das nicht verwalten, Speicher) würde ich mir vorstellen, so etwas ist automatisch mit der Aufzeichnung der Größe der Zuweisung, und wie es sich durchsetzt unter Zuordnungen für andere Anwendungen (von denen jeder machen kann, - Freigabe und Fragmentierung etc.).
  • Aber wenn Sie nicht wnat, um den Speicher frei bisher, so dass es zu dem OS zu bereinigen, die auf Prozess beenden (was es ohnehin tun), es gibt keine Notwendigkeit zu halten Spur von jeder der Informationen, die notwendig ist, um freie zugewiesenen Blöcke, damit Sie nur nicht.
  • ja, macht Sinn. Ich dachte, ich würde es nicht, wenn Sie befreit es, aber wenn es tut, so oder so, warum dann nicht.
  • Ich würde wirklich empfehlen Sie nicht die Verwendung andere Sprache als Englisch für Variablen und Funktion von Namen. Manchmal ist Ihr code wird gelesen von Menschen, die nicht Französisch verstehen (wie, glaube ich, hier bei stack-overflow), das macht es schwerer für Sie, Lesen Sie Ihren code.

InformationsquelleAutor realUser404 | 2014-07-23
  1. 91

    std::list in C++ ist eine verknüpfte Liste, in der Erwägung, dass java.util.ArrayList ist ein array. Versuchen Sie ersetzen std::list durch std::vector. Auch, sicher sein, zu kompilieren mit Optimierung auf.

    • Ich bin jetzt immer 6 Sekunden für C++ nach dem Wechsel von vector und durch die Weitergabe mit Verweis. Es ist immer noch doppelt so viel wie Java, aber ich denke, es kommt auch auf den compiler an.
    • Für mich, der übergabe by reference ist langsamer in diesem Fall (ich denke, weil die Point Objekt ist nicht groß). Auch, welche compiler verwenden Sie? Für mich Ihre ursprünglichen C++ - code ist bereits schneller als der original-Java-code bei der Kompilierung mit Optimierung (g++-4.9 -O2).
    • Ersetzen double durch int in der Point-Struktur können die compiler erzeugen auch besseren code.
    • Guter Punkt. Java-code mit int vs. C++ - code mit double ist kein fairer Vergleich.
    • Ich bekomme auch einen deutlichen Schub durch den Austausch der loop-in - verifierNonPrise mit std::find_if
    • Meine Gedanken genau. Falsche Daten, die Struktur und falschen Datentyp. Weitere, in der Interessen zu helfen, unser Freund Peter, ich denke, jede Sprache hat Ihr eigenes STL-Macken. Immer fließend erfordert die Kenntnis der Bibliotheken sowie der Idiome.
    • Möchten Sie vielleicht zum detail, wie die std::list Struktur ist weniger effizient, für dieses Programm als std::vector. Ist es nur eine Frage, dass die grundlegenden Operationen (z.B. Zunahme von ein iterator) auf eine (doppelt verkettete) Liste benötigen mehr Zyklen als für einen Vektor, oder gibt es Sachen, die sind grundsätzlich langsamer für Listen (wie das element access by index)? In anderen Worten, führen Sie die beiden Implementierungen die gleiche asymptotische Komplexität nur mit einem Konstanten Faktor zwischen Ihnen, oder nicht?
    • In diesem Fall eben der zusammenhängenden Natur der vector auswirken können (mehr cache-freundlich).
    • Sicher, aber das tritt nur in dem Konstanten Faktor Zeug. Ich sage nicht, dass mit den Listen ist eine gute Idee, aber es könnte nur für einen account ein konstanter Faktor in der Geschwindigkeit.
    • Tatsächlich, je schneller ist die Verwendung von Punkt* eher als jeder STL-container (es ist leicht, hier zu tun, weil wir wissen, die Größe und es ist behoben). Siehe mein code-Vorschlag in meiner Antwort unten.
    • Es gibt absolut überhaupt keinen Grund, warum ein Vektor von Punkt-Objekte werden sollte, dass es langsamer als eine "Nackte" array von Point-Objekten.

    InformationsquelleAutor Brian
  2. 88

    Updates:

    Änderungen an C++

    • Wie geschrieben:

      Zusammenstellung Scheitern
    • Ersetzen math.h => cmath

      27610 Millisekunden
    • Add-O3 flag

      4416 Millisekunden
    • Ersetzen std::list mit std::vector

      2294 Millisekunden
    • Ersetzen Punkt mit std::pair

      2384 Millisekunden
    • Gemacht verifierNonPrise const richtige

      2351 Millisekunden
    • Ersetzt Schleife in verifierNonPrise mit std::find_if

      929 Millisekunden
    • Ersetzen Doppelzimmer mit int (damit es equiv Java)

      549 Millisekunden

    Änderungen an Java -

    • Wie geschrieben

      3459 Millisekunden
    • Änderungen verifierNonPrise frühe Rückkehr

      368 Millisekunden

    Java Vs C++

    > javac HuitDames.java
> time java HuitDames
real    0m0.368s
user    0m0.436s
sys     0m0.042s    
> g++ -O3 -std=c++11 HuitDames.cpp
> time ./a.out
real    0m0.541s
user    0m0.539s
sys     0m0.002s

    Der Endgültige Code:

    #include <iostream>
#include <vector>
#include <cmath>
#include <stdlib.h>
#include <chrono>
#include <algorithm>

using namespace std;

typedef std::pair<int, int>   Point;

#define LARGEUR_GRILLE 22
vector<Point> positions;


bool verifierNonPrise(Point const& emplacement) {
    return std::find_if(positions.begin(), positions.end(), [&emplacement](Point const& val){
        if (val.first != emplacement.first) {
            if ((val.second == emplacement.second) || (abs(val.second - emplacement.second) == abs(val.first - emplacement.first))) {
                return true;
            }
        }
        return false;
    }) == positions.end();
}

bool placerDame(int i) {
    bool bonnePosition = false;

    for (int j = 1; j <= LARGEUR_GRILLE && !bonnePosition; j++) {
        Point emplacement(i,j);
        positions.push_back(emplacement);
        if (verifierNonPrise(emplacement) && (i == LARGEUR_GRILLE || placerDame(i + 1))) {
            bonnePosition = true;
        }
        else {
            positions.pop_back();
        }
    }

    return bonnePosition;
}


int main()
{
    using std::chrono::system_clock;

    system_clock::time_point begin_time = system_clock::now();

    int i = 1;
    placerDame(i);
    for (vector<Point>::iterator it = positions.begin(); it!= positions.end(); it++) {
        cout << "(" << it->first << "; " << it->second << ")" << endl;
    }

    system_clock::time_point end_time = system_clock::now();

    long long elapsed_milliseconds = std::chrono::duration_cast<std::chrono::milliseconds>(end_time - begin_time).count();
    cout << "Duration (milliseconds): "
         << elapsed_milliseconds
         << std::endl;    
}
    • #include <algorithm> und #include <chrono> fehlen (nicht kompilieren auf meinem compiler auch ohne Sie). Auch, -O3 und -Ofast nichts ändern für die timings. Irgendwelche Gedanken, warum?
    • Sind die Zeiten für Replace std::list with std::vector, Replace Point with std::pair und Made verifierNonPrise const correct wirklich anders-oder sind die Unterschiede nur mess-imprecisions?
    • ermöglicht Optimierungen, die es ermöglichen, nicht-standard-Verhalten, aber immer noch Verhalten sich vernünftig, in den meisten Fällen (z.B. das optimieren einereineina (a - a)*(a*a). Es gibt einfach keine Gelegenheit, hier, wo dies könnte führen zu messbaren Verbesserungen.
    • Das Ergebnis ist genau wie ich es erwartet habe: Java-und C++ haben eine vergleichbare Leistung, wenn die Start-Zeit ist nicht so wichtig. Beachten Sie, dass Sie im Vergleich zu den nicht optimierten Java-version, wo die offensichtlichen bugs die noch nicht behoben wurden, wie z.B. die fehlerhafte Schleife in verifierNonPrise.
    • Betrachten Sie explizit aufrufen, wo Sie ändern die Datenstrukturen und Datentypen übereinstimmen, die Java-version, also eigentlich machen die Fälle überhaupt vergleichbar.
    • Das sind Reale Messungen (in Millisekunden) über einen Lauf. So wird es einige Schwankungen in den zahlen.
    • Ich dachte, ich Tat. Ersetzen std::list mit std::vector. Ersetzt Point mit std::pair<double, double> dann ersetzt alle double mit int.
    • Ich würde überlegen, die einzige wirkliche große Verbesserungen: 1) Schalten Sie die Optimierung. 2) Verwenden von std::vector über std::list 3) mit int statt double 4) Verwenden Sie standard-algorithmen anstatt hand geschrieben loops.
    • Hinzugefügt ein Update der Java-Versionen, so verifierNonPrise() zurück so bald wie möglich. Nun die Zeiten sind vergleichbar.
    • Was ist, wenn Sie entfernen <iostream> und verwenden printf statt? Das sollte deutlich beschleunigt werden.
    • Der Unterschied in der Geschwindigkeit zwischen den beiden ist (meist) ein Mythos. Viele der Artikel auf SO drüber. Wenn Sie sehen, ein Unterschied es ist, weil Sie vergessen zu nennen sync_with_stdio
    • href="http://stackoverflow.com/q/22225333/14065">stackoverflow.com/q/22225333/14065
    • Danke. Obwohl Sie nicht verwenden, die in Ihrem C++ - code...
    • Die output-Menge ist so klein, ich erwarte nicht, dass alle messbaren Unterschied in der Geschwindigkeit. Habe es gerade ausprobiert (kein Unterschied).
    • Einige kleine Verbesserung kann erhalten werden, indem nur tun, die push_back wenn keine überlappung gefunden für das neue, durch die Vereinfachung der Logik zu entfernen (unnötig benannte Variablen, entfernen von bedingten mit der Feststellung, dass die Zeilen ausgewertet werden (in aufsteigender Reihenfolge) und entfernen der abs, und dadurch die std::find_if über eine weniger element: coliru.stacked-crooked.com/a/2915144fc0c2a75e Auf Coliru, reduziert sich die Laufzeit von 1511ms zu 1130ms (-25%). Natürlich, YMMV, und Java könnte auch von diesen Veränderungen profitieren.
    • cout << "(" << it->first << "; " << it->second << ")" << endl; - sollte nicht sein, das Spülen der stream nach jeder line - endl sollte ersetzt werden, mit '\n'. Beachten Sie, dass der Java-code ist System.out.println("(" + point.x + "; " + point.y + ")"); ist nicht bündig, denn es gibt keinen Zeilenumbruch.
    • Sie timed, um zu sehen, was ist der prozentuale Unterschied????
    • hatte nicht ein guter compiler praktisch, so dass ich nur lief es auf ideone... kamen herab von über 1800ms zu 1700ms aber nicht sicher, wie reproduzierbar die hardware, Optimierung der Einstellungen, und das war mit inline vorangestellt verifierNonPrise auch, obwohl es war hoffentlich sein inlined sowieso, und ein cleanup auf den lambda return "X & Y" anstelle des if (X) if (Y) return true; return false; Tanz... wohl auch irrelevant.

    InformationsquelleAutor Martin York
  3. 30

    Test dieser version, aktualisiert mit C++11-features. Getestet in GCC 4.9.0 mit -std=c++11. Getestet auf Celeron 1.6 GHz, 512 MB RAM.

    Zeiten in meinem PC:

    Original: Dauer (Millisekunden): 12658

    Erste Version: Dauer (Millisekunden): 3616

    Optimierte Version: Dauer (Millisekunden): 1745

    Änderungen sind:

    • Mit vector statt list Benchmark, und Worte von Stroustrup.
    • Mit const, was wir können, ist der compiler in der Lage, zu optimieren, viel mehr, wenn es bekannt ist, dass der Wert nicht ändern.
    • Mit std::pair statt Punkt.
    • Mit neuen for-Schleife mit Konstanten Iteratoren.

    Quelle:

    #include <iostream>
#include <vector>
#include <chrono>
#include <iomanip>

using namespace std;

typedef std::pair<int, int> Point;

#define LARGEUR_GRILLE 22
vector<Point> positions;

bool verifierNonPrise(const Point& emplacement) {
    bool nonPrise = true;
    for (const auto& p : positions) {
        if (p.first != emplacement.first) {
            if (p.second == emplacement.second) {
                nonPrise = false;
            }
            if (abs(p.second - emplacement.second) ==
                abs(p.first - emplacement.first)) {
                nonPrise = false;
            }
        }
    }

    return nonPrise;
}

bool placerDame(int i) {
    bool bonnePosition = false;
    for (int j = 1; j <= LARGEUR_GRILLE && !bonnePosition; j++) {
        Point emplacement(i, j);
        positions.emplace_back(emplacement);
        if (verifierNonPrise(emplacement) &&
            (i == LARGEUR_GRILLE || placerDame(i + 1))) {
            bonnePosition = true;
        } else {
            positions.pop_back();
        }
    }

    return bonnePosition;
}

int main(int argc, char* argv[]) {
    std::chrono::system_clock::time_point begin_time =
        std::chrono::system_clock::now();

    positions.reserve(LARGEUR_GRILLE);

    placerDame(1);
    for (const auto& p : positions) {
        cout << "(" << p.first << "; " << p.second << ")" << endl;
    }

    std::chrono::system_clock::time_point end_time =
        std::chrono::system_clock::now();
    long long elapsed_milliseconds =
        std::chrono::duration_cast<std::chrono::milliseconds>(
            end_time - begin_time).count();
    std::cout << "Duration (milliseconds): " << elapsed_milliseconds
              << std::endl;

    return 0;
}

    Etwas mehr Tiefe verpasst.

    Änderungen:

    • Der Rückkehr so früh wie möglich. Sobald die Königin kann nicht platziert werden.
    • Rückkehr zu einem einfacheren Punkt-Klasse.
    • Mit find_if Algorithmus für die Suche der Königin Platzierung.

    Quelle (einige Empfehlung aktualisiert):

    #include <algorithm>
#include <iostream>
#include <vector>
#include <chrono>
#include <iomanip>

using namespace std;

struct Point {
    int x, y;
};

#define LARGEUR_GRILLE 22
vector<Point> positions;

bool verifierNonPrise(const Point& emplacement) {
    return find_if(positions.cbegin(), positions.cend(), [&emplacement](const Point& p) {
               return (p.x != emplacement.x &&
                       (p.y == emplacement.y ||
                        abs(p.y - emplacement.y) == abs(p.x - emplacement.x)));
           }) == positions.cend();
}

bool placerDame(int i) {
    for (int j = 1; j <= LARGEUR_GRILLE; j++) {
        Point emplacement{i, j};
        positions.push_back(emplacement);
        if (verifierNonPrise(emplacement) &&
            (i == LARGEUR_GRILLE || placerDame(i + 1))) {
            return true;
        } else {
            positions.pop_back();
        }
    }
    return false;
}

int main(int argc, char* argv[]) {
    std::chrono::system_clock::time_point begin_time =
        std::chrono::system_clock::now();

    positions.reserve(LARGEUR_GRILLE);

    placerDame(1);
    for (const auto& p : positions) {
        cout << "(" << p.x << "; " << p.y << ")" << endl;
    }

    std::chrono::system_clock::time_point end_time =
        std::chrono::system_clock::now();
    long long elapsed_milliseconds =
        std::chrono::duration_cast<std::chrono::milliseconds>(
            end_time - begin_time).count();
    std::cout << "Duration (milliseconds): " << elapsed_milliseconds
              << std::endl;

    return 0;
}
    • Und? Wie funktioniert es ausführen, im Vergleich zum original?
    • Nicht sicher, warum std::pair? Aus einer Sicht des design, es ist definitiv etwas, was Sie vermeiden wollen. Ich zweifle auch daran, dass mit emplace_back macht einen erheblichen Unterschied; es ist mehr fein-tuning. (Mit std::vector - und referenzübergabe sind zweifellos die großen Gewinne.)
    • Auf meiner Maschine Original 4296 ms. NetVipeC version 682. Wahrscheinlich noch einige Verbesserungen vorgenommen werden, aber schon eine große Verbesserung
    • ja in diesem Fall emplace_back nicht gewinnen, nichts habe ich geändert, weil denke, dass emplacement variable in der Methode placerDame war nur für das einfügen in die vector rückgängig zu machen und wenn Sie sehen, der Aufruf zu verifierNonPrise, aber vergessen emplace_back. Der Grund für std::pair war, dass es keinen Grund gibt, eine Klasse zu erstellen für etwas, STD cover, ist nur mehr code pflegen, mehr code zu testen, auch wenn ist so trivial, und std::make_pair (in einigen Compilern nur eine Zuteilung für die 2 Arten), in diesem Fall ist nicht viel, aber die Schaffung von 1 Million Paare, das wäre ein Unterschied.
    • Kein compiler tun sollte eine Zuweisung für irgendetwas außerhalb von std::vector hier. Es wäre viel sauberer, und nicht langsamer, Sie zu einer Klasse. Oder, da du dich mit C++11, eine Struktur mit Liste der Initialisierung. Und natürlich std::pair ist Verschleierung, denn die Mitglieder sind der nicht ersten und zweiten, aber x und y (das hat eine klare semantische Bedeutung); std::pair ist praktisch für schnelle Experimente, aber Ihre Verwendung ist ein anti-pattern in der ernst-code.
    • Ich könnte hinzufügen, dass Ihre Verwendungen von const helfen nicht dem compiler zu optimieren, da der compiler kann nicht davon ausgehen, dass das Objekt geändert wird nicht durch einen anderen Pfad. (Auf der anderen Seite, Sie helfen die Lesbarkeit zu verbessern.)
    • Nach dem Wechsel zum std::list -> std::vector und Point -> std::pair die beste Verbesserung, die ich bekam, war der Einsatz von std::find_if statt eines expliziten Schleife.
    • Die Tatsache ist, dass es nicht Punkte, die gespeichert werden sollen in den Vektor. Derzeit ist es immer wahr, dass positions[i].x == i. Dies bedeutet, dass die Speicherung der x-Koordinate ist überflüssig. Sie können lassen Sie nur die y (und verwenden std::vector<int>).
    • Sie haben Recht, wahrscheinlich wird es keinen großen performance-Gewinn, zumindest in diesem speziellen Fall, aber es ist besser, nicht um die Speicherung von redundanten Informationen.

    InformationsquelleAutor NetVipeC
  4. 19

    Vergleich verwaltet, dynamisch kompilierten Sprache wie Java eine statisch kompilierte Sprache wie C++, ist sehr schwierig.

    Werden Sie immer äpfel mit Birnen vergleichen in einem gewissen Sinne, denn Sie sind konzeptionell sehr unterschiedlich. Es beginnt mit der Nutzung von standard-Bibliotheken (ArrayList vs std::list/vector), die möglicherweise völlig unterschiedliche Leistungsmerkmale, auch dein code sieht ähnlich aus in beiden Sprachen.

    Dann ist es die inhärente problem mit microbenchmarks in Java (kurzer test in Java immer langsamer, weil die JIT beobachten den Programmablauf, bevor er entscheidet, was und wie es zusammengestellt werden). Gleiches gilt für die compiler-Optionen für C++, auch die Struktur der source-code (unabhängig kompiliert und verlinkt Klassen im Vergleich zu single-Datei, Quelle) einen großen Unterschied machen kann (weil es ändert sich die Höhe des "Einblick" der C++ - compiler in den anderen Klassen).

    Nächstes wird der Allgemeine Unterschied in der memory management, garbage collection-vs-Handbuch memory management (smart pointers etc. sind immer noch als die manuelle Speicherverwaltung).

    Nicht zu erwähnen, die Allgemeine Sprache Unterschiede wie müssen Sie explizit deklarieren eine Methode virtual in C++ und in Java jeder member-Methode ist standardmäßig virtuell (arbeiten Sie heraus, ob es wirklich virtuell zur Laufzeit ist in der VM).

    ... Mit alle diese Unterschiede wird es immer Fälle geben, in denen eine Sprache haben einen massiven Vorteil gegenüber den anderen. Ein einfacher test mit sehr begrenzten Rahmen (wie dein test hier) sagt sehr wenig über jede Sprache als ganzes.

    Ein weiterer Punkt, den Menschen neigen oft dazu, zu ignorieren, ist: Wie produktiv kann man mit einer Sprache, Geschwindigkeit ist nicht alles (Aussehen, wie erfolgreiche Skript langages sind in einigen Bereichen, trotz kaum konkurrenzfähiger, wenn man nur bei der Ausführung Geschwindigkeit). Mangelnde Leistung kann lähmend sein, aber so kann die geringe Produktivität.

    • +1 Überlassen Sie es dem Schweizer zu sein, so Diplomatisch 🙂
    • Ich denke, der Punkt der Frage ist, dass OP hätte (zu Recht) erwartet, dass C++ schneller zu sein in diesem besonderen Fall, und war überrascht, dass es war viel langsamer. Es gibt keine äpfel oder Orangen hier.
    • Dann wird der Titel der quest sollte worden", Wie zur Verbesserung dieser C++ - code", und es wäre wahrscheinlich besser, einfach auf codereview. Während andere Antworten decken mögliche Optimierungen sowie, Sie alle vernachlässigen die Natur aus unvergleichliches Aussehen - und einige Optimierungen vorgeschlagen, die Ergebnisse noch unvergleichlicher. Das einzig richtige war die änderung der C++ - version der vector-denn es ist ähnlich wie ArrayList. Aber alles andere ist nur eine Erhöhung der Differenz zwischen den beiden Implementierungen, wo es wird äpfel mit Birnen vergleichen.
    • ändern Punkt-Koordinaten double in int macht es noch anderes, um das Java-Beispiel. Und es kann von einem großen preformace Unterschied.
    • Während ich von ganzem Herzen Zustimmen, die Ihres gleichen Datentypen machen es ähnlich, aber meine Allgemeinen "äpfel mit Birnen" gemeint war, hin zu Optimierungs-versuche wie "die Rückkehr so früh wie möglich. Sobald die Königin kann nicht platziert werden." wo die Logik ist sogar grundlegend verändert. Habe ich nicht einzeln durchgehen und überprüfen Sie die OP ' s original-code, wenn Sie ähnlich war es in den ersten Platz, so dass ich noch gar nicht bemerkt, dass dieser Fehler existiert in der ursprünglichen C++ - version. Ich habe einfach Vertrauenswürdige, als er sagte exakt gleichen Algorithmus, dass es keine solche grundlegenden (und oft unmotiviert) Unterschiede.
    • Mein Punkt war, Ihr "Das einzig richtige war die änderung der C++ - version der vector-denn es ist ähnlich wie ArrayList. Aber alles andere ist nur eine Erhöhung der Differenz zwischen den beiden Implementierungen, in denen es äpfel mit Birnen vergleichen." war nicht komplett wahr. Die java-Optimierer erzeugen kann besser/schneller code aufgrund der integregral Daten geben. Einer der genau richtig/vorgeschlagenen Lösungen beinhaltet diese änderung. Ich habe nicht die Absicht zu polemize mit Ihren Bemerkungen auf die Optimierung und das benchmarking im Allgemeinen.
    • -1. Das ist Quatsch. Alles, was Sie sagte, impliziert C++ schneller sein soll hier. "Äpfel und Birnen vergleichen" ist nur weasling. Uhren können alles vergleichen, der Zeit braucht. Der Vergleich ist legitim. Aber Sie scheinen zu bestätigen, dass Sie Sie vergleichen können, indem Sie miteinander verglichen werden. Sie nicht nur zu diskutieren, Ihre Auswirkungen auf die Geschwindigkeit des Programms. Kurz gesagt, diese Antwort würde einen guten Frage, aber die Antworten nichts.

    InformationsquelleAutor Durandal
  5. 3

    Ich kann schlagen ein Totes Pferd hier, aber Sie einfach tun, eine Zeile für Zeile übersetzung von Java zu C++, auch nicht mit const Referenz-Parameter oder eine solche Sache, die Sie sehen können, C++ ist fast doppelt so schnell wie Java.
    Alle die "syntaktische-Optimierung" emplacing etc. hat wenig Wirkung, wenn jede... 

    rep ~/Documents $ g++ -O3 Queen.cpp
rep ~/Documents $ javac Queen.java 
rep ~/Documents $ time java Queen 
(1; 1)
(2; 3)
(3; 5)
(4; 2)
(5; 4)
(6; 10)
(7; 14)
(8; 17)
(9; 20)
(10; 13)
(11; 19)
(12; 22)
(13; 18)
(14; 8)
(15; 21)
(16; 12)
(17; 9)
(18; 6)
(19; 16)
(20; 7)
(21; 11)
(22; 15)

real    0m4.806s
user    0m4.857s
sys     0m0.067s
rep ~/Documents $ time ./a.out
(1; 1)
(2; 3)
(3; 5)
(4; 2)
(5; 4)
(6; 10)
(7; 14)
(8; 17)
(9; 20)
(10; 13)
(11; 19)
(12; 22)
(13; 18)
(14; 8)
(15; 21)
(16; 12)
(17; 9)
(18; 6)
(19; 16)
(20; 7)
(21; 11)
(22; 15)

real    0m2.131s
user    0m2.113s
sys     0m0.000s
rep ~/Documents $

    Queen.java (ins englische übersetzt)

    import java.awt.Point;
import java.util.ArrayList;
import java.util.List;

public class Queen {

    private static List<Point> positions = new ArrayList<>();
    private static final int GRID_SIZE = 22;

    public static void main(String[] args) 
    {
        int i = 1;
        placeQueen(i);
        for (Point point : positions) 
        {
            System.out.println("(" + point.x + "; " + point.y + ")");
        }
    }

    private static boolean placeQueen(int i) 
    {
        boolean bIsGoodPos = false;
        for (int j = 1; j <= GRID_SIZE && bIsGoodPos == false; j++) 
        {
            Point emplacement = new Point(i, j);
            positions.add(emplacement);
            if (verifyPos(emplacement) && (i == GRID_SIZE || placeQueen(i + 1))) 
            {
                bIsGoodPos = true;
            }
            else 
            {
                positions.remove(i - 1);
            }
        }

        return bIsGoodPos;
    }

    private static boolean verifyPos(Point position) 
    {
        boolean bIsSafe = true;
        for (Point point : positions) 
        {
            if (!point.equals(position)) 
            {
                if (position.y == point.y) 
                {
                    bIsSafe = false;
                }
                if (Math.abs(position.y - point.y) == Math.abs(position.x - point.x)) 
                {
                    bIsSafe = false;
                }
            }
        }

        return bIsSafe;
    }
}

    Queen.cpp

    #include <cmath>
#include <vector>
#include <iostream>

using namespace std;

struct Point
{
    int x, y;
    Point(int ii, int jj):x(ii), y(jj){}
};

vector<Point> positions;
int GRID_SIZE = 22;


bool verifyPos(Point position) 
{
    bool bIsSafe = true;
    for(int i = 0; i < positions.size(); ++i) 
    {
        Point point = positions[i];
        if(point.x != position.x || point.y != position.y) 
        {
            if(position.y == point.y) 
            {
                bIsSafe = false;
            }
            if(abs(position.y - point.y) == abs(position.x - point.x)) 
            {
                bIsSafe = false;
            }
        }
    }

    return bIsSafe;
}

bool placeQueen(int i) 
{
    bool bIsGoodPos = false;
    for(int j = 1; j <= GRID_SIZE && bIsGoodPos == false; j++) 
    {
        Point p(i, j);
        positions.push_back(p);
        if(verifyPos(p) && (i == GRID_SIZE || placeQueen(i + 1))) 
        {
            bIsGoodPos = true;
        }
        else 
        {
            positions.pop_back();
        }
    }
    return bIsGoodPos;
}


int main(void) 
{
    int i = 1;
    placeQueen(i);
    for(int i = 0; i < positions.size(); ++i) 
    {
        Point p = positions[i];
        cout << "(" << p.x << "; " << p.y << ")" << endl;
    }

    return 0;
}
    InformationsquelleAutor rep_movsd
  6. 2

    C++ machen kann in 21 ms (auf einem alten core i7-860), wenn Sie bit-Karten. Für die timing-run, den ich auskommentiert, die showSoln () - Aufruf, da der eine grafische Darstellung der Schachbrett dauert doppelt so lange, als das finden der Lösung.

    #include <iostream>
#include <iomanip>
#include <fstream>
#include <omp.h>                        //omp_get_wtime() is my favorite time function
using namespace std;

static const unsigned n(22);            //size of board
static_assert(n<32,"use long unsigned for bit masks if n > 32");
static const unsigned mask((1U<<n)-1);  //n wide bitmask with every bit set

void showSoln(unsigned* selCol, unsigned numSoln) {     //show a solution
    cout << "\nsolution " << numSoln << '\n';
    for (unsigned row=0; row<n; ++row) {
        for (unsigned col=0; col<n; ++col)
            cout << (col==selCol[row]? " Q": " .");
        cout << '\n';
    }
}

void main() {
    //for each row bitmasks that show what columns are attacked, 1 bit means attacked
    unsigned ulAttack[n];           //cols attacked from upper left, shift right for next row
    unsigned upAttack[n];           //cols attacked from straight up, same for next row
    unsigned urAttack[n];           //cols attacked from upper right, shift left for next row
    unsigned allAttack[n];          //OR of all attacks on given row
    allAttack[0]= ulAttack[0]= upAttack[0]= urAttack[0]= 0; //no attacks on row 0
    unsigned row= 0;                //the row where now placing a queen 
    unsigned selCol[n];             //for each row the selected column
    unsigned numSoln= 0;            //count of soutions found
    double wtime= omp_get_wtime();
    for (;;) {                                          //loop until find 1st (or all) solutions
        if (allAttack[row]!=mask) {                     //if 'row' has a column not attacked
            unsigned long bit;
            _BitScanForward(&bit,~allAttack[row]);      //find lowest column not attacked
            //note - your compiler may have a different intrinsic for find lowest set bit
            selCol[row]= bit;                           //remember selected column for this row
            unsigned move= 1U<<bit;                     //convert selected column to bitmask
            allAttack[row]|= move;                      //mark column attacked to prevent re-use
            if (row==n-1) {                             //if move in last row have a soln
                ++numSoln;
                showSoln(selCol,numSoln);
                break;                                  //remove this break if want all solutions
            } else {                                    //no solution yet, fill in rows below
                unsigned nrow= row+1;                   //next row
                //from attacks on this row plus 'move' decide attacks on row below
                ulAttack[nrow]= (ulAttack[row] | move) >> 1;
                upAttack[nrow]= (upAttack[row] | move);
                urAttack[nrow]= ((urAttack[row] | move) << 1) & mask;
                allAttack[nrow]= ulAttack[nrow] | upAttack[nrow] | urAttack[nrow];
                row= nrow;                              //go to next row
            }
        } else {                //else move on 'row' is impossible so backtrack
            if (!row)           //if backtrack from row 0 have found all solutions
                break;
            --row;              //try next move in prior row
        }
    }
    wtime= omp_get_wtime() - wtime;
    cout << "numSoln= " << numSoln << '\n';
    cout << "time= " << wtime*1000 << " msec\n";
}
    InformationsquelleAutor snstrand
  7. 1

    Auch, es gibt keinen Grund für die Verwendung von float/doouble-Typen, die für die Koordinaten.

    Sollten Sie die Leistung erhalten, wenn Sie nicht mit Gewalt aufrufenden floating-point-abs-library-Aufruf in der C++ -

    Java speichert die Koordinaten als integer. Die get-Funktionen geben Doppel, doch dies ist wohl leichter zu optimieren, der Weg in Java, dann in c++.

    InformationsquelleAutor Jakub
  8. 0

    Es scheint, dass der code, der benötigt nicht zu viel Speicher zugreifen und intensive computing der Unterschied zwischen Java eine C++ ist gering. Aber in der umgekehrten situation den Unterschied sieht toll aus :

    test.java

    import java.lang.String;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class test{
    private static Random gna=new Random();

    public static double new_value(double value){
        if (value<0.5) value=0;
        return value*value;
    }

    public static void main(String[] args) {
        long start_time = System.currentTimeMillis();   
        List<Double> ze_list=new ArrayList();
        for (int i=0;i<1e8;i++){
            double temp=new_value(gna.nextDouble());
            ze_list.add(temp);
        }
        long end_time = System.currentTimeMillis();
        System.out.println("Time (s) :"+ ((end_time-start_time)/1000));
        Scanner input = new Scanner(System.in);
        String inputval = input.next();
    }
}

    und vergleichen Sie es test.cpp:

    #include <iostream>
#include <vector>
#include <ctime>
#include <random>
using namespace std;

static default_random_engine dre1(time(0));
static uniform_real_distribution <double> urd1(0, 1);

static double new_value(double value){
    if (value<0.5) value=0;
    return value*value;
}

int main(void){
        time_t tbegin,tend;
        double texec=0;
        tbegin=time(NULL);
        vector<double> ze_list;
        for (int i=0;i<1e8;i++){
            double temp=new_value(urd1(dre1));
            ze_list.push_back(temp);
        }
        tend=time(NULL);
        texec=difftime(tend,tbegin);
        cout << "\nTime (s) " << texec << " s\n";
        int val=0;
        cin >> val;
    return 0;
}

    Habe es gerade getestet auf meinem Mac :

    • die Java-version nahm der 90er Jahre und erforderlich 3.77 Gehen
    • die C++ - programm nahm 2s und nur erforderlich, 770 Mo

    Gibt es vielleicht eine Möglichkeit, die Java-Leistungen, aber ich sehe nicht, wie.

    InformationsquelleAutor 3dmaze
  9. -1

    Java übergibt Objekte um Methoden-Referenzen und die Referenzen als Wert übergeben werden, aber C++ geht Gegenstände von Wert.

    Sollten Sie C++ - code machen es gleich wie Java (Übergeben von Zeigern in C++ intstead der übergabe von Objekten):

    bool verifierNonPrise(Point* emplacement) //The correct way for passing arguments.
    InformationsquelleAutor Amir Saniyan
Schreibe einen Kommentar