Моё меню Общее меню Пользователи Правила форума Все прочитано
Вернуться   uForum.uz > ИКТ и телеком > IT-индустрия > Софт > Программирование
Знаете ли Вы, что ...
...нарушения правил форума наказываются. Старайтесь их не нарушать.
<< Предыдущий совет - Случайный совет - Следующий совет >>

Программирование Обсуждаются вопросы мира программирования. Слово программирование отпугивает некоторых... Не бойтесь, заходите учитесь, помогайте, обучайте...


Ответить

 
Опции темы Опции просмотра
Старый 25.12.2010 18:58   #1  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Нахождение простых чисел. Оптимизация

Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 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 секунды. Результат впечатлил студентов, можно надеяться, что в дальнейшем они будут думать над оптимизацией.

Теперь бы приучить их к красивому коду.
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
Старый 25.12.2010 19:17   #2  
Real ID Group
Аватар для Rooslan Khayrov
Оффлайн
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114  374/183
– 6  9/8

Switzerland
Мне опять непонятны некоторые принятые здесь решения.
Зачем было заводить временный массив результата? Избегать ввода-вывода, перемежающегося вычислениями? А на что это влияет?
Но если уж завели, можно было бы ещё больше ускорить алгоритм очевидным образом.
Ответить 
Старый 25.12.2010 19:33   #3  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
Зачем было заводить временный массив результата? Избегать ввода-вывода, перемежающегося вычислениями? А на что это влияет?
Да, чтобы вывести на экран все результаты сразу, а не постепенно. Сравнивал скорость работы программы, при постепенном выводе, время выполнения примерно на 25% больше.

Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
Но если уж завели, можно было бы ещё больше ускорить алгоритм очевидным образом.
Указатели? Многопоточность?
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)

Последний раз редактировалось German Stimban; 25.12.2010 в 19:35.
Ответить 
Старый 25.12.2010 21:27   #4  
Real ID Group
Аватар для Rooslan Khayrov
Оффлайн
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114  374/183
– 6  9/8

Switzerland
Цитата:
Сообщение от German Stimban Посмотреть сообщение
Указатели? Многопоточность?
Нет, просто перебирать делители только из уже найденных простых чисел.
Цитата:
Сообщение от German Stimban Посмотреть сообщение
Да, чтобы вывести на экран все результаты сразу, а не постепенно. Сравнивал скорость работы программы, при постепенном выводе, время выполнения примерно на 25% больше.
Это уже шаманство. Даже если эффект действительно наблюдался (я, например, воспроизвести его не могу), мог бы ты объяснить студентам, почему так происходит?
Время, разумеется, надо измерять с перенаправлением вывода в /dev/null, потому что иначе мы меряем скорость рисования в эмуляторе терминала.
И ещё: от hardcoded размеров массивов стоит отучать сразу, потому что неверный выбор чреват расстрелом памяти. Надо было либо воспользоваться теоремой о распределении простых чисел, либо сделать массив динамически расширяемым — вручную или, ещё лучше, использовав std::vector.
Ответить 
2 "+" от:
Старый 25.12.2010 21:53   #5  
Real ID Group uParty Member
Аватар для Shuhrat Ismailov
Оффлайн
Сообщений: 3,411
+ 2,928  2,654/1,361
– 84  129/82

UzbekistanОтправить сообщение для Shuhrat Ismailov с помощью Skype™Facebook
Цитата:
Сообщение от German Stimban Посмотреть сообщение
простое число - это число, которое делится только на себя и на единицу.
Оффтоп:
небольшая поправочка.
простое число - это натуральное число, большее единицы, которое делится только на себя и на единицу.
Иначе говоря, простое число́— это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя.
Ответить 
2 "+" от:
Старый 26.12.2010 01:58   #6  
Аватар для Наташа
Оффлайн
Сообщений: 1,306
+ 885  788/480
– 0  51/26

Germany
Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 1 до 100.000, на всякий случай напомнив, что простое число - это число, которое делится только на себя и на единицу. Через некоторое время задание было выполнено. Практически все сделали примерно так:
Мне кажется это простое не знание алгоритмов, возможно их просто не учили этому -есть огромная куча совершенно различных алгоритмов, к которым просто так не приходят с помощью простой "оптимизации" -их над изучать
Например:
PHP код:
List<intGetPrimNumber(int n)//n -число до которого необходимо искать простые числа
        
