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

Сообщений: 2115
Дата регистрации: 24.09.2007
Немного переделанный вариант Леонида (решето на нечетных числах), работает чуть быстрее (примерно на 1 попугая):
lnSec = SECONDS()
lnCnt=10000
lnOddArea=INT(1.2*lnCnt*log(lnCnt)/2)
DIMENSION aDigits(lnOddArea) of boolean
k=1
FOR i=2 TO lnOddArea
IF !aDigits[i]
FOR j=3*i-1 TO lnOddArea STEP 2*i-1
aDigits[j]=.t.
ENDFOR
k=k+1
IF k=lnCnt
? 2*i-1
EXIT
ENDIF
ENDIF
ENDFOR
? SECONDS() - lnSec
Влад Колосов
А, ну значит вариант с решетом по сравнению с исходным у меня дает 3 при первом запуске и 0.8 при втором. А вариант Леонида - 7-8.
Почему другая скорость на втором запуске? Может, исходный массив не освобождается и используется повторно?
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Taran

Сообщений: 13626
Откуда: Красноярск
Дата регистрации: 16.01.2008
Влад Колосов
А, ну значит вариант с решетом по сравнению с исходным у меня дает 3 при первом запуске и 0.8 при втором. А вариант Леонида - 7-8.
а дополнить свой пост сырцами? Поскольку уже врядли кто сделает лучше 0.8 попугаев. Пора чевствовать победителя!?
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
leonid
Автор

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
2ry

А вот так еще быстрее

lnSec = SECONDS()
lnCnt=10000
lnOddArea=INT(1.2*lnCnt*log(lnCnt)/2)
DIMENSION aDigits(lnOddArea) of boolean
k=2
FOR i=1 TO lnOddArea while k<lnCnt
IF !aDigits[i]
FOR j=(i+1)*i*2 TO lnOddArea STEP 2*i+1
aDigits[j]=.t.
ENDFOR
k=k+1
ENDIF
ENDFOR
? 2*i+1
? SECONDS() - lnSec
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2115
Дата регистрации: 24.09.2007
leonid
2ry
А вот так еще быстрее
Быстрее, только почему-то у меня выдает неверный результат (110527)
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
leonid
Автор

Сообщений: 3204
Откуда: Рига
Дата регистрации: 03.02.2006
Да, действительно, уж не помню, с каким языком спутал, где в for можно было конструкцию while добавлять. А на результат в последний момент не посмотрел. Вот так должно было быть
lnSec = SECONDS()
lnCnt=10000
lnOddArea=INT(1.2*lnCnt*log(lnCnt)/2)
local aDigits(lnOddArea)
k=1
FOR i=1 TO lnOddArea
IF aDigits[i]
loop
ENDIF
FOR j=(i+1)*i*2 TO lnOddArea STEP 2*i+1
aDigits[j]=.t.
ENDFOR
k=k+1
if k=lnCnt
exit
endif
ENDFOR
? 2*i+1
? SECONDS() - lnSec
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Влад Колосов

Сообщений: 22664
Откуда: Ростов-на-Дону
Дата регистрации: 05.05.2005
Так я ничего не изобретал, просто копировал код и смотрел на время. Последний вариант Леонида дает 6 попугаев.


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




Исправлено 1 раз(а). Последнее : Влад Колосов, 20.04.10 17:58
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Taran

Сообщений: 13626
Откуда: Красноярск
Дата регистрации: 16.01.2008
leonid
Да, действительно, уж не помню, с каким языком спутал....
2leonud. Да вроде без проблем твой пред.предыдущий пост отрабатывает, только правильный результат в m.tn
Вообще сильно! Всем респект. Сам не могу (грустно).



Исправлено 2 раз(а). Последнее : Taran, 20.04.10 17:58
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Crispy

Сообщений: 18571
Дата регистрации: 16.05.2005
Решил привести все к единообразному виду, чтобы как-то понятнее было с попугаями.

