Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Delphi: Общие вопросы > Скорость вычисления корней квадратного уравнения


Автор: iLents 16.5.2008, 16:58
Приветствую !

Вот такой код на Delphi7 ( вычисление корней квадратного уравнения )

Код

function Quadratic(const a:double; const b:double; const c:double; var x0, x1: double):integer;
var
t, d: double;
px0:PDouble;
x2:PDouble;
begin
        (* degenerated cases *)
        if a = 0. then begin
            if b = 0. then begin
                if c = 0. then begin
                    Result := -3; Exit;
                end;
                Result := -2; Exit;
            end;
            x0 := -c / b;
            Result := -1;
            Exit;
        end;
        (* the main case *)
        d := b * b - 4. * a * c; // the discriminant
        ///* one distinct root */
        if d = 0. then begin
            x1 := -b / (2. * a);
            x0 := x1;
            Result := 1;
            Exit;
        end;
        (*
         * conjugate complex roots - if u need it. Otherwise change this part
         *)
        if d < 0. then begin
            t := 0.5 / a;
            x0 := -b * t;
            x1 := sqrt(-d) * t;
            Result := 0;
            Exit;
        end;
        ///* 2 real roots: avoid subtraction of 2 close numbers */
        if b >= 0. then begin
            d := (-0.5) * (b + sqrt(d));
        end else begin
            d := (-0.5) * (b - sqrt(d));
        end;
        x0 := d / a;
        x1 := c / d;
        Result := 2;
        Exit;
end;



procedure TForm3.Button7Click(Sender: TObject);
var
i, j: integer;
//x:array[0..1] of double;
x0, x1: double;
start: dword;
begin
  start := GetTickCount();
  for i := 0 to 2000000 do begin
    Quadratic(1, 4, 3, x0, x1);
  end;
  ShowMessage(IntToStr(GetTickCount - start));

end;



исполняется 250 ms

Вот такой код на Java 1.5 ( Windows XP )

Код

    /*
     * Quadratic equation solution. Real coefficients case.
     * 
     * int Quadratic(double *x,double a,double b,double c); Parameters: x -
     * solution array (size 2). On output: 2 real roots -> then x is filled with
     * them; 2 complex-conjugate roots -> x[0] is real part, x[1] is
     * non-negative imaginary part. other cases -> x[0] unique valid root if
     * (-1) returned, no valid roots otherwise. a, b, c - coefficients: ax^2 +
     * bx + c = 0. Returns: 2 - 2 real and distince roots; 1 - 1 real distinct
     * root (x[0]=x[1]); 0 - 2 complex roots; -1 - one real root in case a==0;
     * -2 - no roots in case a=0, b=0; -3 - infinite number of roots (a=b=c=0).
     */

    int Quadratic(double x[], double a, double b, double c) {
        double d;
        /* degenerated cases */
        if (a == 0.) {
            if (b == 0.) {
                if (c == 0.)
                    return (-3);
                return (-2);
            }
            x[0] = -c / b;
            return (-1);
        }
        /* the main case */
        d = b * b - 4. * a * c; /* the discriminant */
        /* one distinct root */
        if (d == 0.) {
            x[0] = x[1] = -b / (2. * a);
            return (1);
        }
        /*
         * conjugate complex roots - if u need it. Otherwise change this part
         */
        if (d < 0.) {
            double t = 0.5 / a;
            x[0] = -b * t;
            x[1] = Math.sqrt(-d) * t;
            return (0);
        }
        /* 2 real roots: avoid subtraction of 2 close numbers */
        if (b >= 0.)
            d = (-0.5) * (b + Math.sqrt(d));
        else
            d = (-0.5) * (b - Math.sqrt(d));
        x[0] = d / a;
        x[1] = c / d;
        return (2);
    }

    public void testSpeed() {
        double x[] = new double[2];

        long start = System.currentTimeMillis();
        for (int i = 0; i < 2000000; i++) {
            Quadratic(x, 1, 4, 3);
        }
        trace(System.currentTimeMillis() - start);

    }




исполняется 150 ms

Т.е. Java работает почти в два раза быстрее.