{
            
//Инициализация
            
bool[] = new bool[n+1];
            
//0 и 1 не простые числа - сразу же исключаем
            
z[0] = true;
            
z[1] = true;
            
double sqrt Math.Sqrt(n);
            
int k 0;
            
int i 2//Первое простое число
            
while (<= sqrt)
            {
                
i;
                while (
k*<= n)
                {
                    
z[k*i] = true;
                    
k++;
                }
                
//Поиск нового простого числа
                
i++;
                while ((
z[i])&&(i<=sqrt))
                {
                    
i++;
                }
            }
            
//Все простые числа вносятся в новый список:
            
List<int= new List<int>();
            for (
int j 0n+1j++)
            {
                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 -все не зачеркнутые числа -простые -называеться алгоритм Решето Эратосфена

Последний раз редактировалось Наташа; 26.12.2010 в 02:20.
Ответить 
Старый 26.12.2010 02:30   #7  
Аватар для Наташа
Оффлайн
Сообщений: 1,306
+ 885  788/480
– 0  51/26

Germany
еще можно решето А́ткина глянуть, это современное оптимизированное Решето Эратосфена -как можно к этому прийти самостоятельно за 2 часа занятий я совершенно себе не представляю...
Ответить 
2 "+" от:
Реклама и уведомления
Старый 27.12.2010 11:30   #8  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
Нет, просто перебирать делители только из уже найденных простых чисел.
Если перерабатывать исходный алгоритм, то это лишь усложнит дело. Цель занятия была не изучение популярных алгоритмов, а оптимизация уже готовых.

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

Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
Время, разумеется, надо измерять с перенаправлением вывода в /dev/null, потому что иначе мы меряем скорость рисования в эмуляторе терминала.
Руслан, так в том-то и дело, чтобы наглядно показать, что вывод данных на экран, запись данных в файл на диске занимают больше времени, чем процессорные операции.

Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
И ещё: от hardcoded размеров массивов стоит отучать сразу, потому что неверный выбор чреват расстрелом памяти.
Это будет в одном из ближайших занятий. Задам свою любимую задачу - вычислить 2^100.000.

Цитата:
Сообщение от Rooslan Khayrov Посмотреть сообщение
либо сделать массив динамически расширяемым — вручную или, ещё лучше, использовав std::vector.
Это ещё не проходили.
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
Старый 27.12.2010 11:33   #9  
Real ID Group Ultimate ex-wild_John
Супермодератор
Аватар для German Stimban
Оффлайн
Центр программистов Bepro
Начальник отдела
Сообщений: 8,039
+ 4,910  6,509/2,845
– 298  135/90

UzbekistanОтправить сообщение для German Stimban с помощью ICQОтправить сообщение для German Stimban с помощью Skype™LiveJournal
Цитата:
Сообщение от Наташа Посмотреть сообщение
Мне кажется это простое не знание алгоритмов, возможно их просто не учили этому -есть огромная куча совершенно различных алгоритмов, к которым просто так не приходят с помощью простой "оптимизации" -их над изучать
Спасибо, буду знать.
__________________
Герман - это не имя, это особое состояние души (Джим Анджер)
Ответить 
"+" от:
Старый 27.12.2010 18:34   #10  
Real ID Group
Аватар для Rooslan Khayrov
Оффлайн
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114  374/183
– 6  9/8

Switzerland
Цитата:
Сообщение от German Stimban Посмотреть сообщение
Цитата:
Даже если эффект действительно наблюдался (я, например, воспроизвести его не могу), мог бы ты объяснить студентам, почему так происходит?
Смог.
И как? Повторюсь, у меня этой разницы не наблюдается, что с выводом всего на экран, что в /dev/null. Вариант с массивом даже чуть-чуть медленнее. Значит какими бы ты соображениями это не объяснил, они недостаточно общие.
Ответить 
Ответить
Опции темы
Опции просмотра




Powered by vBulletin® Version 3.8.5
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Advertisement System V2.5 By Branden
OOO «Единый интегратор UZINFOCOM»


Новые 24 часа Кто на форуме Новички Поиск Кабинет Все прочитано Вверх