Получение функционального сита из Эратосфена быстро - PullRequest
Новая
       56

Получение функционального сита из Эратосфена быстро

5 голосов
/ 24 июня 2011

Я прочитал этот другой пост о версии F # этого алгоритма . Я нашел его очень элегантным и попытался объединить некоторые идеи ответов.

Хотя я оптимизировал его, чтобы сделать меньше проверок (проверять только числа около 6) и исключить ненужное кэширование, оно все еще мучительно медленно. Вычисление 10000 th премьер уже займет более 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))

Ответы [ 2 ]

2 голосов
/ 24 июня 2011

Если вы звоните Seq.skip в любом месте, то вероятность того, что у вас есть алгоритм O (N ^ 2), составляет 99%.Почти для каждого элегантного, функционального, ленивого решения Project Euler, включающего последовательности, вы должны использовать LazyList, а не Seq.(См. Ссылку на комментарий Джульетты для дальнейшего обсуждения.)

0 голосов
/ 01 января 2012

Даже если вам удастся укротить странные проблемы проектирования квадратичных F # -последовательностей, некоторые алгоритмические улучшения еще впереди. Вы работаете здесь (...((x-a)-b)-...). x или around6 становится все глубже и глубже, но это наиболее часто производящая последовательность. Преобразуйте в схему (x-(a+b+...)) - или даже используйте древовидную структуру, чтобы улучшить сложность . (извините, эта страница в Хаскеле). Это на самом деле очень близко к сложности императивного сита, хотя все еще намного медленнее, чем базовый код C ++.

Измерение локальных эмпирических порядков роста как 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 , Простой базовый уровень C ++ императивный код достигает O(n^1.45 .. 1.18 .. 1.14), в то время как код объединения деревьев , а также код на основе очереди приоритетов, оба демонстрируют устойчивое поведение O(n^1.20), более или менее. Конечно, C ++ в ~ 1026 * 50 20,15 раз быстрее, но это в основном просто "постоянный фактор". :) 1030 * *

...