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

Ответ 1

std::list в С++ - это связанный список, тогда как java.util.ArrayList - это массив. Попробуйте заменить std::list на std::vector. Кроме того, обязательно скомпилируйте с включенной оптимизацией.

Ответ 2

Обновление:

Изменения в С++

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

Изменения в Java

• Как написано 3459 миллисекунд
• Изменения verifierNonPrise раннее возвращение
  368 миллисекунд

Java Vs С++

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

Ответ 3

Проверьте эту версию, обновленную с использованием возможностей С++ 11. Протестировано в GCC 4.9.0 с -std=c++11. Протестировано на Celeron 1.6 GHz, 512 MB RAM.

Время на моем ПК:
Оригинал: Продолжительность (миллисекунды): 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;
}

Ответ 4

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

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

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

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

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

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

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

Ответ 5

Я, возможно, избиваю мертвую лошадь здесь, но просто выполняя линейный перевод Java на С++, даже не используя опорные параметры const или любую такую ​​вещь, вы можете видеть, что С++ почти в два раза быстрее, чем 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 << "(" << p.x << "; " << p.y << ")" << endl;
    }

    return 0;
}

Ответ 6

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

Вы должны повысить производительность, если не хотите вызывать вызов библиотеки абс. абс. с плавающей запятой в вашем С++

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

Ответ 7

С++ может сделать это за 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";
}

Ответ 8

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

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

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