Leistungsproblem: Java vs C ++

Ich habe immer gehört, dass C ++ viel effizienter als Java ist (und deshalb werden die meisten Spiele in C ++ entwickelt).

Ich schrieb einen kleinen Algorithmus, um das "Acht-Königinnen-Rätsel" in Java und C ++ mit genau demselben Algorithmus zu lösen, und begann dann, die Zahl oder die Quadrate zu erhöhen. Wenn Sie Checkboards von 20 * 20 oder sogar 22 * ​​22 erreichen, scheint Java viel effektiver zu sein (3 Sekunden gegenüber 66 Sekunden für C ++).

Ich habe keine Ahnung warum, aber ich fange ziemlich gut mit C ++ an, daher ist es möglich, dass ich einige große Leistungsfehler gemacht habe. Daher akzeptiere ich gerne alle Informationen, die mir helfen würden, zu verstehen, was passiert.

Unten ist der Code, den ich in Java verwende:

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 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;
}

std::listin C ++ ist eine verknüpfte Liste, während java.util.ArrayListes sich um ein Array handelt. Versuchen Sie, std::listdurch zu ersetzen std::vector. Stellen Sie außerdem sicher, dass Sie bei aktivierter Optimierung kompilieren.

Aktualisierung:

Änderungen an C ++

• Wie geschrieben:
  Kompilierungsfehler
• Ersetzen Sie math.h => cmath
  27610 Millisekunden
• Fügen Sie -O3-Flag
  4416 Millisekunden hinzu
• Ersetzen Sie std :: list durch std :: vector
  2294 Millisekunden
• Ersetzen Sie Point durch std :: pair
  2384 Millisekunden
• VerifierNonPrise const wurde auf
  2351 Millisekunden korrigiert
• Die Schleife in verifierNonPrise wurde durch std::find_if
  929 Millisekunden ersetzt
• Ersetzen Sie double durch int (damit es Java entspricht)
  549 Millisekunden

Änderungen an Java

• Wie geschrieben
  3459 Millisekunden
• Ändert die verifierNonPrisefrühe Rendite um
  368 Millisekunden

Java gegen 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

Endgültiger 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;    
}

Testen Sie diese Version, die mit C ++ 11-Funktionen aktualisiert wurde. 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:

• Verwenden vectoranstelle von list Benchmark und Wörter von Stroustrup .
• Mit const kann der Compiler viel mehr optimieren, wenn er weiß, dass sich der Wert nicht ändert.
• Verwenden von std :: pair anstelle von Point.
• Verwenden einer 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;
}

Noch tiefere Veränderungen.

Änderungen umfassen:

• Rückkehr so ​​früh wie möglich. Sobald die Königin nicht platziert werden kann.
• Zurück zu einer einfacheren Punktklasse.
• Verwenden des find_if-Algorithmus zum Suchen der Platzierung von Königinnen.

Quelle (einige Empfehlungen 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;
}

Der Vergleich einer verwalteten, dynamisch kompilierten Sprache wie Java mit einer statisch kompilierten Sprache wie C ++ ist sehr schwierig.

Sie werden Äpfel immer in gewissem Sinne mit Orangen vergleichen, weil sie konzeptionell sehr unterschiedlich sind. Es beginnt mit der Verwendung der Standardbibliotheken (ArrayList vs std :: list / vector), die möglicherweise sehr unterschiedliche Leistungsmerkmale aufweisen, selbst wenn Ihr Code in beiden Sprachen ähnlich aussieht.

Dann gibt es das inhärente Problem mit Mikrobenchmarks in Java (kurze Tests in Java sind immer langsamer, da die JIT den Programmfluss beobachtet, bevor sie entscheidet, was und wie kompiliert werden soll). Gleiches gilt für Compileroptionen für C ++. Selbst die Struktur des Quellcodes (unabhängig kompilierte und verknüpfte Klassen im Vergleich zu einer einzelnen Dateiquelle) kann einen signifikanten Unterschied bewirken (da sich dadurch die Menge an "Einsicht" ändert, die der C ++ - Compiler in die anderen Klassen hat). .

Als nächstes folgt der allgemeine Unterschied zwischen Speicherverwaltung, Speicherbereinigung und manueller Speicherverwaltung (intelligente Zeiger usw. gelten weiterhin als manuelle Speicherverwaltung).

Ganz zu schweigen von den allgemeinen Sprachunterschieden, wie Sie eine Methode in C ++ explizit als virtuell deklarieren müssen, während in Java jede Mitgliedsmethode standardmäßig virtuell ist (es ist der VM überlassen, ob sie zur Laufzeit wirklich virtuell ist).

Bei all diesen Unterschieden wird es immer Fälle geben, in denen eine Sprache einen massiven Vorteil gegenüber der anderen hat. Ein einfacher Test mit sehr begrenztem Umfang (wie Ihr Test hier) sagt sehr wenig über jede Sprache als Ganzes aus.

Ein weiterer Punkt, den die Leute oft ignorieren, ist: Wie produktiv können Sie mit einer Sprache sein - Geschwindigkeit ist nicht alles (sehen Sie, wie erfolgreich Skriptsprachen in einigen Domänen sind, obwohl sie kaum wettbewerbsfähig sind, wenn Sie nur die Ausführungsgeschwindigkeit betrachten). Ein Mangel an Leistung kann lähmend sein, aber auch eine geringe Produktivität.

Ich mag hier ein totes Pferd schlagen, aber wenn ich einfach eine zeilenweise Übersetzung von Java nach C ++ mache, ohne auch nur konstante Referenzparameter oder ähnliches zu verwenden, kann man sehen, dass C ++ fast doppelt so schnell ist wie Java. Alle "syntaktischen Optimierungs" -Einlagerungen usw. haben, wenn überhaupt, nur geringe Auswirkungen ...

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;
}

C ++ kann dies in 21 ms (auf einem alten Core i7-860) tun, wenn Sie Bitmaps verwenden. Für den Timing-Lauf habe ich den Aufruf von showSoln () auskommentiert, da eine grafische Anzeige des Schachbretts doppelt so lange dauert wie 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";
}

Es gibt auch keinen Grund, Float / Doouble-Typen für die Koordinaten zu verwenden.

Sie sollten an Leistung gewinnen, wenn Sie den Aufruf von Gleitkomma-Abs-Bibliotheken in C ++ nicht erzwingen

Java speichert die Punktkoordinaten als Ganzzahl. Die get-Funktionen geben double zurück, dies ist jedoch wahrscheinlich einfacher in Java zu optimieren als in c ++.

Es scheint, dass für Code, der nicht zu viel Speicherzugriff und intensives Rechnen erfordert, der Unterschied zwischen Java und C ++ gering ist. Aber in der umgekehrten Situation sieht der Unterschied erstaunlich 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 vergleiche es mit 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;
}

Ich habe es gerade auf meinem Mac getestet:

• Die Java-Version dauerte 90s und erforderte 3.77 Go
• Das C ++ - Programm dauerte 2 Sekunden und benötigte nur 770 Mo.

Vielleicht gibt es eine Möglichkeit, die Java-Leistung zu steigern, aber ich kann nicht sehen, wie.

Java übergibt Objekte als Referenzen an Methoden und diese Referenzen werden als Wert übergeben, C ++ übergibt Objekte jedoch als Wert.

Sie sollten den C ++ - Code so ändern, dass er mit Java identisch ist (Übergeben Sie Zeiger in C ++ anstelle von übergebenen Objekten):

bool verifierNonPrise(Point* emplacement) // The correct way for passing arguments.