nlothik (nlothik) wrote,
nlothik
nlothik

Category:

Си опять не обогнал Джаву

Попробовал снова устроить соревнование двух языков программирования. В качестве подопытного алгоритма в этот раз у нас очень древний (200 лет до нашей эры!) способ нахождения всех простых чисел до некоторого целого числа n, называемый Решето Эратосфена. Берём массив чисел и начинаем вычёркивать составные числа: начиная с 2 и кончая n, вычёркиваем в массиве все числа, являющиеся кратными текущему числу. Например, если надо найти все простые числа до 10, начиная с 2 мы зачеркнём 4, 6, 8. Потом зачеркнём всё кратное 3, т.е. 6, 9. И так далее. В результате останутся только простые числа.

Я знаю, что 6 уже было зачёркнуто как кратное 2. Но вставление лишнего if в самый центр цикла (т.е. в то, что выполняется максимальное количество раз) сильно замедляет работу алгоритма. В машинном времени дешевле поставить 0 в нужном месте в памяти, чем проверять лишний раз.

Сложность алгоритма O(n log(log(n))).

Я находил все простые числа до 200 000 000 (больше не получалось, выскакивало переполнение кучи). После чего распечатывал первые 10 и последние 10. Делал я это во-первых, с целью проверить правильность работы алгоритма, а во-вторых компилятор нынче сильно умный, зараза, пошёл. Он мог увидеть, что у меня все эти данные потом в программе не используются, и тупо пропустить выполнение. Уже видел такое не раз и не два.

[Сишный код]
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{

int limit = 200000000;

static int primes[200000000];

for (int i = 2; i < limit; i++)
{
primes[i] = 1;
}

clock_t startTime = clock();

for (int i = 2; i < limit; i++)
{
if(primes[i] == 1)
{
for (int j = 2; j < (double)limit / i; j++)
{
primes[j * i] = 0;
}

}
}

clock_t endTime = clock();

double elapsed_time = (double)(endTime - startTime) / CLOCKS_PER_SEC;

printf("Elapsed time, seconds: %f\n", elapsed_time);

int maxToPrint = 10;
int printed = 0;

for (int i = 2; i < limit; i++)
{
if (primes[i] == 1)
{
printf("%i\n", i);
printed++;
}

if (printed == maxToPrint)
{
break;
}

}

printed = 0;

for (int i = limit - 1; i > 0; i--)
{
if (primes[i] == 1)
{
printf("%i\n", i);
printed++;
}

if (printed == maxToPrint)
{
break;
}
}

}


[Джавовский код]
public class primes
{

public static void main(String[] args)
{

int limit = 200000000;

int primes[] = new int[200000000];

for (int i = 2; i < limit; i++)
{
primes[i] = 1;
}

//init done
long startTime = System.nanoTime();

for (int i = 2; i < limit; i++)
{
if(primes[i] == 1)
{
for (int j = 2; j < (double)limit / i; j++)
{
primes[j * i] = 0;
}

}
}

long endTime = System.nanoTime();
System.out.println("Elapsed time, seconds: " + (endTime - startTime) / 1000000000.0);

int maxToPrint = 10;
int printed = 0;

for (int i = 2; i < limit; i++)
{
if (primes[i] == 1)
{
System.out.println(i);
printed++;
}

if (printed == maxToPrint)
{
break;
}

}

printed = 0;

for (int i = limit - 1; i > 0; i--)
{
if (primes[i] == 1)
{
System.out.println(i);
printed++;
}

if (printed == maxToPrint)
{
break;
}
}

}

}


А теперь -- результаты.

Под виртуалкой Ubuntu Сишная версия слегка выигрывала, выполняясь в среднем за 6.51 секунд против 6.71 секунд у Джава-варианта.
Под баш-оболочкой в Windows 10 с большим отрывом выиграла уже Джава, выполняясь за 4.75 секунд вместо 6.4 у Сишной версии.
И, наконец, я скомпилировал Сишный код под Windows, поставив дистрибутив LLVM (clang), и запустил всё просто в командной строке. Скорость выполнения обоих программ оказалась одинаковой -- от 4.69 до 4.75 секунд для обоих вариантов, разница, если она и была, составляла какие-то доли процента -- статистически незначимо.

Си компилировал везде clang со степенью оптимизации 3. В этот раз gcc показал себя не так сильно отстающим от clang (но всё же отстающим), как в прошлый раз. Java -- JDK 9, экспорт в jar из Eclipse.

Итого! Как мы видим, скорость выполнения данных программ больше зависит от того, где и как программа запускается, чем от языка программирования.

Засим -- извольте откланяться, на тему "Си быстрее Джавы" я могу предъявить уже два теста, где Си нихера не быстрее Джавы. Если кто-то продолжит упорствовать, пусть пишет свои тесты, выкладывает код в открытый доступ, чтобы можно было устроить независимую перепроверку. А я -- за то, чтобы брать ПРАВИЛЬНЫЙ инструмент под задачу, а не размахивать флагом "Лучший язык программирования -- Паскаль". Драйверы низкоуровневые или там ядро ОС -- пишите на голых Сях. А крупный корпоративный проект на них вы писать УСРЁТЕСЬ, а на Джаве -- нормально. Что лучше -- молоток или пила? Отвёртка или кувалда? Да ни то ни другое. Они разные и для разного.
Tags: #include, на вентилятор, программирование
Subscribe

Recent Posts from This Journal

  • Про затмение

    Затмение, конечно, прошло мимо нас, да и “не очень-то и хотелось”, так как оно было не полное, как в 17м году, а кольцевое. В сети…

  • Они хакнули физику

    Как известно, парусная лодка может идти быстрее ветра. Но с оговоркой — если ветер сбоку. Тогда парус работает не за счёт сопротивления, а за…

  • Жулики на Амазоне

    Недобросовестное жульё, оказывается, есть и у Безоса. Под видом настоящей камеры Хиквижен мне продали какую-то подделку. Вотжеж. Хорошо, что…

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 12 comments

Recent Posts from This Journal

  • Про затмение

    Затмение, конечно, прошло мимо нас, да и “не очень-то и хотелось”, так как оно было не полное, как в 17м году, а кольцевое. В сети…

  • Они хакнули физику

    Как известно, парусная лодка может идти быстрее ветра. Но с оговоркой — если ветер сбоку. Тогда парус работает не за счёт сопротивления, а за…

  • Жулики на Амазоне

    Недобросовестное жульё, оказывается, есть и у Безоса. Под видом настоящей камеры Хиквижен мне продали какую-то подделку. Вотжеж. Хорошо, что…