Добрый день!
Прошу прощения, продолжу оффтоп про Хаскель.
Два небольших соображения:
1) primesA сильно быстрее, чем primesE, за счёт прыжков до следующего
квадрата. Если это реализовать для primesE, то разница в производительности
между ними уже не такая драматическая:
primesE2 = sieve [2..] 4
> Мог ошибиться в границах, но смысл должен быть понятен: каждая
> следующая граница (lim) получается из предыдущей примерно
> возведением в квадрат, так ведь?
Так, так, именно!
> Поколение - то, что выходит после очередной фильтрации как кусок
> списка простых и служит сомножителями в следующем
чт, 10 окт. 2019 г. в 18:32, Sergei M. Abramov abram_AT_botik.ru <
refal@botik.ru>:
> День добрый, всем!
>
> > То есть для последнего "поколения" эта работа лишняя.
>
> А что такое последнее поколение, если я строю список всех простых
> чисел?
>
> Да, всех, но не сразу ведь.
Сначала весь
>> То есть для последнего "поколения" эта работа лишняя.
Про поколения.
Замечу, что если взять несколько первых простых чисел p1...pK, их
произведение pp и профильтровать (\ k -> (gcd pp k) == 1) весь
бесконечный список [(pk+1).. ], то результат фильтрации имеет очень
простое, эффективное,
On Thu, Oct 10, 2019 at 6:32 PM Sergei M. Abramov abram_AT_botik.ru <
refal@botik.ru> wrote:
>
> Вот, хочу сказать, что меня удивило:
>
> ns' = filter (\ k -> (gcd pp k) == 1) ns
>
> работает немного медленнее, чем
>
> ns' = filter ((== 1).(gcd pp)) ns
>
> Вот нифига ж себе?
>
В
День добрый, всем!
> То есть для последнего "поколения" эта работа лишняя.
А что такое последнее поколение, если я строю список всех простых
чисел?
> Наверно, лучше накапливать в виде списка, а при подаче на Filter
> для следующего шага все перемножить.
> Интересно, для Хаскела это тоже
Александр, а можно попросить вас пропустить вариант для 176100 вместо 4
- тогда результаты (времена) будут сопоставимы.
Я подумал еще об одной оптимизации. Сейчас произведение простых формируется
сразу, а ведь оно может и не понадобиться.
То есть для последнего "поколения" эта работа лишняя.