Проблема производительности: Java vs C++

обновления:

изменения в C++

• как написано:
  Ошибка Компиляции
• заменить математику.h = > cmath
  27610 мсек
• добавить-O3 флаг
  4416 мсек
• заменить std:: list на std:: vector
  2294 мсек
• заменить точку на std:: pair
  2384 мсек
• сделано verifierNonPrise const правильно
  Две тысячи триста пятьдесят один миллисекунды
• заменен цикл в verifierNonPrise с std::find_if
  929 МС
• замена double на int (чтобы сделать его равным Java)
  549 МС

изменения в Java

• как писала
  3459 мсек
• изменения verifierNonPrise досрочное возвращение
  368 МС

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

Окончательный Код:

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

протестируйте эту версию, обновленную с помощью функций C++11. Испытания в GCC 4.9.0 с -std=c++11. Протестировано на Celeron 1.6 ГГц, 512 МБ оперативной памяти.

раз в моем ПК:
Оригинал:длительность (миллисекунды): 12658
Первая Версия:продолжительность (миллисекунды): 3616
Оптимизированная Версия:продолжительность (миллисекунды): 1745

изменения:

• используя vector вместо list Benchmark и слова от Страуструпа.
• используя 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_if для поиска ферзя.

источник (некоторые рекомендации обновлено):

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

сравнение управляемого, динамически компилируемого языка, такого как Java, со статически компилируемым языком, таким как C++, очень сложно.

вы всегда будете сравнивать яблоки с апельсинами в каком-то смысле, потому что они концептуально очень разные. Он начинается с использования стандартных библиотек (ArrayList vs std::list/vector), которые будут иметь потенциально дико разные характеристики производительности, даже ваш код выглядит одинаково на обоих языках.

тогда есть неотъемлемая проблема с microbenchmarks в Java (короткий тест в Java всегда медленнее, потому что JIT будет наблюдать за потоком программы, прежде чем он решит, что и как он должен быть скомпилирован). То же самое касается параметров компилятора для C++, даже структура исходного кода (независимо скомпилированные и связанные классы по сравнению с одним исходным файлом) может иметь существенное значение (поскольку он изменяет объем "понимания" компилятора C++ в другой учебные занятия.)

Далее идет общая разница в управлении памятью, сборке мусора и ручном управлении памятью (умные указатели и т. д. по-прежнему считается ручное управление памятью).

Не говоря уже об общих языковых различиях, таких как вам нужно явно объявить метод virtual в C++, а в Java каждый метод члена является виртуальным по умолчанию (разработка, если он действительно виртуальный во время выполнения остается на виртуальной машине).

со всеми этими есть различия всегда будут случаи, когда один язык будет иметь огромное преимущество над другими. Простой тест с очень ограниченным объемом (как ваш тест здесь) говорит очень мало о каждом языке в целом.

еще один момент, который люди часто склонны игнорировать: насколько продуктивным вы можете быть с языком-скорость не все (посмотрите, насколько успешны скриптовые языки в некоторых областях, несмотря на то, что они вряд ли конкурентоспособны при поиске только при скорости возбуждения). Отсутствие производительность можете некстати, но так может быть низкая производительность.

Я могу бить мертвую лошадь здесь, но просто делать построчный перевод 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 $

Королева.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;
    }
}

Королева.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++ может сделать это за 21 МС (на старом ядре i7-860), если вы используете битовые карты. Для запуска времени я прокомментировал вызов showSoln (), так как графический дисплей шахматной доски занимает в два раза больше времени, чем поиск решения.

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

кроме того, нет причин использовать типы float/doouble для координат.

вы должны получить производительность, если вы не заставляете вызывать вызов библиотеки abs с плавающей точкой в вашем C++

Java сохраняет координаты точки как целое. Функции get возвращают double, однако это, вероятно, легче оптимизировать в Java, а затем в c++.

похоже, что для кода, который требует не слишком большого доступа к памяти и интенсивных вычислений разница между Java и C++ невелика. Но в противоположной ситуации разница выглядит потрясающе :

Java передает объекты методам как ссылки, и эти ссылки передаются по значению, но C++ передает объекты по значению.

вы должны изменить код C++, чтобы сделать его таким же, как Java (Pass указатели в C++ intstead передаваемых объектов):

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