性能问题:Java与C ++

我一直听说C ++比Java更有效率(所以大多数游戏都是用C ++开发的)。

我写了一个小的algorithm来解决Java和C ++中的“八皇后问题”,使用完全相同的algorithm,然后开始提高数量或方块。 当达到20 * 20甚至22 * 22的检查板时,看起来Java效率更高(C ++为3秒,而66秒为多)。

我不知道为什么,但我很早就开始使用C ++,所以我可能犯了一些巨大的性能错误,所以我会很乐意接受任何有助于我理解正在发生的事情的信息。

以下是我在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; } } 

以下是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; } 

C ++中的std::list是一个链表,而java.util.ArrayList是一个数组。 尝试用std::list std::vectorreplacestd::list 。 另外,一定要编译优化打开。

更新:

对C ++的更改

  • 正如所写:
    编译失败
  • replacemath.h => cmath
    27610毫秒
  • 添加-O3标志
    4416毫秒
  • 用std :: vectorreplacestd :: list
    2294毫秒
  • 用std :: pairreplace点
    2384毫秒
  • 使verifierNonPrise常量正确
    2351毫秒
  • 使用std::find_ifreplaceverifierNonPrise中的循环
    929毫秒
  • 用intreplacedouble(使其等同于Java)
    549毫秒

对Java的改变

  • 正如书面
    3459毫秒
  • 更改verifierNonPrise提前返回
    368毫秒

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

最终代码:

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

testing这个版本,使用C ++ 11function进行更新。 使用-std=c++11testingGCC 4.9.0。 testing赛扬1.6 GHz,512 MB RAM。

在我的电脑中的时代:
原文: 持续时间(毫秒):12658
第一个版本: 持续时间(毫秒):3616
优化版本: 持续时间(毫秒):1745

变化是:

  • 使用vector而不是list Benchmark和Stroustrup的单词 。
  • 如果知道值不变,编译器就可以使用const来进行更多的优化。
  • 使用std :: pair而不是Point。
  • 使用带有常量迭代器的新的for循环。

资源:

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

一些更深的变化。

变化包括:

  • 尽早回归。 一旦女王不能放置。
  • 返回到一个更简单的Point类。
  • 使用find_ifalgorithmsearch皇后位置。

来源(更新了一些build议):

 #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 (px != emplacement.x && (py == emplacement.y || abs(py - emplacement.y) == abs(px - 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 << "(" << px << "; " << py << ")" << 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; } 

将像Java这样的托pipe的dynamic编译语言与像C ++这样的静态编译语言进行比较是非常困难的。

从某种意义上说,你将永远比较苹果和橙子,因为它们在概念上是非常不同的。 它从使用标准库(ArrayList vs std :: list / vector)开始,这些库将具有潜在的非常不同的性能特征,即使你的代码在两种语言中都看起来相似。

那么Java中的microbenchmarks就存在固有的问题(Java中的简短testing总是比较慢,因为JIT将在决定编译之前以及如何编译之前观察程序stream)。 C ++的编译器选项也是如此,甚至源代码的结构 (独立编译和链接类与单个文件源)也可以产生显着的差异(因为它改变了C ++编译器对其他类的“洞察”数量) 。

接下来是内存pipe理,垃圾收集与手动内存pipe理(智能指针等仍被视为手动内存pipe理)的一般差异。

更不用说一般的语言差异了,比如你需要在C ++中明确地声明一个虚拟的方法,而在Java中, 每个成员方法都是默认虚拟的(假设虚拟机在运行时真的是虚拟的)。

所有这些差异总会有一种情况,一种语言会比另一种语言具有巨大的优势。 一个范围非常有限的简单testing(比如你的testing)对整个语言的描述都很less。

人们经常会忽略的另一点是:语言能力有多高 – 速度不是一切(看起来语言是一种成功的脚本语言,尽pipe在只看速度时几乎没有竞争力)。 性能不足可能会导致瘫痪,但生产力也可能会降低。

我可能在这里打死了一个死马,但是只要做一个Java到C ++的逐行翻译,甚至不使用const引用参数或任何类似的东西,你可以看到C ++几乎是Java的两倍。 所有的“语法优化”的摆设等,如果有什么影响… …

 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(翻译成英文)

 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 << "(" << px << "; " << py << ")" << endl; } return 0; } 

此外,没有理由使用float / doubletypes的坐标。

如果您不强制在C ++中调用浮点型abs库调用,则应该获得性能

Java将Point坐标存储为整数。 get函数返回double,但是这可能更容易在Java中进行优化,然后在c ++中进行优化。

如果使用位图,C ++可以在21 ms(在旧的核心i7-860上)完成。 对于定时运行,我注意到了showSoln()调用,因为棋盘的graphics显示需要两倍的时间才能find解决scheme。

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

Java将对象作为引用传递给方法,并且这些引用通过值传递,但是C ++通过值传递对象。

您应该更改C ++代码,使其与Java相同(传递C ++中的指针而不是传递对象):

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