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

Сообщений: 2113
Дата регистрации: 24.09.2007
Вариант перебора по простым делителям с
DO WHILE aDigits < Sqrt(m.iDigit)
проходит быстрее исходного варианта, но все равно медленней, чем простой перебор по всем нечетным числам. Странно, но тот же вариант на цикле FOR c проверкой в цикле
IF aDigits[i] >= Sqrt(m.iDigit) ...
(и даже если корень вычисляется за циклом) едва ворочается.
To Igor Korolyov
То, что надо ограничивать перебор по корню проверяемого числа, а не вычислять корень из порядкового номера последнего простого числа, это понятно. Но эти величины на самом деле растут практически одинаково (доказательства привести не могу, т.к. просто "нутром чую" ). Конечно, строгой линейности там нет, но с некоторым допуском это работает - при округлении в бОльшую сторону простые числа находятся правильно (во всяком случае, до 50000-го простого числа, дальше не проверял). Т.е. и ограничение по aDigits[i] < Sqrt(m.iDigit), и ограничение по i < Ceiling(Sqrt(m.iCount)), выдают один результат, но второй вариант работает заметно быстрее. При повторной прогонке тестов результат уже другой, 60-65 попугаев против стабильно 50-ти у перебора всех нечетных чисел. Не совсем удачный комп для тестирования - очень много фоновых сервисов работает...
Попробовал также реализовать вероятностный метод проверки простоты числа (Миллера-Рабина), но при малом количестве итераций он ошибается, а с увеличением числа итераций время выполнения растет очень сильно.



[i]Исправлено 1 раз(а). Последнее : ry, 16.04.10 16:47
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Чисто теоретически. Можно попробовать найти искомое число,воспользовавшись решетом Эратосфена. По моим прикидкам выигрыш должен быть, т.к. данный алгос позволяет обойтись практически без деления, одними умножениями.
Алгос для решета Эратосфена подразумевает хотя бы грубую оценку верхней границы искомого числа. Для этого можно воспользоваться формулой: количество простых чисел, не превосходящих n стремится к n/ln n при n, стремящемся к бесконечности. Тут возникает проблема - уравнения типа x/ln x = a не решаются аналитически, надо юзать приближенные методы. Не сожрет ли приближенное вычисление корней этого уравнения весь выигрыш от алгоса, если он конечно вообще есть (выигрыш то бишь).
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
-



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

Сообщений: 31166
Откуда: Каменск-Уральски
Дата регистрации: 22.11.2006
Цитата:
Можно попробовать найти искомое число,воспользовавшись решетом Эратосфена.

Во, точно! А я никак не мог вспомнить как такой алгоритм называется.


------------------
"Veni, vidi, vici!"(с)
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
Решето Эратосфена работает на заранее определенной области натуральных чисел и для задачи нахождения N-го простого числа не совсем подходит, т.к. заранее неизвестно количество простых числе в области.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
medstrax
Забанен

Сообщений: 5964
Дата регистрации: 23.03.2007
Советую внимательней перечитать мой пост
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
medstrax
Советую внимательней перечитать мой пост
Да, не внимателен... Все о том же
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
medstrax
И переопределять размерность массива внутри цикла это все-таки не айс.
Да, некрасиво редименшн на кажом шаге делать, но что ещё более интересно, на производительности для данного случая это практически не сказывается - по крайней мере в VFP9 SP2...

2 leonid
Я предполагаю какой ты использовал способ (очевидно это "модерновое" развитие моего "древнего" и простейшего v1), мне просто лениво было его кодировать Подождём что другие придумают.

P.S. Информации в сети более чем достаточно

P.P.S. Совершенно естественно, что на какой-нить 10-летней давности машинке с 128Мб памяти некоторые варианты запросто могут оказаться проигрышными по причине сваливания в своп - всё-же фокс не может так-же экономно память использовать как Си - там, скажем, массив байт имеет размер разный числу элементов - в фоксе же масив его "элементов произвольных типов" будет заметно больше... Как я понимаю, каждый элемент массива занимает как минимум 16 байт (если это строка, то конечно же может быть и намного больше). Впрочем, в указанных пределах поиска 10000-го, я как-то о-о-чень сомневаюсь что не хватит памяти - каких-то жалких 1.5-2 Мб на "самый большой" массив


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

