:: Игры Разума
Оптимизация алгоритмов вообще и на фоксе в частности
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Задача простая - написать на фоксе программу, которая вычисляет 10000-ое простое число (первым считать 2). Конечно, нужно постараться, чтобы она работала как можно быстрее.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Меня снова терзают смутные сомнения и странное чувство дежа-вю
Но я никак не могу найти поиском где это всё дело происходило (возможно не на фоксклубе) - при том, судя по дате файлов, было это в 2004 году...
По скорости лучший алгоритм для 10000-го числа (это кстати 104729) опережает банальный перебор в 6 раз (0.25 секунды против 1.5 секунд) для 100000-го числа (а это 1299709) разница увеличивается до 13 раз (3.4 секунды против 45.6)

Вот аглоритм перебора (он конечно же не то чтобы совсем уж "полный" - т.е. там таки есть один махонький элемент оптимизации, но скажем так - это не самый оптимальный алгоритм) - да и как эталон для сравнения/тестирования других алгоритмов его можно использовать.
Кроме того, можно с его помошью грубо так сравнивать производительность машин - дабы верхние цифры скорости не выглядели совсем уж отфонарными. Т.е. принять его производительность за скажем 100 попугаев и от этого плясать в поиске лучшего (не заморачиваясь слишком уж на разницу в железе).

LPARAMETERS tnNumber
m.tnNumber = INT(m.tnNumber)
DO CASE
CASE m.tnNumber < 1
ERROR "Number must be natural figure"
RETURN 0
CASE m.tnNumber = 1
RETURN 2
ENDCASE
LOCAL lnCurPos, lnCurValue, llSimple, lnDivisor
lnCurPos = 2
lnCurValue = 3
DO WHILE .T.
llSimple = .T.
FOR m.lnDivisor = 2 TO INT(SQRT(m.lnCurValue))
IF m.lnCurValue % m.lnDivisor = 0
llSimple = .F.
EXIT
ENDIF
ENDFOR
IF m.llSimple
IF m.lnCurPos = m.tnNumber
EXIT
ELSE
lnCurPos = m.lnCurPos + 1
ENDIF
ENDIF
lnCurValue = m.lnCurValue + 1
ENDDO
RETURN m.lnCurValue

P.S. Очень надеюсь что не требуется найти алгоритм пригодный для поиска абсолютно произвольных простых чисел - т.к. очевидно то что хорошо для 1000-100000 числа будет вряд-ли подходяще для миллионно-миллиардных Да и фокс там уж 100% начнёт загибаться - и по точности, и по объёму памяти.

P.P.S. Естественно я не буду пока выкладывать оптимальный алгоритм, т.к. это будет нечестно - я его не сейчас придумывал, а 6 лет назад Подождём, посмотрим что народ скажет...


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
Смысла перебирать четные числа по алгоритму простого перебора нет, т.е. от тройки STEP 2.


------------------
Совершенство - это не тогда, когда нельзя
ничего прибавить, а тогда, когда нечего убавить.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Для определения простоты m достаточно проверить его делимость на все простые n, такие что n*n не больше m. В данном случае этот алгоритм будет по-видимому оптимальным по скорости, но не по размеру (нужен массив для хранения найденных простых чисел). Различные вероятностные и детерминированные тесты простоты числа вряд ли будут быстрее непосредственной проверки делением, ввиду небольших m.



Исправлено 1 раз(а). Последнее : medstrax, 14.04.10 11:56
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
Влад Колосов
Смысла перебирать четные числа по алгоритму простого перебора нет, т.е. от тройки STEP 2.
Также нет смысла проверять числа, заканчивающиеся на 5. Надо проверять только числа с последней цифрой 1,3,7 или 9.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
medstrax
Для определения простоты m достаточно проверить его делимость на все простые n, такие что n*n не больше m. В данном случае этот алгоритм будет по-видимому оптимальным по скорости, но не по размеру (нужен массив для хранения найденных простых чисел).
Совершенно верно. Побочный выход такого алгоритма - не только искомое N-е простое число, но и все предыдущие... Есть одно НО - для указанного диапазона это НЕ самый быстрый алгоритм (по крайней мере в фоксовой реализации). У меня он идёт как V2 и требует примерно 61 попугая, тогда как мой V1 требует всего 16.5 попугаев Напоминаю что "эталонный вариант это 100 попугаев.
ry
Также нет смысла проверять числа, заканчивающиеся на 5
Ну если ты знаешь простой цикл способный выдавать все нечётные числа КРОМЕ заканчивающихся на 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
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Crispy

Сообщений: 18571
Дата регистрации: 16.05.2005
Igor Korolyov
Ну если ты знаешь простой цикл способный выдавать все нечётные числа КРОМЕ заканчивающихся на 5 - то велкам в тесты А так, эта проверка (делимость на 5 внутри цикла с шагом 2) ничем не отличается от проверки на деломость на любое другое число (например на 3 или на 7 или на чёртову дюжину в конце концов) - т.е. выигрыша в таком "хардкодинге" нет никакого.

