埃拉托色尼在F#的筛子 [英] The sieve of Eratosthenes in F#
问题描述
我是纯功能F#兴趣埃拉托色尼的筛的实现。我感兴趣的实际筛的实现,不是天真功能的实现,是不是真的筛,所以没有这样的事情:
I am interested in an implementation of the sieve of eratosthenes in purely functional F#. I am interested in an implementation of the actual sieve, not the naive functional implementation that isn't really the sieve, so not something like this:
let rec PseudoSieve list =
match list with
| hd::tl -> hd :: (PseudoSieve <| List.filter (fun x -> x % hd <> 0) tl)
| [] -> []
以上简要的第二个链接描述了一个算法,将需要使用一个多重映射,这是不是可以在F#据我知道。 Haskell的实施给使用支持的 insertWith
方法,我还没有看到可供的 F#的功能地图。
The second link above briefly describes an algorithm that would require the use of a multimap, which isn't available in F# as far as I know. The Haskell implementation given uses a map that supports an insertWith
method, which I haven't seen available in the F# functional map.
有谁知道一个办法把给定的哈斯克尔地图code至F#,或许知道的另一种实现方法或筛分算法是高效和更适合于功能的实现或F#?
Does anyone know a way to translate the given Haskell map code to F#, or perhaps knows of alternative implementation methods or sieving algorithms that are as efficient and better suited for a functional implementation or F#?
推荐答案
阅读这篇文章,我想出了不需要multimap中的想法。它处理由连连移动通过其首要值碰撞键向前,直到它到达一个关键是在地图上不碰撞映射键。在素数
是下一个迭代值的键,而且是素数的值的地图。
Reading that article I came up with an idea that doesn't require a multimap. It handles colliding map keys by moving the colliding key forward by its prime value again and again until it reaches a key that isn't in the map. Below primes
is a map with keys of the next iterator value and values that are primes.
let primes =
let rec nextPrime n p primes =
if primes |> Map.containsKey n then
nextPrime (n + p) p primes
else
primes.Add(n, p)
let rec prime n primes =
seq {
if primes |> Map.containsKey n then
let p = primes.Item n
yield! prime (n + 1) (nextPrime (n + p) p (primes.Remove n))
else
yield n
yield! prime (n + 1) (primes.Add(n * n, n))
}
prime 2 Map.empty
我终于想通了,从纸最终优先级队列的算法。 I $低于p $ psent它。我把通用优先级队列功能在顶部。我用一个元组重新present懒列表迭代。该算法达到整数溢出比上面的算法,这是一件好事,因为这意味着我们跳过多个测试用例更快。
I finally figured out the final priority queue based algorithm from that paper. I present it below. I placed the generic priority queue functions at the top. I use a tuple to represent the lazy list iterators. This algorithm reaches integer overflow faster than the above algorithm which is a good thing since it means we are skipping more test cases.
let primes =
// the priority queue functions
let insert = SkewBinomialHeap.insert
let findMin = SkewBinomialHeap.findMin
let insertDeleteMin value = SkewBinomialHeap.deleteMin >> SkewBinomialHeap.insert value
let empty = []
let wheelData = [|2L;4L;2L;4L;6L;2L;6L;4L;2L;4L;6L;6L;2L;6L;4L;2L;6L;4L;6L;8L;4L;2L;4L;2L;4L;8L;6L;4L;6L;2L;4L;6L;2L;6L;6L;4L;2L;4L;6L;2L;6L;4L;2L;4L;2L;10L;2L;10L|]
// increments iterator
let wheel (composite, n, multiple) =
composite + wheelData.[n % 48] * multiple, n + 1, multiple
let insertPrime (prime, n, multiple) table =
insert (prime * prime, n, multiple * prime) table
let rec adjust x table =
let composite, n, multiple = findMin table
if composite <= x then
table
|> insertDeleteMin (wheel (composite, n, multiple))
|> adjust x
else
table
let rec sieve iterator table =
seq {
let x, _, _ = iterator
let composite, _, _ = findMin table
if composite <= x then
yield! sieve (wheel iterator) (adjust x table)
else
yield x
yield! sieve (wheel iterator) (insertPrime iterator table)
}
sieve (13L, 1, 1L) (insertPrime (11L, 0, 1L) empty)
|> Seq.append [2L;3L;5L;7L;11L]
这篇关于埃拉托色尼在F#的筛子的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!