Комментарии ?

Автор: Doga 18.5.2008, 14:43
Привет.

А если скорость измерять с помощью QueryPerformanceFrequency/QueryPerformanceCounter?

Автор: iLents 19.5.2008, 13:12
Ими я и измерял сначала, тот же самый результат

Добавлено @ 13:18
Решил упростить задачу, уж больно код сложный был. Вообще ничего не понимаю теперь.

Код

function PrimitiveQuadratic(const a:double; const b:double; const c:double; var x0, x1: double): integer;
var
d: double;
begin
    d := b * b - 4. * a * c;
    d := (-0.5) * (b + sqrt(d));
    x0 := d / a;
    x1 := c / d;
    Result := 2;
end;


Код

    int PrimitiveQuadratic(double x[], double a, double b, double c) {
        double d = b * b - 4. * a * c;
        d = (-0.5) * (b + Math.sqrt(d));
        x[0] = d / a;
        x[1] = c / d;
        return 2;
    }


Так вот, на Java стало быстрее ( чего и следовало ожидать, число проверок-то уменьшилось ), а на Delphi - стало медленнее !

Delphi 2 млн итераций выполняет за 290 ms, Java за 140 ms. Т.е. на этом примере Javа в два раза быстрее.
Подымите мне веки, в чем порылась собака ?

Автор: Alexeis 19.5.2008, 13:45
iLents, дампни прогу, нужно взглянуть на асм код иначе трудно сказать чего там плохо.

Добавлено через 4 минуты и 57 секунд
  При таких условиях повторения компилятор мог заменить передачу параметров на явную подстановку чисел и даже кой чего вычислить заранее. Попробуй сгенерить большой массив чисел на 2000000 и передавать в функцию элементы этого массива, тогда компилятор не сможет ничего просчитать заранее.

Автор: iLents 19.5.2008, 13:54
Ок, сделаю массив 1000x1000

Автор: Alexeis 19.5.2008, 13:59
Вообще-то оптимизатор у делфей паршивенький, но лишего делать не станет. Поглядел на асмовский код, единственное чего видеться тормозного так это вызов функции sqrt, вызов можно было вполне заменить на инлайн вствку, тем более что функция небольшая.

Автор: iLents 19.5.2008, 14:10
Убрал sqrt

Код

function Stupid(const a:double; const b:double; const c:double; var x0, x1: double): integer;
var
d: double;
begin
    d := b * b - 4. * a * c;
    d := (-0.5) * (b + d);
    x0 := d / a;
    x1 := c / d;
    Result := 2;
end;


джавовский код все равно в два раза быстрее

Код

    int Stupid(double x[], double a, double b, double c) {
        double d = b * b - 4. * a * c;
        d = (-0.5) * (b + d);
        x[0] = d / a;
        x[1] = c / d;
        return 2;
    }



Автор: Alexeis 19.5.2008, 14:36
Цитата(iLents @  19.5.2008,  13:10 Найти цитируемый пост)
джавовский код все равно в два раза быстрее

  На массиве?

Автор: iLents 19.5.2008, 20:26
Нет, пока просто убрал вычисление корня, ввиду твоего предположения "единственное чего видеться тормозного так это вызов функции sqrt". 

Автор: iLents 19.5.2008, 20:45
В яву добавил вычисление с массивами. Т.е. по набору из 10000*3 коэфифциентов вычисляется 10000*2 корней и так до общего числа итераций 2000000.

Код

            int arrSize = 10000;
            double coeffs[][] = new double[arrSize][3];
            for(int i=0;i<arrSize;i++){
                coeffs[i][0] = 1;
                coeffs[i][1] = 4;
                coeffs[i][2] = 3;
            }
            double xx[][] = new double[arrSize][2];
            int cnt = 0;
            long start = System.currentTimeMillis();
            for(int i=0;i<2000000/arrSize;i++){
                for(int j=0;j<arrSize;j++){
                    cnt++;
                    Quadratic(xx[j], coeffs[j][0], coeffs[j][1], coeffs[j][2]);                    
                }
            }
            trace("Quadratic arrays:("+cnt+") " + ( System.currentTimeMillis() - start ));


