Сравнение скорости языков. Неужели Pascal самый быстрый?

Question

Всем привет! Решая очередную задачу из ЕГЭ наткнулся на задание:

Найдите все натуральные числа, принадлежащие отрезку [106 000 000; 107 000 000], у которых ровно три различных чётных делителя. В ответе перечислите найденные числа в порядке возрастания.

Написал решение на Python:

for number in range(106000000 ,107000000 + 1):
    countDel = 0
    if number % 2 == 1:
        continue
    for j in range(1, round(number ** 0.5) + 1):
        if number % j == 0:
            if j % 2 == 0:
                countDel += 1
            if number // j % 2 == 0:
                countDel += 1
            if number == j * j:
                countDel -= 1
        if countDel > 3:
            break
    if countDel == 3:
        print(number)

Работает достаточно медленно, как и ожидалось, и у меня возникла замечательная идея написать на более быстром языке и выбрал С++ (Visual Studio) Написал код:

#include <cmath>
int main()
{   
    for (int number = 106000000; number < 107000001; number++) {
        int countDel = 0;
        if (number % 2 == 1) continue;
        for (int j = 1; j <= round(sqrt(number)); j++)
        {
            if (number % j == 0) {
                if (j % 2 == 0) countDel ++;
                if (number / j % 2 == 0) countDel ++;
                if (number == j * j) countDel--;
            }
            if (countDel > 3) break;
        }
        if (countDel == 3) { 
            std::cout << number << std::endl;
        }
   }
}

Отлично, работает быстрее, однако решил проверить задание из примера и удивился, что код на Pascal`е, по сути идентичный, работает в 2 раза быстрее:

var 
    count, i, j: longint;
    sqrtI: real;
begin
    for i := 106000000 to 107000000 do begin
        count := 1;
        if i mod 2 = 0 then begin
            for j := 2 to round(sqrt(i)) do begin
                if i mod j = 0 then
                    if j mod 2 = 0 then count := count + 1;
                if i mod j = 0 then
                    if (i div j) mod 2 = 0 then count := count + 1;
                if (j * j = i) and (j mod 2 = 0) then count := count - 1;
                if count > 3 then break;
            end;
        end;
        if count = 3 then writeln(i);
        count := 1;
    end;
end.

Получается, что Pascal самый быстрый язык программирования и всё это время нам врали?

Answer 1

for j := 2 to round(sqrt(i)) do begin

Паскаль оценивает предел цикла внутреннего цикла for (где используется медленная вещественная операция sqrt) только один раз перед каждым запуском этого цикла.

Как дело обстоит с С++ - вероятно, зависит от оптимизатора.

В целом же обычно компиляторы C++ выдают код лучшего качества.

Есть ещё важный вопрос - как Вы измеряли? Какова точность?

Сделал тест. На 3.1 ГГц процессоре поколения Haswell (Xeon 1220v3, примерно как i5 4440) Delphi выдаёт 1.4 с.

C++ VS 2017 (стоит максимальная оптимизация -O2, как -O3 включить в среде - я не знаю) тратит 5.7 с. Если заменить предполагаемую зловредную строку на одноразовое вычисление

    int s = round(sqrt(number));
    for (int j = 1; j <= s; j++)

то время становится 1.2 с, что вполне согласуется с обычным соотношением скорости генерируемого кода на простых примерах (при возможности векторизации и т.п. компиляторы C++ дадут жару).

Судя по тесту Stanislav Volodarskiy, gcc c -O3 догадывается, как лучше оптимизировать.

Answer 2

Если правильно написать - быстрее С++ не получится :)

Если подумать - то это числа вида 2*p*p, где p - простое число. Так что...

#include <iostream>
#include <cmath>

bool is_prime(unsigned long x)
{
    unsigned long n = sqrt(x);
    if (x%2 == 0) return false;
    for(unsigned long  i = 3; i <= n; i+=2)
    {
        if (x%i == 0)
        {
            return false;
        }
    }
    return true;
}


int main()
{
    for(int n = sqrt(106000000/2)-1; n < sqrt(107000001/2)+1; n++)
    {
        if (is_prime(n))
        {
            int m = n*n*2;
            if (m <= 107000001 && m >= 106000000) std::cout << m << "\n";
        }
    }
}

Время просто не фиксируется :) - https://ideone.com/FBKkw8

Ну, а по вашему вопросу Pascal vs С++ - надо сравнивать не абстрактные шарообразные компиляторы в вакууме, а конкретные компиляторы, с указанием настроек оптимизации и многого другого. Думаю, что по скорости они как минимум сравнимы, и различие в 2 раза - не внутренне присущее Pascal, а конкретные настройки конкретного компилятора...

Увы, Pascal на машине не держу, так что поработать с вашими кодами не могу, это так, просто теоретические рассуждения.

Answer 3

Мне стало любопытно сравнить С++ и Pascal.

Платформа Linux Ubuntu, 64-bit. Компиляторы:

Free Pascal Compiler version 3.0.0+dfsg-2 [2016/01/28] for x86_64
gcc version 9.3.0 (Ubuntu 9.3.0-23ubuntu1~16.04)

Командные строки:

fpc -O4 pascal.pas
g++ -O3 -std=c++11 -pedantic -Wall -Wextra -Werror cpp.cpp

Результаты прогона:

$ time ./pascal
106084178
106492418
106784498
106842962

real    0m7.114s
user    0m7.112s
sys 0m0.004s

$ time ./a.out
106084178
106492418
106784498
106842962

real    0m1.179s
user    0m1.176s
sys 0m0.000s

Чуда не произошло: С++ компилятор в данном конкретном случае выдает в шесть раз более быстрый код.

P.S. Разница велика. Я проверил различные оптимизации доступные на платформах. GCC без оптимизаций замедляется в четыре раза, FPC во всех вариантах -Cf??? -Op??? показывает одно время - разница не более десяти процентов.

P.P.S. Я буду благодарен если вы укажите мне мои промахи. Возможно, я не умею использовать FPC.

БЛОГ НА HUSL

Сравнение скорости языков. Неужели Pascal самый быстрый?

Ответы (3 шт):