Ну почему же. На 5-то как раз и отличается:
ПризнакДелимостиНа5 = IIF(RIGH(STR(lnNumber),1)='5' OR RIGH(STR(lnNumber),1)='0',.T.,.F.)
На 3 или на 7 кстати можно тоже примерно так же, чуть длиннее будет разумеется, просто точно не помню сами признаки, лень искать.
Строчные функции вообще облегчают жизнь на фоксе своей большей проработанностью в смысле функциональности, чем на многих других языках.


------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ssa

Сообщений: 12999
Откуда: Москва
Дата регистрации: 23.03.2005
Crispy
ПризнакДелимостиНа5 = IIF(RIGH(STR(lnNumber),1)='5' OR RIGH(STR(lnNumber),1)='0',.T.,.F.)
Ну обясните же мне наконец дя чего здесь IIF? Без масла масляного жизнь не мила?

------------------
Лень - это неосознанная мудрость.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Crispy

Сообщений: 18571
Дата регистрации: 16.05.2005
ssa
Crispy
ПризнакДелимостиНа5 = IIF(RIGH(STR(lnNumber),1)='5' OR RIGH(STR(lnNumber),1)='0',.T.,.F.)
Ну обясните же мне наконец дя чего здесь IIF? Без масла масляного жизнь не мила?

Для наглядности аргумента. В цикле же понятно всегда лучше воспользоваться, чем окажется удобнее в данном месте. То ли это окажется IIF, то ли IF с дальнейшим EXIT или LOOP.


------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Crispy
ПризнакДелимостиНа5 = IIF(RIGH(STR(lnNumber),1)='5' OR RIGH(STR(lnNumber),1)='0',.T.,.F.)
Это не катит. Процессор гораздо больше времени потратит на преобразование числа в строку(десятки если не сотни инструкций), нежели на простое деление на 5 (одна инструкция, правда весьма не быстрая)



Исправлено 1 раз(а). Последнее : medstrax, 14.04.10 21:04
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Игорь, я когда открывал тему, как раз и хотел подчеркнуть (в заголовке), что оптимизация кода на фоксе отличается от оптимизации вообще. Насчет твоего приведенного кода, я сам поленился его написать, а навскидку думал, что он будет работать заметно дольше. Кстати, его все-таки можно ускорить в два раза "легким движением руки". Для этого нужно не только заменить строчку

lnCurValue = m.lnCurValue + 1

на

lnCurValue = m.lnCurValue + 2

но еще и

FOR m.lnDivisor = 2 TO INT(SQRT(m.lnCurValue))

на

FOR m.lnDivisor = 3 TO INT(SQRT(m.lnCurValue)) step 2

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



Исправлено 1 раз(а). Последнее : leonid, 14.04.10 23:22
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
Я тоже примерно так начинал оптимизировать:
m.tnNumber = 10000
lnCurPos = 4
lnCurValue = 7
Do While m.lnCurPos < m.tnNumber
For m.lnDivisor = 3 To Int(Sqrt(m.lnCurValue)) STEP 2
If m.lnCurValue % m.lnDivisor = 0
lnCurPos = m.lnCurPos - 1
EXIT
ENDIF
ENDFOR
lnCurPos = m.lnCurPos + 1
If (m.lnCurValue % 10 = 3)
lnCurValue = m.lnCurValue + 4
ELSE
lnCurValue = m.lnCurValue + 2
endif
Enddo
Выигрыш - ровно в 2 раза.
По идее, для ускорения можно было бы делать проверку деления не на все нечетные числа, а только на простые (тоже до Int(Sqrt(m.lnCurValue))). Но для этого необходимо хранить результаты предыдущих вычислений. А вот тут начинаются проблемы: варианты и с массивом, и с курсором у меня получаются примерно в 20 раз медленнее полного перебора...
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
ry
Выигрыш - ровно в 2 раза.
В коде есть ошибки - ну точнее нужно выход прописать (а то наращивает после нахождения) и сам подсчёт "порядкового номера числа" сбился на 1-цу - т.к. в таком виде он выдаёт на выходе 104727 которое никак не простое (а "находит" до "порчи" на самом деле он 9999-е простое число 104723)
ry
Но для этого необходимо хранить результаты предыдущих вычислений. А вот тут начинаются проблемы: варианты и с массивом, и с курсором у меня получаются примерно в 20 раз медленнее полного перебора...
Очень странно - у меня варианты с массивами (вплоть до очень больших размеров) очень быстры. Может что-то не то накодил А вот варианты с курсором я думаю и должны быть медленнее...


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
2 leonid
Ну да, не докрутил я игнорирование чётных до конца так оно реально даёт 49 попугаев... Но это всё-же по прежнему не идеал


