java - 性能问题 : Java vs C++

Question

我一直听说 C++ 比 Java 更高效(这就是为什么大多数游戏都是用 C++ 开发的)。

我写了一个小算法来解决 Java 和 C++ 中的“八皇后谜题”，使用完全相同的算法，然后开始提高数字或平方。 当达到 20*20 甚至 22*22 的棋盘格时，Java 似乎更有效(3 秒对 C++ 的 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;
}

Answer 1

std::list 在 C++ 中是一个链表，而 java.util.ArrayList 是一个数组。尝试用 std::vector 替换 std::list。另外，请务必在打开优化的情况下进行编译。