|
|
Знаете ли Вы, что ... | |
...инструкция по установке аватара описана в Правилах форума. | |
<< Предыдущий совет - Случайный совет - Следующий совет >> |
Программирование Обсуждаются вопросы мира программирования. Слово программирование отпугивает некоторых... Не бойтесь, заходите учитесь, помогайте, обучайте... |
Ответить |
|
Опции темы | Опции просмотра |
25.12.2010 18:58 | #1 | ||
ex-wild_John
Супермодератор |
Сегодня на курсах опять столкнулись с вопросами оптимизации. Обучающаяся группа, которая уже достаточно умело щёлкает алгоритмы полагала, что оптимизация кода не нужна. Ну вот хоть убей не понятно, зачем это надо, если программа и так работает. Для примера задал им задачку найти все простые числа от 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; } Код:
#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; } Теперь бы приучить их к красивому коду.
__________________
Герман - это не имя, это особое состояние души (Джим Анджер) |
||
|
Ответить |
25.12.2010 19:17 | #2 |
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114
374/183
– 6
9/8
|
Мне опять непонятны некоторые принятые здесь решения.
Зачем было заводить временный массив результата? Избегать ввода-вывода, перемежающегося вычислениями? А на что это влияет? Но если уж завели, можно было бы ещё больше ускорить алгоритм очевидным образом. |
|
Ответить |
25.12.2010 19:33 | #3 | |
ex-wild_John
Супермодератор |
Цитата:
Указатели? Многопоточность?
__________________
Герман - это не имя, это особое состояние души (Джим Анджер) Последний раз редактировалось German Stimban; 25.12.2010 в 19:35. |
|
|
Ответить |
25.12.2010 21:27 | #4 | |
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114
374/183
– 6
9/8
|
Нет, просто перебирать делители только из уже найденных простых чисел.
Цитата:
Время, разумеется, надо измерять с перенаправлением вывода в /dev/null, потому что иначе мы меряем скорость рисования в эмуляторе терминала. И ещё: от hardcoded размеров массивов стоит отучать сразу, потому что неверный выбор чреват расстрелом памяти. Надо было либо воспользоваться теоремой о распределении простых чисел, либо сделать массив динамически расширяемым — вручную или, ещё лучше, использовав std::vector. |
|
|
Ответить |
2 "+" от:
|
25.12.2010 21:53 | #5 | |
|
Цитата:
Оффтоп: небольшая поправочка.простое число - это натуральное число, большее единицы, которое делится только на себя и на единицу. Иначе говоря, простое число́— это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. |
|
|
Ответить |
2 "+" от:
|
26.12.2010 01:58 | #6 | |
Сообщений: 1,306
+ 885
788/480
– 0
51/26
|
Цитата:
Например: PHP код:
смысл алгоритма очень прост: ряд чисел 2,3,4,5,6,7,8,9,10...,n сначала находим первое не перечеркнутое число 2 и перечеркиваем все кратные ему числа 2,3, Последний раз редактировалось Наташа; 26.12.2010 в 02:20. |
|
|
Ответить |
4 "+" от:
|
26.12.2010 02:30 | #7 |
Сообщений: 1,306
+ 885
788/480
– 0
51/26
|
еще можно решето А́ткина глянуть, это современное оптимизированное Решето Эратосфена -как можно к этому прийти самостоятельно за 2 часа занятий я совершенно себе не представляю...
|
|
Ответить |
2 "+" от:
|
Реклама и уведомления | |
27.12.2010 11:30 | #8 | ||||
ex-wild_John
Супермодератор |
Цитата:
Цитата:
Цитата:
Цитата:
Это ещё не проходили.
__________________
Герман - это не имя, это особое состояние души (Джим Анджер) |
||||
|
Ответить |
27.12.2010 18:34 | #10 |
Google
software engineer
AKA:Y combinator
Сообщений: 418
+ 114
374/183
– 6
9/8
|
И как? Повторюсь, у меня этой разницы не наблюдается, что с выводом всего на экран, что в /dev/null. Вариант с массивом даже чуть-чуть медленнее. Значит какими бы ты соображениями это не объяснил, они недостаточно общие.
|
|
Ответить |
|