Сообщений: 34580
Дата регистрации: 28.05.2002
medstrax
Чисто теоретически. Можно попробовать найти искомое число,воспользовавшись решетом Эратосфена.
Чисто практически, это и есть мой v1 Во древние греки жгут то!

Я думал его слегка оптимизировать убрав все чётные элементы, но боюсь что тут как раз может сказаться негативно необходимость пересчёта числа в индекс массива, плюс пропуск чётных потом... Ну теперь наверное и до варианта Леонида остался 1 шаг


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

Сообщений: 34580
Дата регистрации: 28.05.2002
P.S. Приближение по указанной оценке (x/ln(x)=N) делается для сравнительно небольших чисел (до 1e10) всего за 10 шагов итеративного алгоритма. Ессно что памяти под такие числа фоксу уже гарантировано не хватит... Для поиска миллионного простого числа этим способом уже потребуется порядка 280Мб памяти (именно фоксу).


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

Сообщений: 5964
Дата регистрации: 23.03.2007
2Igor Korolyov.
Если не лениво, попробуй сравнить исходный вариант на 100 попугаев и твой v1, переписав оба варианта на ассемблере.
Разница должна быть много больше, чем в 6 раз. К тому же можно будет вычислять простые числа с многократно бОльшим порядковым номером. На асме можно заюзать битовые строки, таким образом на каждый байт можно хранить 8 чисел. Для вычисления миллионного простого число достаточно битовой строки, представляющей решето Эратосфена, которая будет занимать примерно 2,5 Мбайт
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
На асме не програмлю, на c# можно будет попробовать - тем паче что челу дал "задание" Он правда все алгоритмы с моего второго пинка уже нашёл - до этого додумался токмо до v2 (массив с уже найденными простыми и там конечно же проверять только < SQRT(проверяемого)).


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

Сообщений: 2022
Откуда: Алматы
Дата регистрации: 14.10.2005
На этот счет довольно интересно:
habrahabr.ru
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2113
Дата регистрации: 24.09.2007
Да, действительно, на коленке собранное решето Эратосфена с оценкой размера решета по методу Ньютона дает эффект в 13-14 попугаев:
m.lnSec = SECONDS()
err=0.1
x=100000
lnArea=x
DO WHILE .t.
f=x/LOG(x)-10000
f1=(LOG(x)-1)/(LOG(x))^2
lnArea=INT(lnArea-(f/f1))
IF ABS(x-lnArea)<err
EXIT
ENDIF
x=lnArea
ENDDO
DIMENSION aDigits(lnArea) of boolean
aDigits[1]=.t.
FOR i=2 TO INT(SQRT(lnArea))
IF !aDigits
FOR j=i^2 TO lnArea STEP i
aDigits[j]=.t.
ENDFOR
ENDIF
ENDFOR
j=0
FOR i=2 TO lnArea
IF !aDigits[i]
j=j+1
IF j=10000
? i
EXIT
ENDIF
ENDIF
ENDFOR
? SECONDS() - lnSec



[i]Исправлено 1 раз(а). Последнее : ry, 19.04.10 11:20
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
13 попугаев - это сколько? У меня выигрыш по скорости в 65 раз.


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

Сообщений: 2113
Дата регистрации: 24.09.2007
Если исходный вариант, предложенный Игорем во втором посте темы, принять за 100 попугаев (у меня он отрабатывает за 1,75 сек), то "решето" вычисляется за 0,23 сек, т.е. примерно 13 попугаев или в 7,6 раза быстрее.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Igor Korolyov

