Нахождение простых чисел. Оптимизация

[German Stimban]

Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 1 до 100.000, на всякий случай напомнив, что простое число - это число, которое делится только на себя и на единицу. Через некоторое время задание было выполнено. Практически все сделали примерно так:

#include <iostream>

bool isProst(int testnum)
{
        int counter=0;
        for (int i=1;i<=testnum;i++)
                if (testnum%i==0)
                        counter++;
        return (!(counter>2));
}

int main()
{
        for (int i=1;i<=100000;i++)
                if (isProst(i))
                        std::cout<<i<<"\n";
        return 0;
}

Пропустил через команду time, готовая программа выполняется на III-пентиуме 1 минуту и 32 секунды. Поставили задачу, чтобы программа выполнялась как можно быстрее, с прежним алгоритмом и функционалом, изменили до вида:

#include <iostream>
#include <math.h>

bool isProst(int testnum)
{
        for (int i=3;i<=sqrt(testnum);i+=2)
                if (testnum%i==0)
                        return false;
        return true;
}

int main()
{
        std::cout<<2<<"\n";
        int tmparr[30000];
        int st=0;
        for (int i=3;i<=100000;i++)
                if (isProst(i))
                        tmparr[st++]=i;
        for (int i=0;i<st;i++)
                std::cout<<tmparr[i]<<"\n";
        return 0;
}

Программа выполняется на том же компьютере за 1.24 секунды. Результат впечатлил студентов, можно надеяться, что в дальнейшем они будут думать над оптимизацией.

Теперь бы приучить их к красивому коду.

[Rooslan Khayrov]

Мне опять непонятны некоторые принятые здесь решения.
Зачем было заводить временный массив результата? Избегать ввода-вывода, перемежающегося вычислениями? А на что это влияет?
Но если уж завели, можно было бы ещё больше ускорить алгоритм очевидным образом.

[German Stimban]

Сообщение от Rooslan Khayrov

Зачем было заводить временный массив результата? Избегать ввода-вывода, перемежающегося вычислениями? А на что это влияет?

Да, чтобы вывести на экран все результаты сразу, а не постепенно. Сравнивал скорость работы программы, при постепенном выводе, время выполнения примерно на 25% больше.

Сообщение от Rooslan Khayrov

Но если уж завели, можно было бы ещё больше ускорить алгоритм очевидным образом.

Указатели? Многопоточность?

[Rooslan Khayrov]

Сообщение от German Stimban

Указатели? Многопоточность?

Нет, просто перебирать делители только из уже найденных простых чисел.

Сообщение от German Stimban

Да, чтобы вывести на экран все результаты сразу, а не постепенно. Сравнивал скорость работы программы, при постепенном выводе, время выполнения примерно на 25% больше.

Это уже шаманство. Даже если эффект действительно наблюдался (я, например, воспроизвести его не могу), мог бы ты объяснить студентам, почему так происходит?
Время, разумеется, надо измерять с перенаправлением вывода в /dev/null, потому что иначе мы меряем скорость рисования в эмуляторе терминала.
И ещё: от hardcoded размеров массивов стоит отучать сразу, потому что неверный выбор чреват расстрелом памяти. Надо было либо воспользоваться теоремой о распределении простых чисел, либо сделать массив динамически расширяемым — вручную или, ещё лучше, использовав std::vector.

[Shuhrat Ismailov]

Сообщение от German Stimban

простое число - это число, которое делится только на себя и на единицу.

Оффтоп:

небольшая поправочка.
простое число - это натуральное число, большее единицы, которое делится только на себя и на единицу.
Иначе говоря, простое число́— это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя.

[Наташа]

Сообщение от Rooslan Khayrov

Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 1 до 100.000, на всякий случай напомнив, что простое число - это число, которое делится только на себя и на единицу. Через некоторое время задание было выполнено. Практически все сделали примерно так:

Мне кажется это простое не знание алгоритмов, возможно их просто не учили этому -есть огромная куча совершенно различных алгоритмов, к которым просто так не приходят с помощью простой "оптимизации" -их над изучать
Например:

PHP код:

List<int> GetPrimNumber(int n)//n -число до которого необходимо искать простые числа
        {
            //Инициализация
            bool[] z = new bool[n+1];
            //0 и 1 не простые числа - сразу же исключаем
            z[0] = true;
            z[1] = true;
            double sqrt = Math.Sqrt(n);
            int k = 0;
            int i = 2; //Первое простое число
            while (i <= sqrt)
            {
                k = i;
                while (k*i <= n)
                {
                    z[k*i] = true;
                    k++;
                }
                //Поиск нового простого числа
                i++;
                while ((z[i])&&(i<=sqrt))
                {
                    i++;
                }
            }
            //Все простые числа вносятся в новый список:
            List<int> l = new List<int>();
            for (int j = 0; j < n+1; j++)
            {
                if (!z[j]) l.Add(j);
            }
            return l;//возврат списка с окончательным результатом
        } 


на c# при n=100 000 выполняется уже за 3 миллисекунды

смысл алгоритма очень прост: ряд чисел 2,3,4,5,6,7,8,9,10...,n сначала находим первое не перечеркнутое число 2 и перечеркиваем все кратные ему числа 2,3,4,5,6,7,8,9,10..., ищем следующее не перечеркнутое число -в данном случае 3 и перечеркиваем дополнительно все кратные ему: 2,3,4,5,6,7,8,9,10..., теперь ищем следующее не перечеркнутое ит.д. пока не достигнем числа равного корню из n -все не зачеркнутые числа -простые -называеться алгоритм Решето Эратосфена

[Наташа]

еще можно решето А́ткина глянуть, это современное оптимизированное Решето Эратосфена -как можно к этому прийти самостоятельно за 2 часа занятий я совершенно себе не представляю...

[German Stimban]

Сообщение от Rooslan Khayrov

Нет, просто перебирать делители только из уже найденных простых чисел.

Если перерабатывать исходный алгоритм, то это лишь усложнит дело. Цель занятия была не изучение популярных алгоритмов, а оптимизация уже готовых.

Сообщение от Rooslan Khayrov

Это уже шаманство. Даже если эффект действительно наблюдался (я, например, воспроизвести его не могу), мог бы ты объяснить студентам, почему так происходит?

Смог.

Сообщение от Rooslan Khayrov

Время, разумеется, надо измерять с перенаправлением вывода в /dev/null, потому что иначе мы меряем скорость рисования в эмуляторе терминала.

Руслан, так в том-то и дело, чтобы наглядно показать, что вывод данных на экран, запись данных в файл на диске занимают больше времени, чем процессорные операции.

Сообщение от Rooslan Khayrov

И ещё: от hardcoded размеров массивов стоит отучать сразу, потому что неверный выбор чреват расстрелом памяти.

Это будет в одном из ближайших занятий. Задам свою любимую задачу - вычислить 2^100.000.

Сообщение от Rooslan Khayrov

либо сделать массив динамически расширяемым — вручную или, ещё лучше, использовав std::vector.

Это ещё не проходили.

[German Stimban]

Сообщение от Наташа

Мне кажется это простое не знание алгоритмов, возможно их просто не учили этому -есть огромная куча совершенно различных алгоритмов, к которым просто так не приходят с помощью простой "оптимизации" -их над изучать

Спасибо, буду знать.

[Rooslan Khayrov]

Сообщение от German Stimban

Смог.

И как? Повторюсь, у меня этой разницы не наблюдается, что с выводом всего на экран, что в /dev/null. Вариант с массивом даже чуть-чуть медленнее. Значит какими бы ты соображениями это не объяснил, они недостаточно общие.