------------------
WBR, Igor
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Igor Korolyov
Очень странно - у меня варианты с массивами (вплоть до очень больших размеров) очень быстры. Может что-то не то накодил
"Очень больших" - это сколько? Больше размера кэша? Если массив не умещается в кэше или вытесняется оттуда какими-то другими данными, например в результате работы фоксового рантайма или вследствие переключения потоков планировщиком винды - в этом случае задержки на чтение памяти могут быть очень велики.
Влиять на скорость может не только кэш, но и размер оперативы в целом. Если оперативы не хватает, то при переключении потоков виндовый планировщик может свопнуть странички с массивом на диск, а это вообще труба, на несколько порядков
может быть медленней.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
Igor Korolyov
В коде есть ошибки - ну точнее нужно выход прописать (а то наращивает после нахождения) и сам подсчёт "порядкового номера числа" сбился на 1-цу - т.к. в таком виде он выдаёт на выходе 104727 которое никак не простое (а "находит" до "порчи" на самом деле он 9999-е простое число 104723)
Да, при выводе результата я сначала просто отнимал добавленные в конце цикла цифры, позже уже переписал тело цикла. А насчет порядкового номера - надо будет завтра глянуть (на текущей машине нет фокса)...
Массив и курсор у меня почему-то идут практически одинаково по времени (на тех же 10000 элементов - простых чисел). При этом если полный перебор по всем ненулевым элементам массива, то работает чуть быстрее, а если дополнительно сравнивать элемент с корнем проверяемого числа для ограничения лишнего перебора, то вообще тормоза начинаются. Завтра сброшу код, может, "намудрил" чего лишнего...
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
Вот перебор с исключением четных чисел (50 попугаев):
m.lnSec = Seconds()
m.tnNumber = 10000
lnCurPos = 4
lnCurValue = 7
Do While m.lnCurPos < m.tnNumber
lnCurValue = m.lnCurValue + 2
If (m.lnCurValue % 5 = 0)
lnCurValue = m.lnCurValue + 2
ENDIF
For m.lnDivisor = 3 To Int(Sqrt(m.lnCurValue)) STEP 2
If m.lnCurValue % m.lnDivisor = 0
lnCurPos = m.lnCurPos - 1
EXIT
ENDIF
ENDFOR
lnCurPos = m.lnCurPos + 1
Enddo
? m.lnCurValue
? Seconds() - lnSec

А вот это попытка сделать проверку деления только на простые
nSec = SECONDS()
DIMENSION aDigits(3) as Integer
aDigits[1]=2
aDigits[2]=3
aDigits[3]=5
m.iCount=3
m.iDigit=7
DO WHILE m.iCount<10000
m.lSimple=.t.
FOR i=2 TO m.iCount
IF m.iDigit % aDigits[i] = 0
m.lSimple=.f.
EXIT
ENDIF
ENDFOR
IF m.lSimple
m.iCount=m.iCount+1
DIMENSION aDigits(m.iCount)
aDigits[iCount]=m.iDigit
ENDIF
m.iDigit=m.iDigit+2
IF m.iDigit % 5 = 0
m.iDigit=m.iDigit+2
ENDIF
ENDDO
? aDigits[10000]
? Seconds() - nSec

Получается в 18 раз медленнее исходного алгоритма. Увеличение размерности массива в цикле или задание начального размера в 10000 элементов на скорости не сказываются. Если же ввести дополнительную проверку
m.iMax=Int(Sqrt(m.iDigit))
...
IF aDigits[i] > m.iMax
m.lSimple=.f.
EXIT
ENDIF
то работает еще медленнее. Зато замена строки
FOR i=2 TO m.iCount
на
FOR i=2 TO Ceiling(SQRT(m.iCount))
дает лучший результат - 40 попугаев. Вот только замена эта немного "притянутая за уши", т.е. абсолютно не факт, что корень из порядкового номера простого числа растет в той же закономерности, что и корень ряда натуральных чисел. Во всяком случае, замена ceiling() на int() дает неверный результат.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Проверка делением на все найденные простые избыточна, отсюда и медленно. Достаточно делить на простые не превосходящие корень из проверяемого числа.
FOR i=2 TO m.iCount
IF m.iDigit % aDigits = 0
m.lSimple=.f.
EXIT
ENDIF
ENDFOR
можно заменить на
i=2
DO WHILE aDigits[i] < Sqrt(m.iDigit)
IF m.iDigit % aDigits[i] = 0
m.lSimple=.f.
EXIT
ENDIF
i = i+1
ENDDO

И переопределять размерность массива внутри цикла это все-таки не айс.



[i]Исправлено 2 раз(а). Последнее : medstrax, 16.04.10 15:17
Ratings: 0 negative/0 positive
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
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Игорь, а у меня за 13.5 попугая получилось

P.S. Даже за 11.6



Исправлено 1 раз(а). Последнее : leonid, 16.04.10 16:15
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 2 (Гостей: 2)

© 2000-2024 Fox Club 
Яндекс.Метрика