F# Idiomatic Performance












6














I'm using Exercism to learn F#. The Nth Prime challenge was to build a Sieve of Eratosthenes. The unit test had you search for the 1,001st prime which is 104,743.



I modified a code snippet I remembered from F# For Fun and Profit to work in batches (need 10k primes, not 25) and compared it to my own imperative version. There is a significant performance difference:



BenchmarkDotNet v0.11.2 Results
(BenchmarkDotNet v0.11.2)



Is there an efficient way to do this idiomatically? I like F#. I like how much time using the F# libraries save. But sometimes I can't see an efficient idiomatic route.



Here is the idiomatic code:



// we only need to check numbers ending in 1, 3, 7, 9 for prime
let getCandidates seed =
let nextTen seed ten =
let x = (seed) + (ten * 10)
[x + 1; x + 3; x + 7; x + 9]
let candidates = [for x in 0..9 do yield! nextTen seed x ]
match candidates with
| 1::xs -> xs //skip 1 for candidates
| _ -> candidates


let filterCandidates (primes:int list) (candidates:int list): int list =
let isComposite candidate =
primes |> List.exists (fun p -> candidate % p = 0 )
candidates |> List.filter (fun c -> not (isComposite c))

let prime nth : int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let rec sieve seed primes candidates =
match candidates with
| -> getCandidates seed |> filterCandidates primes |> sieve (seed + 100) primes //get candidates from next hunderd
| p::_ when primes.Length = nth - 2 -> p //value found; nth - 2 because p and 2 are not in primes list
| p::xs when (p * p) < (seed + 100) -> //any composite of this prime will not be found until after p^2
sieve seed (p::primes) [for x in xs do if (x % p) > 0 then yield x]
| p::xs ->
sieve seed (p::primes) xs


Some (sieve 0 [3; 5] )


And here is the imperative:



type prime = 
struct
val BaseNumber: int
val mutable NextMultiple: int
new (baseNumber) = {BaseNumber = baseNumber; NextMultiple = (baseNumber * baseNumber)}
//next multiple that is odd; (odd plus odd) is even plus odd is odd
member this.incrMultiple() = this.NextMultiple <- (this.BaseNumber * 2) + this.NextMultiple; this
end

