性能问题：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而不是listBenchmark和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.
