Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Задача простая - написать на фоксе программу, которая вычисляет 10000-ое простое число (первым считать 2). Конечно, нужно постараться, чтобы она работала как можно быстрее.
|
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Меня снова терзают смутные сомнения и странное чувство дежа-вю
Но я никак не могу найти поиском где это всё дело происходило (возможно не на фоксклубе) - при том, судя по дате файлов, было это в 2004 году... По скорости лучший алгоритм для 10000-го числа (это кстати 104729) опережает банальный перебор в 6 раз (0.25 секунды против 1.5 секунд) для 100000-го числа (а это 1299709) разница увеличивается до 13 раз (3.4 секунды против 45.6) Вот аглоритм перебора (он конечно же не то чтобы совсем уж "полный" - т.е. там таки есть один махонький элемент оптимизации, но скажем так - это не самый оптимальный алгоритм) - да и как эталон для сравнения/тестирования других алгоритмов его можно использовать. Кроме того, можно с его помошью грубо так сравнивать производительность машин - дабы верхние цифры скорости не выглядели совсем уж отфонарными. Т.е. принять его производительность за скажем 100 попугаев и от этого плясать в поиске лучшего (не заморачиваясь слишком уж на разницу в железе).
P.S. Очень надеюсь что не требуется найти алгоритм пригодный для поиска абсолютно произвольных простых чисел - т.к. очевидно то что хорошо для 1000-100000 числа будет вряд-ли подходяще для миллионно-миллиардных Да и фокс там уж 100% начнёт загибаться - и по точности, и по объёму памяти. P.P.S. Естественно я не буду пока выкладывать оптимальный алгоритм, т.к. это будет нечестно - я его не сейчас придумывал, а 6 лет назад Подождём, посмотрим что народ скажет... ------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Влад Колосов Сообщений: 22664 Откуда: Ростов-на-Дону Дата регистрации: 05.05.2005 |
Смысла перебирать четные числа по алгоритму простого перебора нет, т.е. от тройки STEP 2.
------------------ Совершенство - это не тогда, когда нельзя ничего прибавить, а тогда, когда нечего убавить. |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Для определения простоты m достаточно проверить его делимость на все простые n, такие что n*n не больше m. В данном случае этот алгоритм будет по-видимому оптимальным по скорости, но не по размеру (нужен массив для хранения найденных простых чисел). Различные вероятностные и детерминированные тесты простоты числа вряд ли будут быстрее непосредственной проверки делением, ввиду небольших m.
Исправлено 1 раз(а). Последнее : medstrax, 14.04.10 11:56 |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Также нет смысла проверять числа, заканчивающиеся на 5. Надо проверять только числа с последней цифрой 1,3,7 или 9. |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
Совершенно верно. Побочный выход такого алгоритма - не только искомое N-е простое число, но и все предыдущие... Есть одно НО - для указанного диапазона это НЕ самый быстрый алгоритм (по крайней мере в фоксовой реализации). У меня он идёт как V2 и требует примерно 61 попугая, тогда как мой V1 требует всего 16.5 попугаев Напоминаю что "эталонный вариант это 100 попугаев. Ну если ты знаешь простой цикл способный выдавать все нечётные числа КРОМЕ заканчивающихся на 5 - то велкам в тесты А так, эта проверка (делимость на 5 внутри цикла с шагом 2) ничем не отличается от проверки на деломость на любое другое число (например на 3 или на 7 или на чёртову дюжину в конце концов) - т.е. выигрыша в таком "хардкодинге" нет никакого. 2 ВладБанальная замена в эталонном варианте lnCurValue = m.lnCurValue + 1 на lnCurValue = m.lnCurValue + 2 даёт в итоге результат в 92 попугая - не шибко густо (и уж ни о каком выигрыше в 2 раза речь точно не идёт, как некоторые могут подумать) - по сути мы заменяем всего 1 (причём самую первую) проверку на %2=0 (я кстати не в курсе насколько быстро фокс такое делает - на ассемблере это был бы трививальный тест младшего разряда, для целых чисел конечно же, что занимает настолько мизерное время, что "обход" такового может оказаться даже проигрышнее) из многих сотен таких проверок для "среднего" проверяемого числа. При этом вообще-то "цикл" в смысле FOR не совсем подходит для этой задачи (т.к. можно лишь очень примерно оценить "до скольких" требуется гнать цикл) - мне кажется более логичным DO WHILE с выходом по нахождению (хотя это очень любопытный вопрос - что в фоксе быстрее - FOR с EXIT или DO WHILE с EXIT и наращиванием переменной внутри). В общем поиск можно продолжать - пока не указана не то что реализация, а даже сам подход, который у меня в v1 даёт лучший резальтат. ------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Crispy Сообщений: 18571 Дата регистрации: 16.05.2005 |
Ну почему же. На 5-то как раз и отличается:
Строчные функции вообще облегчают жизнь на фоксе своей большей проработанностью в смысле функциональности, чем на многих других языках. ------------------ В действительности все иначе, чем на самом деле. (Антуан де Сент-Экзюпери) |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ssa Сообщений: 12999 Откуда: Москва Дата регистрации: 23.03.2005 |
Ну обясните же мне наконец дя чего здесь IIF? Без масла масляного жизнь не мила? ------------------ Лень - это неосознанная мудрость. |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Crispy Сообщений: 18571 Дата регистрации: 16.05.2005 |
Для наглядности аргумента. В цикле же понятно всегда лучше воспользоваться, чем окажется удобнее в данном месте. То ли это окажется IIF, то ли IF с дальнейшим EXIT или LOOP. ------------------ В действительности все иначе, чем на самом деле. (Антуан де Сент-Экзюпери) |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Это не катит. Процессор гораздо больше времени потратит на преобразование числа в строку(десятки если не сотни инструкций), нежели на простое деление на 5 (одна инструкция, правда весьма не быстрая) Исправлено 1 раз(а). Последнее : medstrax, 14.04.10 21:04 |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Игорь, я когда открывал тему, как раз и хотел подчеркнуть (в заголовке), что оптимизация кода на фоксе отличается от оптимизации вообще. Насчет твоего приведенного кода, я сам поленился его написать, а навскидку думал, что он будет работать заметно дольше. Кстати, его все-таки можно ускорить в два раза "легким движением руки". Для этого нужно не только заменить строчку
на
но еще и
на
А сам я пробовал много разных вариантов фоксовской оптимизации. Но пока лучший результат - 40 попугаев. Правда при этом в курсоре получаются все простые числа. Исправлено 1 раз(а). Последнее : leonid, 14.04.10 23:22 |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Я тоже примерно так начинал оптимизировать:
По идее, для ускорения можно было бы делать проверку деления не на все нечетные числа, а только на простые (тоже до Int(Sqrt(m.lnCurValue))). Но для этого необходимо хранить результаты предыдущих вычислений. А вот тут начинаются проблемы: варианты и с массивом, и с курсором у меня получаются примерно в 20 раз медленнее полного перебора... |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
В коде есть ошибки - ну точнее нужно выход прописать (а то наращивает после нахождения) и сам подсчёт "порядкового номера числа" сбился на 1-цу - т.к. в таком виде он выдаёт на выходе 104727 которое никак не простое (а "находит" до "порчи" на самом деле он 9999-е простое число 104723) Очень странно - у меня варианты с массивами (вплоть до очень больших размеров) очень быстры. Может что-то не то накодил А вот варианты с курсором я думаю и должны быть медленнее... ------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
2 leonid
Ну да, не докрутил я игнорирование чётных до конца так оно реально даёт 49 попугаев... Но это всё-же по прежнему не идеал ------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
"Очень больших" - это сколько? Больше размера кэша? Если массив не умещается в кэше или вытесняется оттуда какими-то другими данными, например в результате работы фоксового рантайма или вследствие переключения потоков планировщиком винды - в этом случае задержки на чтение памяти могут быть очень велики. Влиять на скорость может не только кэш, но и размер оперативы в целом. Если оперативы не хватает, то при переключении потоков виндовый планировщик может свопнуть странички с массивом на диск, а это вообще труба, на несколько порядков может быть медленней. |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Да, при выводе результата я сначала просто отнимал добавленные в конце цикла цифры, позже уже переписал тело цикла. А насчет порядкового номера - надо будет завтра глянуть (на текущей машине нет фокса)... Массив и курсор у меня почему-то идут практически одинаково по времени (на тех же 10000 элементов - простых чисел). При этом если полный перебор по всем ненулевым элементам массива, то работает чуть быстрее, а если дополнительно сравнивать элемент с корнем проверяемого числа для ограничения лишнего перебора, то вообще тормоза начинаются. Завтра сброшу код, может, "намудрил" чего лишнего... |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
ry Сообщений: 2113 Дата регистрации: 24.09.2007 |
Вот перебор с исключением четных чисел (50 попугаев):
А вот это попытка сделать проверку деления только на простые
Получается в 18 раз медленнее исходного алгоритма. Увеличение размерности массива в цикле или задание начального размера в 10000 элементов на скорости не сказываются. Если же ввести дополнительную проверку
|
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
medstrax Забанен Сообщений: 5964 Дата регистрации: 23.03.2007 |
Проверка делением на все найденные простые избыточна, отсюда и медленно. Достаточно делить на простые не превосходящие корень из проверяемого числа.
И переопределять размерность массива внутри цикла это все-таки не айс. [i]Исправлено 2 раз(а). Последнее : medstrax, 16.04.10 15:17 |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
Igor Korolyov Сообщений: 34580 Дата регистрации: 28.05.2002 |
В этом варианте нужно не "порядковый номер" пытаться проверять на < SQRT(), а само число (при этом вычисление собственно корня, конечно же стоит вынести за цикл. Округлять можно через FLOOR). При этом, собственно говоря и достигается высокая скорость (для данного алгоритма! а не "вообще").
IF aDigits[m.i] > m.lnSQRTofDigit EXIT ENDIF В конце с тем же успехом можно написать более сложный "шорткат" IF m.iDigit % 3 = 0 iDigit=m.iDigit+2 ENDIF IF m.iDigit % 5 = 0 iDigit=m.iDigit+2 ENDIF Это тоже даст выигрыш, но минимальный (порядка 1-2 попугаев). ------------------ WBR, Igor |
Re: Оптимизация алгоритмов вообще и на фоксе в частности | |
---|---|
leonid Автор Сообщений: 3202 Откуда: Рига Дата регистрации: 03.02.2006 |
Игорь, а у меня за 13.5 попугая получилось
P.S. Даже за 11.6 Исправлено 1 раз(а). Последнее : leonid, 16.04.10 16:15 |
© 2000-2024 Fox Club  |