CLEAR
PUBLIC npop, nk
zamer('Obrazec')
npop = nk
zamer('leon1')
zamer('leon_ry')
zamer('leon_ry_leon')
CANCEL
PROCEDURE leon_ry
LPARAMETERS lnCnt
lnOddArea=INT(1.2*lnCnt*log(lnCnt)/2)
DIMENSION aDigits(lnOddArea) of boolean
k=1
FOR i=2 TO lnOddArea
IF !aDigits
FOR j=3*i-1 TO lnOddArea STEP 2*i-1
aDigits[j]=.t.
ENDFOR
k=k+1
IF k=lnCnt
EXIT
ENDIF
ENDIF
ENDFOR
RETURN 2*i-1
PROCEDURE leon_ry_leon
LPARAMETERS lnCnt
lnOddArea=INT(1.2*lnCnt*log(lnCnt)/2)
local aDigits(lnOddArea)
k=1
FOR i=1 TO lnOddArea
IF aDigits[i]
loop
ENDIF
FOR j=(i+1)*i*2 TO lnOddArea STEP 2*i+1
aDigits[j]=.t.
ENDFOR
k=k+1
if k=lnCnt
exit
endif
ENDFOR
RETURN 2*i+1
PROCEDURE leon1
LPARAMETERS lnCnt
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
RETURN m.ts
PROCEDURE Obrazec
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 = 3 TO INT(SQRT(m.lnCurValue)) STEP 2
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 + 2
ENDDO
RETURN m.lnCurValue
PROCEDURE zamer
LPARAMETERS cproc
LOCAL nt
nt=SECONDS()
?cproc+' =', LTRIM(STR(&cproc(10000)))
nk=SECONDS()-nt
?IIF(cproc='Obrazec',nk,STR((nk/npop)*100,4)), IIF(cproc='Obrazec','сек.','попугаев')
?

Собственно последний (по времени) вариант из предложенных у меня например дает в среднем 19 попугаев. Плюс-минус 1, видимо с очисткой кэша связаны колебания.
Кстати в leon1 не то число выводится в результате?


------------------
В действительности все иначе, чем на самом деле.
                                      (Антуан де Сент-Экзюпери)




[i]Исправлено 2 раз(а). Последнее : Crispy, 22.04.10 15:13
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2115
Дата регистрации: 24.09.2007
Crispy
Решил привести все к единообразному виду, чтобы как-то понятнее было с попугаями. ...
Собственно последний (по времени) вариант из предложенных у меня например дает в среднем 19 попугаев. Плюс-минус 1, видимо с очисткой кэша связаны колебания.
Кстати в leon1 не то число выводится в результате?
В leon1 надо выводить RETURN m.tn
В leon_ry вместо IF !aDigits надо IF !aDigits(i) (форум i в квадратных скобках принимает за код разметки).
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Taran

Сообщений: 13626
Откуда: Красноярск
Дата регистрации: 16.01.2008
и все-таки в первоначальном варианте было
FOR m.lnDivisor = 2 TO INT(SQRT(m.lnCurValue))
в таком случае вариант leon1 дает 7 попугаев.
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
ry

Сообщений: 2115
Дата регистрации: 24.09.2007
Taran
и все-таки в первоначальном варианте было
FOR m.lnDivisor = 2 TO INT(SQRT(m.lnCurValue))
в таком случае вариант leon1 дает 7 попугаев.
Да, Crispy взял за образец уже "уполовиненный" до 50 попугаев вариант.
Только у меня сегодня результаты "пляшут", стабильности при повторных запусках нет. Подозреваю, что виной запущенный WinAmp...
Ratings: 0 negative/0 positive
Re: Оптимизация алгоритмов вообще и на фоксе в частности
Crispy

Сообщений: 18571
Дата регистрации: 16.05.2005
Ну поскольку Игорь согласился на двойной шаг (да оно было и слишком уж очевидным сразу же, видимо на ходу набрасывая вариант с корнем, он просто не подумал о четности), я и решил, что именно такое сравнение и будет наиболее объективным.
А любопытно бы было хотя бы просто для информации узнать, сколько попугаев дает его собственный "секретный" вариант с решетом.


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

Сообщений: 34580
Дата регистрации: 28.05.2002
Я то согласился, что это разумная и достаточо очевидная "оптимизация", но это не повод менять "эталон" Кроме того, я вполне чётко сказал что мой вариант менее оптимален чем первый вариант решета от ry (и даже объяснил в чём различие и почему оно у меня медленнее).


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

Сообщений: 18571
Дата регистрации: 16.05.2005
Ну значит пока что рекорд держит вариант от ry.
А эталон для корня как раз и должен быть именно эталоном для корня ;) - дабы было с чем сравнивать по решету.


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

Сообщений: 2115
Дата регистрации: 24.09.2007
Самый быстрый вариант указан в посте Леонида от 20.04.10 15:42:45 (он же leon_ry_leon у Crispy). На тестах у меня он выдает от 4 до 7 попугаев (но чаще всего 5) по сравнению с исходным вариантом Игоря (с полным перебором). Только мне до сих пор неясно, почему мой первый вариант решета отрабатывал у Влада за 3 и даже за 0,8 попугаев (у меня за 13), тогда как первый вараинт Леонида - за 7-8 (у меня также за 7)?
Ratings: 0 negative/0 positive


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

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

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