Guest User

Untitled

a guest
Mar 23rd, 2018
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.46 KB | None | 0 0
  1. module FastSieve =
  2. let rec setNonPrimes (isNonPrimes : _ []) step i =
  3. if i < isNonPrimes.Length then
  4. isNonPrimes.[i] <- true
  5. setNonPrimes isNonPrimes step (i + step)
  6.  
  7. let rec scan (isNonPrimes : _ []) i =
  8. if i < isNonPrimes.Length then
  9. if isNonPrimes.[i] then
  10. scan isNonPrimes (i + 1)
  11. else
  12. setNonPrimes isNonPrimes i (i + i)
  13. scan isNonPrimes (i + 1)
  14.  
  15. let rec buildResizeArray (ra : ResizeArray<_>) (isNonPrimes : _ []) i =
  16. if i < isNonPrimes.Length then
  17. if not isNonPrimes.[i] then
  18. ra.Add i
  19. buildResizeArray ra isNonPrimes (i + 1)
  20.  
  21. let primesLessThan n =
  22. let isNonPrimes = Array.zeroCreate n
  23. isNonPrimes.[0] <- true
  24. isNonPrimes.[1] <- true
  25.  
  26. scan isNonPrimes 2
  27.  
  28. let ra = ResizeArray n
  29. buildResizeArray ra isNonPrimes 0
  30.  
  31. ra.ToArray ()
  32.  
  33. let run count =
  34. primesLessThan count |> Seq.sum
  35.  
  36.  
  37. module SeqSieve =
  38. let sieveOutPrime p numbers =
  39. numbers
  40. |> Seq.filter (fun n -> n % p <> 0)
  41.  
  42. let primesLessThan n =
  43. let removeFirstPrime s =
  44. let s = s |> Seq.cache
  45. match s with
  46. | s when Seq.isEmpty s -> None
  47. | s -> Some(Seq.head s, sieveOutPrime (Seq.head s) (Seq.tail s))
  48.  
  49. let remainingPrimes =
  50. seq {3..2..n}
  51. |> Seq.unfold removeFirstPrime
  52.  
  53. seq { yield 2; yield! remainingPrimes }
  54.  
  55. let run count =
  56. primesLessThan count |> Seq.sum
  57.  
  58. module ListSieve =
  59. let sieveOutPrime p numbers =
  60. numbers
  61. |> List.filter (fun n -> n % p <> 0)
  62.  
  63. let primesLessThan n =
  64. let removeFirstPrime = function
  65. | s when List.isEmpty s -> None
  66. | s -> Some(List.head s, sieveOutPrime (List.head s) (List.tail s))
  67.  
  68. let remainingPrimes =
  69. [|3..2..n|]
  70. |> List.ofArray
  71. |> List.unfold removeFirstPrime
  72.  
  73. 2::remainingPrimes
  74.  
  75. let run count =
  76. primesLessThan count |> List.sum
  77.  
  78. module ArraySieve =
  79. let sieveOutPrime p numbers =
  80. numbers
  81. |> Array.filter (fun n -> n % p <> 0)
  82.  
  83. let primesLessThan n =
  84. let removeFirstPrime = function
  85. | s when Array.isEmpty s -> None
  86. | s -> Some(Array.head s, sieveOutPrime (Array.head s) (Array.tail s))
  87.  
  88. let remainingPrimes =
  89. [|3..2..n|]
  90. |> Array.unfold removeFirstPrime
  91.  
  92. Array.concat [|[|2|]; remainingPrimes|]
  93.  
  94. let run count =
  95. primesLessThan count |> Array.sum
  96.  
  97. module LazySieve =
  98.  
  99. type [<Struct>] LazyResult<'T> =
  100. | LazyEmpty
  101. | LazyCons of 'T*LazyList<'T>
  102. and [<Struct>] LazyList<'T> = LL of (unit -> LazyResult<'T>)
  103.  
  104.  
  105. module LazyList =
  106. module Details =
  107. let mutable runs = 0
  108. let inline run (LL lt) =
  109. runs <- runs + 1
  110. lt ()
  111. open Details
  112.  
  113. let fold f z l =
  114. let rec loop s l =
  115. match run l with
  116. | LazyEmpty -> s
  117. | LazyCons (h, t) -> loop (f s h) t
  118. loop z l
  119.  
  120. let unfold g z : LazyList<_> =
  121. LL <| fun () ->
  122. let rec loop s () =
  123. match g s with
  124. | None -> LazyEmpty
  125. | Some (v, ns) -> LazyCons (v, LL (loop ns))
  126. loop z ()
  127.  
  128. let empty<'T> : LazyList<'T> =
  129. LL <| fun () ->
  130. LazyEmpty
  131.  
  132. let cons h t : LazyList<_> =
  133. LL <| fun () ->
  134. LazyCons (h, t)
  135.  
  136. let head l : _ =
  137. match run l with
  138. | LazyEmpty -> failwith "lazy list is empty"
  139. | LazyCons (h, _) -> h
  140.  
  141. let tail l : LazyList<_> =
  142. LL <| fun () ->
  143. match run l with
  144. | LazyEmpty -> failwith "lazy list is empty"
  145. | LazyCons (_, t) -> run t
  146.  
  147. let isEmpty l : bool =
  148. match run l with
  149. | LazyEmpty -> true
  150. | LazyCons (_, _) -> false
  151.  
  152. let filter f l : LazyList<_> =
  153. LL <| fun () ->
  154. let rec loop ll () =
  155. match run ll with
  156. | LazyEmpty -> LazyEmpty
  157. | LazyCons (h, t) ->
  158. if f h then
  159. LazyCons (h, LL (loop t))
  160. else
  161. loop t ()
  162. loop l ()
  163.  
  164. let map m l : LazyList<_> =
  165. LL <| fun () ->
  166. let rec loop ll () =
  167. match run ll with
  168. | LazyEmpty -> LazyEmpty
  169. | LazyCons (h, t) ->
  170. LazyCons (m h, LL (loop t))
  171. loop l ()
  172.  
  173. let ofArray (vs : _ []) : LazyList<_> =
  174. LL <| fun () ->
  175. let rec loop i () =
  176. if i < vs.Length then
  177. LazyCons (vs.[i], LL (loop (i + 1)))
  178. else
  179. LazyEmpty
  180. loop 0 ()
  181.  
  182. let toArray l : _ [] =
  183. let ra = ResizeArray 16
  184.  
  185. let rec loop l =
  186. match run l with
  187. | LazyEmpty -> ()
  188. | LazyCons (h, t) ->
  189. ra.Add h
  190. loop t
  191.  
  192. loop l
  193.  
  194. ra.ToArray ()
  195.  
  196. let inline sum l =
  197. let mutable sum = LanguagePrimitives.GenericZero<_>
  198.  
  199. let rec loop l =
  200. match run l with
  201. | LazyEmpty -> ()
  202. | LazyCons (h, t) ->
  203. sum <- sum + h
  204. loop t
  205.  
  206. loop l
  207.  
  208. sum
  209.  
  210. let cache l : LazyList<_> =
  211. l |> toArray |> ofArray
  212.  
  213. module Tests =
  214. open FsCheck
  215.  
  216. type Properties () =
  217. static member ``fromArray >> toArray`` (vs : int[]) =
  218. let e = vs
  219. let a = vs |> ofArray |> toArray
  220.  
  221. e = a
  222.  
  223. static member ``isEmpty`` (vs : int[]) =
  224. let e = vs |> Array.isEmpty
  225. let a = vs |> ofArray |> isEmpty
  226.  
  227. e = a
  228.  
  229. static member ``cons`` (v : int) (vs : int[]) =
  230. let e = Array.concat [|[|v|]; vs|]
  231. let a = vs |> ofArray |> cons v |> toArray
  232.  
  233. e = a
  234.  
  235. static member ``head`` (vs : int[]) =
  236. vs.Length > 0 ==> fun () ->
  237. let e = vs |> Array.head
  238. let a = vs |> ofArray |> head
  239.  
  240. e = a
  241.  
  242. static member ``tail`` (vs : int[]) =
  243. vs.Length > 0 ==> fun () ->
  244. let e = vs |> Array.tail
  245. let a = vs |> ofArray |> tail |> toArray
  246.  
  247. e = a
  248.  
  249. static member ``filter`` (vs : int[]) =
  250. let f v = v % 2 = 0
  251. let e = vs |> Array.filter f
  252. let a = vs |> ofArray |> filter f |> toArray
  253.  
  254. e = a
  255.  
  256. static member ``map`` (vs : int[]) =
  257. let m v = v + 2
  258. let e = vs |> Array.map m
  259. let a = vs |> ofArray |> map m |> toArray
  260.  
  261. e = a
  262.  
  263. static member ``fold`` (z : int) (vs : int[]) =
  264. let e = vs |> Array.fold (+) z
  265. let a = vs |> ofArray |> fold (+) z
  266.  
  267. e = a
  268.  
  269. static member ``unfold`` (z : int) (v : int) =
  270. let g s =
  271. if s < v then
  272. Some (s, s + 1)
  273. else
  274. None
  275.  
  276. let e = Array.unfold g z
  277. let a = unfold g z |> toArray
  278.  
  279. e = a
  280.  
  281. let run () =
  282. let config = { Config.Quick with MaxTest = 1000; MaxFail = 1000 }
  283. Check.All<Properties> config
  284.  
  285. let sieveOutPrime p numbers =
  286. numbers
  287. |> LazyList.filter (fun n -> n % p <> 0)
  288.  
  289. let primesLessThan n =
  290. let removeFirstPrime s =
  291. let s = s |> LazyList.cache
  292. match s with
  293. | s when LazyList.isEmpty s -> None
  294. | s -> Some(LazyList.head s, sieveOutPrime (LazyList.head s) (LazyList.tail s))
  295.  
  296. let remainingPrimes =
  297. [|3..2..n|]
  298. |> LazyList.ofArray
  299. |> LazyList.unfold removeFirstPrime
  300.  
  301. LazyList.cons 2 remainingPrimes
  302.  
  303. let run count =
  304. primesLessThan count |> LazyList.sum
  305.  
  306. open LazySieve
  307.  
  308. // now () returns current time in milliseconds since start
  309. let now : unit -> int64 =
  310. let sw = System.Diagnostics.Stopwatch ()
  311. sw.Start ()
  312. fun () -> sw.ElapsedMilliseconds
  313.  
  314. // time estimates the time 'action' repeated a number of times
  315. let time repeat action =
  316. let inline cc i = System.GC.CollectionCount i
  317.  
  318. let v = action ()
  319.  
  320. System.GC.Collect (2, System.GCCollectionMode.Forced, true)
  321.  
  322. let bcc0, bcc1, bcc2 = cc 0, cc 1, cc 2
  323. let b = now ()
  324.  
  325. for i in 1..repeat do
  326. action () |> ignore
  327.  
  328. let e = now ()
  329. let ecc0, ecc1, ecc2 = cc 0, cc 1, cc 2
  330.  
  331. v, (e - b), ecc0 - bcc0, ecc1 - bcc1, ecc2 - bcc2
  332. [<EntryPoint>]
  333. let main argv =
  334. // LazySieve.LazyList.Tests.run ()
  335.  
  336. let testCases =
  337. [|
  338. "seq" , SeqSieve.run
  339. "list" , ListSieve.run
  340. "array" , ArraySieve.run
  341. // "lazy-list" , LazySieve.run
  342. "mutable" , FastSieve.run
  343. |]
  344.  
  345. let outer = 10
  346. let inner = 4000
  347.  
  348. for name, action in testCases do
  349. printfn "Running '%s' ..." name
  350. let v, diff, cc0, cc1, cc2 = time outer (fun () -> action inner)
  351. printfn " it took %d ms with cc (%d, %d, %d), the result is: %A" diff cc0 cc1 cc2 v
  352.  
  353.  
  354. printfn "Lazy evaluations: %A" LazySieve.LazyList.Details.runs
  355. 0
Add Comment
Please, Sign In to add comment