Модераторы: Poseidon, Snowy, bems, MetalFan

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Скорость вычисления корней квадратного уравнения 
:(
    Опции темы
iLents
Дата 16.5.2008, 16:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

Репутация: нет
Всего: нет
Приветствую !

Вот такой код на 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 работает почти в два раза быстрее.

Комментарии ?
PM MAIL   Вверх
Doga
Дата 18.5.2008, 14:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Шустрый
*


Профиль
Группа: Участник
Сообщений: 115
Регистрация: 20.12.2007
Где: Россия, Обнинск

Репутация: нет
Всего: нет
Привет.

А если скорость измерять с помощью QueryPerformanceFrequency/QueryPerformanceCounter?
PM MAIL WWW   Вверх
iLents
Дата 19.5.2008, 13:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

Репутация: нет
Всего: нет
Ими я и измерял сначала, тот же самый результат

Добавлено @ 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а в два раза быстрее.
Подымите мне веки, в чем порылась собака ?

Это сообщение отредактировал(а) iLents - 19.5.2008, 13:27
PM MAIL   Вверх
Alexeis
Дата 19.5.2008, 13:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 109
Всего: 459
iLents, дампни прогу, нужно взглянуть на асм код иначе трудно сказать чего там плохо.

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


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
iLents
Дата 19.5.2008, 13:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

Репутация: нет
Всего: нет
Ок, сделаю массив 1000x1000

Это сообщение отредактировал(а) iLents - 19.5.2008, 13:56
PM MAIL   Вверх
Alexeis
Дата 19.5.2008, 13:59 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

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


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
iLents
Дата 19.5.2008, 14:10 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

Репутация: нет
Всего: нет
Убрал 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;
    }




Это сообщение отредактировал(а) iLents - 19.5.2008, 14:10
PM MAIL   Вверх
Alexeis
Дата 19.5.2008, 14:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Амеба
Group Icon


Профиль
Группа: Админ
Сообщений: 11743
Регистрация: 12.10.2005
Где: Зеленоград

Репутация: 109
Всего: 459
Цитата(iLents @  19.5.2008,  13:10 Найти цитируемый пост)
джавовский код все равно в два раза быстрее

  На массиве?


--------------------
Vit вечная память.

Обсуждение действий администрации форума производятся только в этом форуме

гениальность идеи состоит в том, что ее невозможно придумать
PM ICQ Skype   Вверх
iLents
Дата 19.5.2008, 20:26 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

Репутация: нет
Всего: нет
Нет, пока просто убрал вычисление корня, ввиду твоего предположения "единственное чего видеться тормозного так это вызов функции sqrt". 
PM MAIL   Вверх
iLents
Дата 19.5.2008, 20:45 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

Репутация: нет
Всего: нет
В яву добавил вычисление с массивами. Т.е. по набору из 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, 20:45
PM MAIL   Вверх
iLents
Дата 19.5.2008, 21:13 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

Репутация: нет
Всего: нет
Попробовал заполнять коэффициенты случайными числами.
Код

 {
            //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"
С этим понятно - стало попадать в ветки, где решений нет, соответственно и вычислений нет ...
PM MAIL   Вверх
Qu1nt
Дата 20.5.2008, 16:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 602
Регистрация: 13.1.2007

Репутация: 18
Всего: 50
Код

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 "убыстрения" (%
PM MAIL   Вверх
iLents
Дата 20.5.2008, 18:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

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

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

Это сообщение отредактировал(а) iLents - 20.5.2008, 18:51
PM MAIL   Вверх
ivan219
Дата 21.5.2008, 10:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1121
Регистрация: 19.11.2005
Где: Планета земля

Репутация: 2
Всего: 12
Ну так создай свой тип:
Код

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;


Это сообщение отредактировал(а) ivan219 - 21.5.2008, 10:24


--------------------
Мой первый сайт и моя первая программа!!!!!
PM MAIL ICQ   Вверх
iLents
Дата 21.5.2008, 12:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 10
Регистрация: 16.5.2008

Репутация: нет
Всего: нет
Проверил. В таком виде с включенной оптимизацией - самый медленный вариант

Это сообщение отредактировал(а) iLents - 21.5.2008, 12:53
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Delphi: Общие вопросы"
SnowyMetalFan
bemsPoseidon
Rrader

Запрещается!

1. Публиковать ссылки на вскрытые компоненты

2. Обсуждать взлом компонентов и делиться вскрытыми компонентами

  • Литературу по Дельфи обсуждаем здесь
  • Действия модераторов можно обсудить здесь
  • С просьбами о написании курсовой, реферата и т.п. обращаться сюда
  • Вопросы по реализации алгоритмов рассматриваются здесь
  • 90% ответов на свои вопросы можно найти в DRKB (Delphi Russian Knowledge Base) - крупнейшем в рунете сборнике материалов по Дельфи

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Snowy, MetalFan, bems, Poseidon, Rrader.
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Delphi: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.1477 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.