Вывод на консоль: Quadratic arrays:(2000000) 188.
Т.е. даже с заполнением массивов в яве существенно быстрее, чем в Delphi без массивов.

Автор: iLents 19.5.2008, 21:13
Попробовал заполнять коэффициенты случайными числами.
Код

 {
            //Quadratic arrays
            Random rand = new Random();
            int arrSize = 10000;
            double coeffs[][] = new double[arrSize][3];
            for(int i=0;i<arrSize;i++){
                coeffs[i][0] = rand.nextDouble();
                coeffs[i][1] = rand.nextDouble();
                coeffs[i][2] = rand.nextDouble();
            }
            double xx[][] = new double[arrSize][2];
            int cnt = 0;
            long start = System.currentTimeMillis();
            for(int i=0;i<2000000/arrSize;i++){
                for(int j=0;j<arrSize;j++){
                    cnt++;
                    Quadratic(xx[j], coeffs[j][0], coeffs[j][1], coeffs[j][2]);                    
                }
            }
            trace("Quadratic arrays:("+cnt+") " + ( System.currentTimeMillis() - start ));            
        }


Пустой номер, только еще быстрее стало: "Quadratic arrays:(2000000) 156"
С этим понятно - стало попадать в ветки, где решений нет, соответственно и вычислений нет ...

Автор: Qu1nt 20.5.2008, 16:58
Код

function Quadratic(const a:double; const b:double; const c:double; var x0, x1: double):integer;

замени на это:
Код

function Quadratic(a, b, c, x0, x1: Double): Integer;

Получишь ~60 ms "убыстрения" (%

Автор: iLents 20.5.2008, 18:49
Действительно, существенный выигрыш, более 100 ms. Однако - корни уравнений надо передавать как variable, они ж назад должны возвращаться.

Компилятор, кстати, начинает ругаться, мол, value assigned to %s never used.  Вот и оптимизирует их, видать.

Автор: ivan219 21.5.2008, 10:18
Ну так создай свой тип:
Код

type TSqrt = record
                     X1: Double;
                     X2: Double;
                     D: Integer; // Число корней
        end; 
.
.
function Quadratic(A, B, C: Double): TSqrt;
begin
.
.
.
Result.X1 := X1;
Result.X2 := X2;
Result.D := D;
end;

Автор: iLents 21.5.2008, 12:52
Проверил. В таком виде с включенной оптимизацией - самый медленный вариант

Автор: iLents 21.5.2008, 13:09
Хм, почитал тут как все в Яве происходит, там сейчам полноценные компиляторы, т.е. два раза компилируется - сначала из исходного кода в байт-код, затем, уже в процессе исполнения, по байт-коду генерируется машинный код.

Напоследок такой тест сделал, на манагер памяти. Возвращаю класс

Код

type TSqrtCls = class
public
  x0: Double;
  x1: Double;
  D: Integer;
end;

function QuadraticTSqrtCls(const a:double; const b:double; const c:double):TSqrtCls;
var
t, d: double;
begin
  Result := TSqrtCls.create;
        (* degenerated cases *)
        if a = 0. then begin
            if b = 0. then begin
                if c = 0. then begin
                    Result.D := -3; Exit;
                end;
                Result.D := -2; Exit;
            end;
...


Освобождения памяти в тесте нет, т.е. тест идет с утечкой памяти. Аналогично в Java:

Код

    SqrtCls QuadraticSqrtCls(double a, double b, double c) {
        SqrtCls res = new SqrtCls();
        double d;
        /* degenerated cases */
        if (a == 0.) {
            if (b == 0.) {
                if (c == 0.){
                    res.D = -3;
                    return res;



Java - 281 ms, Delphi - 875 ms

Автор: Alexeis 21.5.2008, 14:23
iLents, попробуй протестировать на чем нибудь действительно сложном, так чтобы потери на всякие вызовы функций, передачи аргументов и инициализации не влияли на подсчет времени. Например посчитай фурье на 1048576 точек, передай файл случайных чисел. 
  Т.е. чтобы была всего одна итерация.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)