F# Idiomatic Performance
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)
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
add a comment |
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)
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
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 atprimes
F# sequence definition from this SO answer. I believeprimes |> 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
add a comment |
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)
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
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)
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
performance f# idiomatic imperative
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 atprimes
F# sequence definition from this SO answer. I believeprimes |> 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
add a comment |
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 atprimes
F# sequence definition from this SO answer. I believeprimes |> 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
add a comment |
2 Answers
2
active
oldest
votes
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.
add a comment |
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 )
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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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.
add a comment |
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.
add a comment |
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.
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.
answered Nov 18 '18 at 23:53
Ringil
3,46021025
3,46021025
add a comment |
add a comment |
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 )
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
add a comment |
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 )
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
add a comment |
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 )
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 )
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
add a comment |
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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
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 believeprimes |> 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