let prime nth : int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let nth' = nth - 1 //not including 2, the first prime
let primes = Array.zeroCreate<prime>(nth')
let mutable primeCount = 0
let mutable candidate = 3
let mutable isComposite = false
while primeCount < nth' do

for i = 0 to primeCount - 1 do
if primes.[i].NextMultiple = candidate then
isComposite <- true
primes.[i] <- primes.[i].incrMultiple()

if isComposite = false then
primes.[primeCount] <- new prime(candidate)
primeCount <- primeCount + 1

isComposite <- false
candidate <- candidate + 2

Some primes.[nth' - 1].BaseNumber









share|improve this question






















  • Amusing name for a website.
    – Robert Harvey
    Nov 18 '18 at 1:39










  • @EricP: In order to approach the idiomatic functional solution performance facet you may want to look at primes F# sequence definition from this SO answer. I believe primes |> Seq.item 10001 may seriously beat the imperative solution you came up with. Then, picking from there the practical application of laziness and memoization idioms you may begin feel better about the functional code efficiency.
    – Gene Belitski
    Nov 19 '18 at 2:03
















6














I'm using Exercism to learn F#. The Nth Prime challenge was to build a Sieve of Eratosthenes. The unit test had you search for the 1,001st prime which is 104,743.



I modified a code snippet I remembered from F# For Fun and Profit to work in batches (need 10k primes, not 25) and compared it to my own imperative version. There is a significant performance difference:



BenchmarkDotNet v0.11.2 Results
(BenchmarkDotNet v0.11.2)



Is there an efficient way to do this idiomatically? I like F#. I like how much time using the F# libraries save. But sometimes I can't see an efficient idiomatic route.



Here is the idiomatic code:



// we only need to check numbers ending in 1, 3, 7, 9 for prime
let getCandidates seed =
let nextTen seed ten =
let x = (seed) + (ten * 10)
[x + 1; x + 3; x + 7; x + 9]
let candidates = [for x in 0..9 do yield! nextTen seed x ]
match candidates with
| 1::xs -> xs //skip 1 for candidates
| _ -> candidates


let filterCandidates (primes:int list) (candidates:int list): int list =
let isComposite candidate =
primes |> List.exists (fun p -> candidate % p = 0 )
candidates |> List.filter (fun c -> not (isComposite c))

let prime nth : int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let rec sieve seed primes candidates =
match candidates with
| -> getCandidates seed |> filterCandidates primes |> sieve (seed + 100) primes //get candidates from next hunderd
| p::_ when primes.Length = nth - 2 -> p //value found; nth - 2 because p and 2 are not in primes list
| p::xs when (p * p) < (seed + 100) -> //any composite of this prime will not be found until after p^2
sieve seed (p::primes) [for x in xs do if (x % p) > 0 then yield x]
| p::xs ->
sieve seed (p::primes) xs


Some (sieve 0 [3; 5] )


And here is the imperative:



type prime = 
struct
val BaseNumber: int
val mutable NextMultiple: int
new (baseNumber) = {BaseNumber = baseNumber; NextMultiple = (baseNumber * baseNumber)}
//next multiple that is odd; (odd plus odd) is even plus odd is odd
member this.incrMultiple() = this.NextMultiple <- (this.BaseNumber * 2) + this.NextMultiple; this
end

let prime nth : int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let nth' = nth - 1 //not including 2, the first prime
let primes = Array.zeroCreate<prime>(nth')
let mutable primeCount = 0
let mutable candidate = 3
let mutable isComposite = false
while primeCount < nth' do

for i = 0 to primeCount - 1 do
if primes.[i].NextMultiple = candidate then
isComposite <- true
primes.[i] <- primes.[i].incrMultiple()

if isComposite = false then
primes.[primeCount] <- new prime(candidate)
primeCount <- primeCount + 1

isComposite <- false
candidate <- candidate + 2

Some primes.[nth' - 1].BaseNumber









share|improve this question






















  • Amusing name for a website.
    – Robert Harvey
    Nov 18 '18 at 1:39










  • @EricP: In order to approach the idiomatic functional solution performance facet you may want to look at primes F# sequence definition from this SO answer. I believe primes |> Seq.item 10001 may seriously beat the imperative solution you came up with. Then, picking from there the practical application of laziness and memoization idioms you may begin feel better about the functional code efficiency.
    – Gene Belitski
    Nov 19 '18 at 2:03














6












6








6


2





I'm using Exercism to learn F#. The Nth Prime challenge was to build a Sieve of Eratosthenes. The unit test had you search for the 1,001st prime which is 104,743.



I modified a code snippet I remembered from F# For Fun and Profit to work in batches (need 10k primes, not 25) and compared it to my own imperative version. There is a significant performance difference:



BenchmarkDotNet v0.11.2 Results
(BenchmarkDotNet v0.11.2)



Is there an efficient way to do this idiomatically? I like F#. I like how much time using the F# libraries save. But sometimes I can't see an efficient idiomatic route.



Here is the idiomatic code:



// we only need to check numbers ending in 1, 3, 7, 9 for prime
let getCandidates seed =
let nextTen seed ten =
let x = (seed) + (ten * 10)
[x + 1; x + 3; x + 7; x + 9]
let candidates = [for x in 0..9 do yield! nextTen seed x ]
match candidates with
| 1::xs -> xs //skip 1 for candidates
| _ -> candidates


let filterCandidates (primes:int list) (candidates:int list): int list =
let isComposite candidate =
primes |> List.exists (fun p -> candidate % p = 0 )
candidates |> List.filter (fun c -> not (isComposite c))

let prime nth : int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let rec sieve seed primes candidates =
match candidates with
| -> getCandidates seed |> filterCandidates primes |> sieve (seed + 100) primes //get candidates from next hunderd
| p::_ when primes.Length = nth - 2 -> p //value found; nth - 2 because p and 2 are not in primes list
| p::xs when (p * p) < (seed + 100) -> //any composite of this prime will not be found until after p^2
sieve seed (p::primes) [for x in xs do if (x % p) > 0 then yield x]
| p::xs ->
sieve seed (p::primes) xs


Some (sieve 0 [3; 5] )


And here is the imperative:



type prime = 
struct
val BaseNumber: int
val mutable NextMultiple: int
new (baseNumber) = {BaseNumber = baseNumber; NextMultiple = (baseNumber * baseNumber)}
//next multiple that is odd; (odd plus odd) is even plus odd is odd
member this.incrMultiple() = this.NextMultiple <- (this.BaseNumber * 2) + this.NextMultiple; this
end

let prime nth : int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let nth' = nth - 1 //not including 2, the first prime
let primes = Array.zeroCreate<prime>(nth')
let mutable primeCount = 0
let mutable candidate = 3
let mutable isComposite = false
while primeCount < nth' do

for i = 0 to primeCount - 1 do
if primes.[i].NextMultiple = candidate then
isComposite <- true
primes.[i] <- primes.[i].incrMultiple()

if isComposite = false then
primes.[primeCount] <- new prime(candidate)
primeCount <- primeCount + 1

isComposite <- false
candidate <- candidate + 2

Some primes.[nth' - 1].BaseNumber









share|improve this question













I'm using Exercism to learn F#. The Nth Prime challenge was to build a Sieve of Eratosthenes. The unit test had you search for the 1,001st prime which is 104,743.



I modified a code snippet I remembered from F# For Fun and Profit to work in batches (need 10k primes, not 25) and compared it to my own imperative version. There is a significant performance difference:



BenchmarkDotNet v0.11.2 Results
(BenchmarkDotNet v0.11.2)



Is there an efficient way to do this idiomatically? I like F#. I like how much time using the F# libraries save. But sometimes I can't see an efficient idiomatic route.



Here is the idiomatic code:



// we only need to check numbers ending in 1, 3, 7, 9 for prime
let getCandidates seed =
let nextTen seed ten =
let x = (seed) + (ten * 10)
[x + 1; x + 3; x + 7; x + 9]
let candidates = [for x in 0..9 do yield! nextTen seed x ]
match candidates with
| 1::xs -> xs //skip 1 for candidates
| _ -> candidates


let filterCandidates (primes:int list) (candidates:int list): int list =
let isComposite candidate =
primes |> List.exists (fun p -> candidate % p = 0 )
candidates |> List.filter (fun c -> not (isComposite c))

let prime nth : int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let rec sieve seed primes candidates =
match candidates with
| -> getCandidates seed |> filterCandidates primes |> sieve (seed + 100) primes //get candidates from next hunderd
| p::_ when primes.Length = nth - 2 -> p //value found; nth - 2 because p and 2 are not in primes list
| p::xs when (p * p) < (seed + 100) -> //any composite of this prime will not be found until after p^2
sieve seed (p::primes) [for x in xs do if (x % p) > 0 then yield x]
| p::xs ->
sieve seed (p::primes) xs


Some (sieve 0 [3; 5] )


And here is the imperative:



type prime = 
struct
val BaseNumber: int
val mutable NextMultiple: int
new (baseNumber) = {BaseNumber = baseNumber; NextMultiple = (baseNumber * baseNumber)}
//next multiple that is odd; (odd plus odd) is even plus odd is odd
member this.incrMultiple() = this.NextMultiple <- (this.BaseNumber * 2) + this.NextMultiple; this
end

let prime nth : int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let nth' = nth - 1 //not including 2, the first prime
let primes = Array.zeroCreate<prime>(nth')
let mutable primeCount = 0
let mutable candidate = 3
let mutable isComposite = false
while primeCount < nth' do

for i = 0 to primeCount - 1 do
if primes.[i].NextMultiple = candidate then
isComposite <- true
primes.[i] <- primes.[i].incrMultiple()

if isComposite = false then
primes.[primeCount] <- new prime(candidate)
primeCount <- primeCount + 1

isComposite <- false
candidate <- candidate + 2

Some primes.[nth' - 1].BaseNumber






performance f# idiomatic imperative






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked Nov 18 '18 at 1:33









EricP

505




505












  • Amusing name for a website.
    – Robert Harvey
    Nov 18 '18 at 1:39










  • @EricP: In order to approach the idiomatic functional solution performance facet you may want to look at primes F# sequence definition from this SO answer. I believe primes |> Seq.item 10001 may seriously beat the imperative solution you came up with. Then, picking from there the practical application of laziness and memoization idioms you may begin feel better about the functional code efficiency.
    – Gene Belitski
    Nov 19 '18 at 2:03


















  • Amusing name for a website.
    – Robert Harvey
    Nov 18 '18 at 1:39










  • @EricP: In order to approach the idiomatic functional solution performance facet you may want to look at primes F# sequence definition from this SO answer. I believe primes |> Seq.item 10001 may seriously beat the imperative solution you came up with. Then, picking from there the practical application of laziness and memoization idioms you may begin feel better about the functional code efficiency.
    – Gene Belitski
    Nov 19 '18 at 2:03
















Amusing name for a website.
– Robert Harvey
Nov 18 '18 at 1:39




Amusing name for a website.
– Robert Harvey
Nov 18 '18 at 1:39












@EricP: In order to approach the idiomatic functional solution performance facet you may want to look at primes F# sequence definition from this SO answer. I believe primes |> Seq.item 10001 may seriously beat the imperative solution you came up with. Then, picking from there the practical application of laziness and memoization idioms you may begin feel better about the functional code efficiency.
– Gene Belitski
Nov 19 '18 at 2:03




@EricP: In order to approach the idiomatic functional solution performance facet you may want to look at primes F# sequence definition from this SO answer. I believe primes |> Seq.item 10001 may seriously beat the imperative solution you came up with. Then, picking from there the practical application of laziness and memoization idioms you may begin feel better about the functional code efficiency.
– Gene Belitski
Nov 19 '18 at 2:03












2 Answers
2






active

oldest

votes


















2














So in general, when using functional idioms, you probably expect to be a bit slower than when using the imperative model because you have to create new objects which takes a lot longer than modifying an already existing object.



For this problem specifically the fact that when using an F# list, the fact that you need to iterate the list of primes every time is a performance loss compared to using an array. You should also note you don't need to generate a candidate list separately, you can just loop and add 2 on the fly. That said the biggest performance win is probably using mutation to store your nextNumber.



type prime = {BaseNumber: int; mutable NextNumber: int}
let isComposite (primes:prime list) candidate =
let rec inner primes candidate =
match primes with
| -> false
| p::ps ->
match p.NextNumber = candidate with
| true -> p.NextNumber <- p.NextNumber + p.BaseNumber*2
inner ps candidate |> ignore
true
| false -> inner ps candidate
inner primes candidate


let prime nth: int option =
match nth with
| 0 -> None
| 1 -> Some 2
| _ ->
let rec findPrime (primes: prime list) (candidate: int) (n: int) =
match nth - n with
| 1 -> primes
| _ -> let isC = isComposite primes candidate
if (not isC) then
findPrime ({BaseNumber = candidate; NextNumber = candidate*candidate}::primes) (candidate + 2) (n+1)
else
findPrime primes (candidate + 2) n
let p = findPrime [{BaseNumber = 3; NextNumber = 9};{BaseNumber = 5; NextNumber = 25}] 7 2
|> List.head
Some(p.BaseNumber)


Running this through #time, I get around 500ms to run prime 10001. For comparison, your "imperative" code takes about 250ms and your "idomatic" code takes around 1300ms.






share|improve this answer





























    1














    At first glance you're not comparing equal concepts. Of course, I'm not talking about functional vs imperative, rather the concepts behind the algorithms themselves.



    Your wiki reference says it best:




    This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.




    In other words, the Sieve of Eratosthenes' power lies in not using trial division. Another wiki ref:




    Trial division is the most laborious but easiest to understand of the integer factorization algorithms.




    And is effectively what you're doing in your filter.



    let isComposite candidate =  
    primes |> List.exists (fun p -> candidate % p = 0 )





    share|improve this answer





















    • I see that. Also, to be fair, Scott Wlaschin said it was a "crude implementation of a prime number sieve" and it was to find the first 25 primes and not the first 10k. The question still remains though, what is an efficient, idiomatic implementation? My brain goes straight to imperative and I'm struggling to learn a new approach.
      – EricP
      Nov 18 '18 at 16:36












    • @EricP for F# idiomatic way is to mix imperative and declarative code. Don't confuse F# with Haskell.
      – Szer
      Nov 22 '18 at 6:22











    Your Answer






    StackExchange.ifUsing("editor", function () {
    StackExchange.using("externalEditor", function () {
    StackExchange.using("snippets", function () {
    StackExchange.snippets.init();
    });
    });
    }, "code-snippets");

    StackExchange.ready(function() {
    var channelOptions = {
    tags: "".split(" "),
    id: "1"
    };
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function() {
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled) {
    StackExchange.using("snippets", function() {
    createEditor();
    });
    }
    else {
    createEditor();
    }
    });

    function createEditor() {
    StackExchange.prepareEditor({
    heartbeatType: 'answer',
    autoActivateHeartbeat: false,
    convertImagesToLinks: true,
    noModals: true,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    imageUploader: {
    brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
    contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
    allowUrls: true
    },
    onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    });


    }
    });














    draft saved

    draft discarded


















    StackExchange.ready(
    function () {
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53357139%2ff-idiomatic-performance%23new-answer', 'question_page');
    }
    );

    Post as a guest















    Required, but never shown

























    2 Answers
    2






    active

    oldest

    votes








    2 Answers
    2






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes









    2














    So in general, when using functional idioms, you probably expect to be a bit slower than when using the imperative model because you have to create new objects which takes a lot longer than modifying an already existing object.



    For this problem specifically the fact that when using an F# list, the fact that you need to iterate the list of primes every time is a performance loss compared to using an array. You should also note you don't need to generate a candidate list separately, you can just loop and add 2 on the fly. That said the biggest performance win is probably using mutation to store your nextNumber.



    type prime = {BaseNumber: int; mutable NextNumber: int}
    let isComposite (primes:prime list) candidate =
    let rec inner primes candidate =
    match primes with
    | -> false
    | p::ps ->
    match p.NextNumber = candidate with
    | true -> p.NextNumber <- p.NextNumber + p.BaseNumber*2
    inner ps candidate |> ignore
    true
    | false -> inner ps candidate
    inner primes candidate


    let prime nth: int option =
    match nth with
    | 0 -> None
    | 1 -> Some 2
    | _ ->
    let rec findPrime (primes: prime list) (candidate: int) (n: int) =
    match nth - n with
    | 1 -> primes
    | _ -> let isC = isComposite primes candidate
    if (not isC) then
    findPrime ({BaseNumber = candidate; NextNumber = candidate*candidate}::primes) (candidate + 2) (n+1)
    else
    findPrime primes (candidate + 2) n
    let p = findPrime [{BaseNumber = 3; NextNumber = 9};{BaseNumber = 5; NextNumber = 25}] 7 2
    |> List.head
    Some(p.BaseNumber)


    Running this through #time, I get around 500ms to run prime 10001. For comparison, your "imperative" code takes about 250ms and your "idomatic" code takes around 1300ms.






    share|improve this answer


























      2














      So in general, when using functional idioms, you probably expect to be a bit slower than when using the imperative model because you have to create new objects which takes a lot longer than modifying an already existing object.



      For this problem specifically the fact that when using an F# list, the fact that you need to iterate the list of primes every time is a performance loss compared to using an array. You should also note you don't need to generate a candidate list separately, you can just loop and add 2 on the fly. That said the biggest performance win is probably using mutation to store your nextNumber.



      type prime = {BaseNumber: int; mutable NextNumber: int}
      let isComposite (primes:prime list) candidate =
      let rec inner primes candidate =
      match primes with
      | -> false
      | p::ps ->
      match p.NextNumber = candidate with
      | true -> p.NextNumber <- p.NextNumber + p.BaseNumber*2
      inner ps candidate |> ignore
      true
      | false -> inner ps candidate
      inner primes candidate


      let prime nth: int option =
      match nth with
      | 0 -> None
      | 1 -> Some 2
      | _ ->
      let rec findPrime (primes: prime list) (candidate: int) (n: int) =
      match nth - n with
      | 1 -> primes
      | _ -> let isC = isComposite primes candidate
      if (not isC) then
      findPrime ({BaseNumber = candidate; NextNumber = candidate*candidate}::primes) (candidate + 2) (n+1)
      else
      findPrime primes (candidate + 2) n
      let p = findPrime [{BaseNumber = 3; NextNumber = 9};{BaseNumber = 5; NextNumber = 25}] 7 2
      |> List.head
      Some(p.BaseNumber)


      Running this through #time, I get around 500ms to run prime 10001. For comparison, your "imperative" code takes about 250ms and your "idomatic" code takes around 1300ms.






      share|improve this answer
























        2












        2








        2






        So in general, when using functional idioms, you probably expect to be a bit slower than when using the imperative model because you have to create new objects which takes a lot longer than modifying an already existing object.



        For this problem specifically the fact that when using an F# list, the fact that you need to iterate the list of primes every time is a performance loss compared to using an array. You should also note you don't need to generate a candidate list separately, you can just loop and add 2 on the fly. That said the biggest performance win is probably using mutation to store your nextNumber.



        type prime = {BaseNumber: int; mutable NextNumber: int}
        let isComposite (primes:prime list) candidate =
        let rec inner primes candidate =
        match primes with
        | -> false
        | p::ps ->
        match p.NextNumber = candidate with
        | true -> p.NextNumber <- p.NextNumber + p.BaseNumber*2
        inner ps candidate |> ignore
        true
        | false -> inner ps candidate
        inner primes candidate


        let prime nth: int option =
        match nth with
        | 0 -> None
        | 1 -> Some 2
        | _ ->
        let rec findPrime (primes: prime list) (candidate: int) (n: int) =
        match nth - n with
        | 1 -> primes
        | _ -> let isC = isComposite primes candidate
        if (not isC) then
        findPrime ({BaseNumber = candidate; NextNumber = candidate*candidate}::primes) (candidate + 2) (n+1)
        else
        findPrime primes (candidate + 2) n
        let p = findPrime [{BaseNumber = 3; NextNumber = 9};{BaseNumber = 5; NextNumber = 25}] 7 2
        |> List.head
        Some(p.BaseNumber)


        Running this through #time, I get around 500ms to run prime 10001. For comparison, your "imperative" code takes about 250ms and your "idomatic" code takes around 1300ms.






        share|improve this answer












        So in general, when using functional idioms, you probably expect to be a bit slower than when using the imperative model because you have to create new objects which takes a lot longer than modifying an already existing object.



        For this problem specifically the fact that when using an F# list, the fact that you need to iterate the list of primes every time is a performance loss compared to using an array. You should also note you don't need to generate a candidate list separately, you can just loop and add 2 on the fly. That said the biggest performance win is probably using mutation to store your nextNumber.



        type prime = {BaseNumber: int; mutable NextNumber: int}
        let isComposite (primes:prime list) candidate =
        let rec inner primes candidate =
        match primes with
        | -> false
        | p::ps ->
        match p.NextNumber = candidate with
        | true -> p.NextNumber <- p.NextNumber + p.BaseNumber*2
        inner ps candidate |> ignore
        true
        | false -> inner ps candidate
        inner primes candidate


        let prime nth: int option =
        match nth with
        | 0 -> None
        | 1 -> Some 2
        | _ ->
        let rec findPrime (primes: prime list) (candidate: int) (n: int) =
        match nth - n with
        | 1 -> primes
        | _ -> let isC = isComposite primes candidate
        if (not isC) then
        findPrime ({BaseNumber = candidate; NextNumber = candidate*candidate}::primes) (candidate + 2) (n+1)
        else
        findPrime primes (candidate + 2) n
        let p = findPrime [{BaseNumber = 3; NextNumber = 9};{BaseNumber = 5; NextNumber = 25}] 7 2
        |> List.head
        Some(p.BaseNumber)


        Running this through #time, I get around 500ms to run prime 10001. For comparison, your "imperative" code takes about 250ms and your "idomatic" code takes around 1300ms.







        share|improve this answer












        share|improve this answer



        share|improve this answer










        answered Nov 18 '18 at 23:53









        Ringil

        3,46021025




        3,46021025

























            1














            At first glance you're not comparing equal concepts. Of course, I'm not talking about functional vs imperative, rather the concepts behind the algorithms themselves.



            Your wiki reference says it best:




            This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.




            In other words, the Sieve of Eratosthenes' power lies in not using trial division. Another wiki ref:




            Trial division is the most laborious but easiest to understand of the integer factorization algorithms.




            And is effectively what you're doing in your filter.



            let isComposite candidate =  
            primes |> List.exists (fun p -> candidate % p = 0 )





            share|improve this answer





















            • I see that. Also, to be fair, Scott Wlaschin said it was a "crude implementation of a prime number sieve" and it was to find the first 25 primes and not the first 10k. The question still remains though, what is an efficient, idiomatic implementation? My brain goes straight to imperative and I'm struggling to learn a new approach.
              – EricP
              Nov 18 '18 at 16:36












            • @EricP for F# idiomatic way is to mix imperative and declarative code. Don't confuse F# with Haskell.
              – Szer
              Nov 22 '18 at 6:22
















            1














            At first glance you're not comparing equal concepts. Of course, I'm not talking about functional vs imperative, rather the concepts behind the algorithms themselves.



            Your wiki reference says it best:




            This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.




            In other words, the Sieve of Eratosthenes' power lies in not using trial division. Another wiki ref:




            Trial division is the most laborious but easiest to understand of the integer factorization algorithms.




            And is effectively what you're doing in your filter.



            let isComposite candidate =  
            primes |> List.exists (fun p -> candidate % p = 0 )





            share|improve this answer





















            • I see that. Also, to be fair, Scott Wlaschin said it was a "crude implementation of a prime number sieve" and it was to find the first 25 primes and not the first 10k. The question still remains though, what is an efficient, idiomatic implementation? My brain goes straight to imperative and I'm struggling to learn a new approach.
              – EricP
              Nov 18 '18 at 16:36












            • @EricP for F# idiomatic way is to mix imperative and declarative code. Don't confuse F# with Haskell.
              – Szer
              Nov 22 '18 at 6:22














            1












            1








            1






            At first glance you're not comparing equal concepts. Of course, I'm not talking about functional vs imperative, rather the concepts behind the algorithms themselves.



            Your wiki reference says it best:




            This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.




            In other words, the Sieve of Eratosthenes' power lies in not using trial division. Another wiki ref:




            Trial division is the most laborious but easiest to understand of the integer factorization algorithms.




            And is effectively what you're doing in your filter.



            let isComposite candidate =  
            primes |> List.exists (fun p -> candidate % p = 0 )





            share|improve this answer












            At first glance you're not comparing equal concepts. Of course, I'm not talking about functional vs imperative, rather the concepts behind the algorithms themselves.



            Your wiki reference says it best:




            This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.




            In other words, the Sieve of Eratosthenes' power lies in not using trial division. Another wiki ref:




            Trial division is the most laborious but easiest to understand of the integer factorization algorithms.




            And is effectively what you're doing in your filter.



            let isComposite candidate =  
            primes |> List.exists (fun p -> candidate % p = 0 )






            share|improve this answer












            share|improve this answer



            share|improve this answer










            answered Nov 18 '18 at 10:32









            Funk

            4,7541725




            4,7541725












            • I see that. Also, to be fair, Scott Wlaschin said it was a "crude implementation of a prime number sieve" and it was to find the first 25 primes and not the first 10k. The question still remains though, what is an efficient, idiomatic implementation? My brain goes straight to imperative and I'm struggling to learn a new approach.
              – EricP
              Nov 18 '18 at 16:36












            • @EricP for F# idiomatic way is to mix imperative and declarative code. Don't confuse F# with Haskell.
              – Szer
              Nov 22 '18 at 6:22


















            • I see that. Also, to be fair, Scott Wlaschin said it was a "crude implementation of a prime number sieve" and it was to find the first 25 primes and not the first 10k. The question still remains though, what is an efficient, idiomatic implementation? My brain goes straight to imperative and I'm struggling to learn a new approach.
              – EricP
              Nov 18 '18 at 16:36












            • @EricP for F# idiomatic way is to mix imperative and declarative code. Don't confuse F# with Haskell.
              – Szer
              Nov 22 '18 at 6:22
















            I see that. Also, to be fair, Scott Wlaschin said it was a "crude implementation of a prime number sieve" and it was to find the first 25 primes and not the first 10k. The question still remains though, what is an efficient, idiomatic implementation? My brain goes straight to imperative and I'm struggling to learn a new approach.
            – EricP
            Nov 18 '18 at 16:36






            I see that. Also, to be fair, Scott Wlaschin said it was a "crude implementation of a prime number sieve" and it was to find the first 25 primes and not the first 10k. The question still remains though, what is an efficient, idiomatic implementation? My brain goes straight to imperative and I'm struggling to learn a new approach.
            – EricP
            Nov 18 '18 at 16:36














            @EricP for F# idiomatic way is to mix imperative and declarative code. Don't confuse F# with Haskell.
            – Szer
            Nov 22 '18 at 6:22




            @EricP for F# idiomatic way is to mix imperative and declarative code. Don't confuse F# with Haskell.
            – Szer
            Nov 22 '18 at 6:22


















            draft saved

            draft discarded




















































            Thanks for contributing an answer to Stack Overflow!


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.





            Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


            Please pay close attention to the following guidance:


            • Please be sure to answer the question. Provide details and share your research!

            But avoid



            • Asking for help, clarification, or responding to other answers.

            • Making statements based on opinion; back them up with references or personal experience.


            To learn more, see our tips on writing great answers.




            draft saved


            draft discarded














            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53357139%2ff-idiomatic-performance%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown





















































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown

































            Required, but never shown














            Required, but never shown












            Required, but never shown







            Required, but never shown







            Popular posts from this blog

            How to change which sound is reproduced for terminal bell?

            Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents

            Can I use Tabulator js library in my java Spring + Thymeleaf project?