Сообщений: 34580
Дата регистрации: 28.05.2002
Форум урезал в исходнике первый индекс по i т.к. это код для курсива Нать было другие буковки для переменной выбрать, или хотя-бы круглые скобки вместо квадратных
Кроме того сам индекс искомого стоило параметром сделать, а не хардкодингом (кстати не понимаю отчего "задающим" числом ты поставил не 10тыс. а 100тыс. - оно не влияет на результат, просто странно это).
Да, у меня совмещённый цикл отсеивания и поиска (а он, естственно, идёт до конца, а не до "половины", как твой), да и я забыл как-то что отсеивать можно сразу с квадрата очередного простого, потому мой вариант был медленнее... Однако мой способ оценки размера всё-же чуть быстрее, хотя и требует на 1-2 шага больше (его я приведу, остальную часть не имеет смысла). Копеечная экономия, но всё-же
#DEFINE EXTRASPACE 2
LOCAL ln1, lnArea
ln1 = m.tnIndex
DO WHILE .T.
lnArea = m.tnIndex * LOG(m.ln1)
IF ABS(m.lnArea - m.ln1) < 1
lnArea = INT(m.lnArea) + EXTRASPACE
EXIT
ENDIF
ln1 = m.lnArea
ENDDO
P.S. Я попробовал реализовать на фоксе решето Аткина (которое по идее должно быть заметно быстрее простого решета Эратосфена), но к сожалению получил плохой результат (порядка 37 попугаев) - то-ли 3 цикла подводят, то-ли необходимость во флипе ("переворачивании" булевого значения - для чего его нужно всё-же предварительно считать из массива). Тогда как на C#
реализация Аткина один-в-один взятая из википедии - ну с небольшой правкой синтаксиса, и заменой (хотя это и не очень существенно по скорости, зато очень хорошо влияет на размер отъедаемой памяти) bool[] на BitArray - даёт 1.5 фоксовых попугая (при происке 100000-го числа и вовсе 0.25 попугая. А милионное на фоксе - я задолбался ждать эталона, там даже самый быстрый эратосфен занимает порядка 21 секунды, тогда как на C# находит за чуть более 1 секунды)...

2 Влад
В начале темы я привёл тупой алгоритм перебора, который предложил как эталон измерения производительности (а то компы то разные, на чистое время нельзя полагаться, а так - сравнивать есть с чем)...
И кстати было бы очень неплохо понять по сравнению с чем у тебя выигрыш в 65 раз Т.к. это получается 1.5 попугая, что ОЧЕНЬ быстро (именно для поиска 10000-го, т.к. для других индексов пропорции будут совсем другие). Может всё-же в 6.5 раза - тогда это 15 попугаев что неплохо, но чуть ниже текущего "рекорда".


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

Сообщений: 2113
Дата регистрации: 24.09.2007
Igor Korolyov
Форум урезал в исходнике первый индекс по i т.к. это код для курсива Нать было другие буковки для переменной выбрать, или хотя-бы круглые скобки вместо квадратных
Точно, а я и не обратил внимания, в коде должно быть IF !aDigits(i)
Igor Korolyov
Кроме того сам индекс искомого стоило параметром сделать, а не хардкодингом (кстати не понимаю отчего "задающим" числом ты поставил не 10тыс. а 100тыс. - оно не влияет на результат, просто странно это).
Исходное число по методу великого научного тыка взял в 10 раз бОльшим Хотя оказалось достаточно близко к искомой точке.
Вообще быстрый алгоритм оценки размера "решета" не искал, взял наугад метод Ньютона. Хотелось просто убедиться, что "решето" работает быстро даже с учетом поиска его размера. Убедился. Молодцы греки, особенно древние!
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
leonid
Автор

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Ребята, для n>50 для оценки размера решета вполне годится формула 1.2*n*log(n). А мой последний алгоритм вот
clear
sc=seconds()
lnCnt=10000
lnMax=int(1.2*lnCnt*log(lnCnt))
local n(lnMax/2)
m.ts=1
for m.cnt=2 to lnCnt
m.tn=m.ts*2+1
for tt=int(m.tn*m.tn/2) to lnMax/2 step m.tn
n(tt)=.t.
next
m.ts=m.ts+1
do while n(m.ts)
m.ts=m.ts+1
enddo
next
?seconds()-sc
?tn

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

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
А, ну значит вариант с решетом по сравнению с исходным у меня дает 3 при первом запуске и 0.8 при втором. А вариант Леонида - 7-8.


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


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

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

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