Я читаю этот другой пост о версии этого алгоритма F #. Я нашел его очень элегантным и попытался объединить некоторые идеи ответов.
Хотя я оптимизировал его, чтобы сделать меньше проверок (проверьте только числа около 6) и оставьте ненужное кэширование, это все еще очень медленно. Вычисление 10 000 th prime уже занимает более 5 минут. Используя императивный подход, я могу тестировать все 31-битные целые числа не намного больше времени.
Итак, мой вопрос в том, что я упускаю что-то, что делает все это настолько медленным. Например, в другом сообщении кто-то предположил, что LazyList может использовать блокировку. У кого-нибудь есть идея?
Как правило, правила StackOverflow не задают новые вопросы в качестве ответов, я чувствую, что для этого нужно начинать новую тему.
Здесь код:
#r "FSharp.PowerPack.dll"
open Microsoft.FSharp.Collections
let squareLimit = System.Int32.MaxValue |> float32 |> sqrt |> int
let around6 = LazyList.unfold (fun (candidate, (plus, next)) ->
if candidate > System.Int32.MaxValue - plus then
None
else
Some(candidate, (candidate + plus, (next, plus)))
) (5, (2, 4))
let (|SeqCons|SeqNil|) s =
if Seq.isEmpty s then SeqNil
else SeqCons(Seq.head s, Seq.skip 1 s)
let rec lazyDifference l1 l2 =
if Seq.isEmpty l2 then l1 else
match l1, l2 with
| LazyList.Cons(x, xs), SeqCons(y, ys) ->
if x < y then
LazyList.consDelayed x (fun () -> lazyDifference xs l2)
elif x = y then
lazyDifference xs ys
else
lazyDifference l1 ys
| _ -> LazyList.empty
let lazyPrimes =
let rec loop = function
| LazyList.Cons(p, xs) as ll ->
if p > squareLimit then
ll
else
let increment = p <<< 1
let square = p * p
let remaining = lazyDifference xs {square..increment..System.Int32.MaxValue}
LazyList.consDelayed p (fun () -> loop remaining)
| _ -> LazyList.empty
loop (LazyList.cons 2 (LazyList.cons 3 around6))
Если вы вызываете Seq.skip в любом месте, то существует вероятность 99%, что у вас есть алгоритм O (N ^ 2). Для почти каждого элегантного функционального ленивого решения Project Euler с участием последовательностей вы хотите использовать LazyList, а не Seq. (См. Ссылку комментария Джульетты для дальнейшего обсуждения.)
Даже если вам удастся укротить странные квадратичные проблемы проектирования последовательности F #, есть еще некоторые алгоритмические улучшения. Здесь вы работаете здесь (...((x-a)-b)-...). x, или around6, становится все глубже и глубже, но это наиболее часто возникающая последовательность. Преобразовать его в схему (x-(a+b+...)) - или даже использовать древовидную структуру для улучшения сложности. (извините, эта страница находится в Haskell). Это фактически очень близко к сложности императивного сита, хотя все еще медленнее, чем базовый С++-код.
Измеряя локальные эмпирические порядки роста как O(n^a) <--> a = log(t_2/t_1) / log(n_2/n_1) (в выражении n), идеал n log(n) log(log(n)) переводится в O(n^1.12) .. O(n^1.085) в диапазоне n=10^5..10^7. Простой базовый уровень С++ императивный код достигает O(n^1.45 .. 1.18 .. 1.14), а код слияния деревьев, а также код, основанный на приоритетной очереди, демонстрируют устойчивое поведение O(n^1.20), более или менее. Конечно, С++ составляет ~ 50 20..15 раз быстрее, но в основном это просто "постоянный фактор".:)