Performance issue: Java vs C++
I have always heard that C++ was way more efficient than Java (and that is why most games are developed in C++).
I wrote a small algorithm to solve the "Eight queens puzzle" in both Java and C++, using the exact same algorithm, and then started to raise the number or squares. When reaching checkboards of 20*20 or even 22*22, it appears Java is much more effective (3 seconds vs 66 seconds for C++).
I have no idea why, but I am pretty beginning with C++, so it is possible I made some huge performance mistakes, so I will gladly accept any information that would help me understand what is happening.
Below is the code I use 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;
}
}
And below is the 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::list in C++ is a linked list, whereas java.util.ArrayList is an array. Try replacing std::list by std::vector . Also, be sure to compile with optimization turned on.
Updates:
Changes to C++
Compilation Failure
27610 milliseconds
4416 milliseconds
2294 milliseconds
2384 milliseconds
2351 milliseconds
std::find_if 929 milliseconds
549 milliseconds
Changes to Java
3459 milliseconds
verifierNonPrise early return 368 milliseconds
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
Final 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;
}
Test this version, updated using C++11 features. Tested in GCC 4.9.0 with -std=c++11 . Tested on Celeron 1.6 GHz, 512 MB RAM.
Times in my PC:
Original: Duration (milliseconds): 12658
First Version: Duration (milliseconds): 3616
Optimized Version: Duration (milliseconds): 1745
Changes are:
vector instead of list Benchmark, and Words from Stroustrup. Source:
#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;
}
Some more deep changes.
Changes include:
Source (some recommendation updated):
#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;
}
上一篇: 你用什么编码技术来优化C程序？
下一篇: 性能问题：Java与C ++