Your F# code is generating and then iterating a lot of IEnumerables that the C# code does not. Every call to isDivOneToTwenty generates a new IEnumerable and then iterates it to find the length, and also iterates the "divisors" sequence as well.
On my machine your F# code takes about 35 seconds. This following version takes 22 seconds. All I changed was generating "divisors" as an array (because arrays are more efficient than lists at storing value types, and because it's faster to get the length of an array than a sequence). I also generated the array in reverse order, rather than generating it and then reversing it, and I cached the count rather than recalculate it every time.
This is faster, but it's still generating and iterating an IEnumerable every time through the loop. It could be made faster yet by making the code more imperative and less functional. This is a strength of F#, in that you have the flexibility to optimize specific functions, while isolating your imperative code in such a way that it doesn't affect the rest of your program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
let p5BruteForce2 = let divisors = [| 20 .. -1 .. 3 |] let divisorCount = Array.length divisors let isDivOneToTwenty n = let dividesBy = divisors |> Seq.takeWhile (fun x -> n % x = 0) Seq.length dividesBy = divisorCount let findNum n = let rec loop n = match isDivOneToTwenty n with | true -> n | false -> loop (n + 2) loop n findNum 2520
Thanks to your help I was able to make further optimizations and eliminate the length comparison completely by using List.forall instead (I tried changing the List to an array but this yielded no performance boost on my computer).
Anyhow, this new code finishes in 2500ms on my machine down from 45k ms :).
1 2 3 4 5 6 7 8 9 10 11
let p5BruteForce = let divisors = [20..-1..3] let isDivOneToTwenty n = divisors |> List.forall (fun x -> n % x = 0) let findNum n = let rec loop n = match isDivOneToTwenty n with | true -> n | false -> loop (n + 2) loop n findNum 2520
Alternatively (leaving the "brute-force" world) you could note that what is asked is to calculate the least common multiple of the range [ 1 .. 20 ] (or [ 2 .. 20 ] because lcm(1, x) = x)
1 2 3 4 5 6 7 8 9 10 11
let rec gcd x y = if y = 0 then abs x else gcd y <| x % y let lcm x y= // do division first to limit overflow risk x / gcd x y * y let p5 = [ 2 .. 20 ] |> List.reduce lcm // alternate version using statement knowledge let p5' = [ 11 .. 20 ] |> List.fold lcm 2520
Topic tags
- f# × 3687
- compiler × 265
- functional × 201
- websharper × 175
- c# × 120
- classes × 97
- web × 96
- book × 84
- .net × 82
- async × 72
- parallel × 43
- server × 43
- parsing × 41
- testing × 41
- asynchronous × 30
- monad × 28
- ocaml × 28
- haskell × 26
- tutorial × 26
- html × 23
- workflows × 22
- linq × 21
- fpish × 19
- introduction × 19
- silverlight × 19
- wpf × 19
- collections × 14
- pipeline × 14
- templates × 12
- monads × 11
- opinion × 10
- reactive × 10
- sitelets × 10
- plugin × 9
- scheme × 9
- solid × 9
- basics × 8
- concurrent × 8
- deployment × 8
- how-to × 8
- javascript × 8
- jquery × 8
- python × 8
- complexity × 7
- lisp × 6
- real-world × 6
- scala × 6
- workshop × 6
- xaml × 6
- conference × 5
- dsl × 5
- java × 5
- metaprogramming × 5
- ml × 5
- piglets × 5
- sitelet × 5
- sql × 5
- visual studio × 5
- formlets × 4
- fsi × 4
- lift × 4
- teaching × 4
- ui.next × 4
- alt.net × 3
- aml × 3
- enhancement × 3
- erlang × 3
- highcharts × 3
- list × 3
- piglet × 3
- reflection × 3
- type provider × 3
- azure × 2
- blog × 2
- clojure × 2
- compilation × 2
- computation expressions × 2
- corporate × 2
- courses × 2
- cufp × 2
- enterprise × 2
- entity framework × 2
- events × 2
- f# interactive × 2
- fsc × 2
- google maps × 2
- hosting × 2
- html5 × 2
- http × 2
- interactive × 2
- interface × 2
- iphone × 2
- iteratee × 2
- jobs × 2
- kendo × 2
- keynote × 2
- mvc × 2
- numeric × 2
- obfuscation × 2
- oop × 2
- packaging × 2
- pattern matching × 2
- performance × 2
- pipelines × 2
- rest × 2
- rx × 2
- script × 2
- seq × 2
- sockets × 2
- stm × 2
- tcp × 2
- trie × 2
- type × 2
- typescript × 2
- xna × 2
- zh × 2
- .net interop × 1
- 2012 × 1
- abstract class × 1
- accumulator × 1
- active pattern × 1
- actor × 1
- addin × 1
- agents × 1
- agile × 1
- alter session × 1
- android × 1
- anonymous object × 1
- appcelerator × 1
- architecture × 1
- array × 1
- arrays × 1
- asp.net 4.5 × 1
- asp.net integration × 1
- asp.net mvc × 1
- asp.net mvc 4 × 1
- asp.net web api × 1
- aspnet × 1
- ast × 1
- b-tree × 1
- badimageformatexception × 1
- batching × 1
- bistro × 1
- bootstrap × 1
- bug × 1
- bundle × 1
- camtasia studio × 1
- canvas × 1
- class × 1
- client × 1
- clojurescript × 1
- closures × 1
- cloud × 1
- cms × 1
- coding diacritics × 1
- color highlighting × 1
- combinator × 1
- confirm × 1
- constructor × 1
- continuation-passing style × 1
- coords × 1
- coursera × 1
- csla × 1
- css × 1
- current_schema × 1
- custom content × 1
- data × 1
- database × 1
- datetime × 1
- declarative × 1
- delete × 1
- dhtmlx × 1
- discriminated union × 1
- disqus × 1
- distance × 1
- docs × 1
- documentation × 1
- dol × 1
- dom × 1
- domain × 1
- du × 1
- duf-101 × 1
- eclipse × 1
- edsl × 1
- em algorithm × 1
- emacs × 1
- emotion × 1
- error × 1
- etw × 1
- euclidean × 1
- event × 1
- example × 1
- examples × 1
- ext js × 1
- extension methods × 1
- extra × 1
- facet pattern × 1
- fantomas × 1
- fear × 1
- float × 1
- flowlet × 1
- fp × 1
- frank × 1
- fsdoc × 1
- fsharp.core × 1
- fsharp.powerpack × 1
- fsharpx × 1
- function × 1
- functional style × 1
- game × 1
- games × 1
- gc × 1
- generic × 1
- geometry × 1
- getlastwin32error × 1
- getting started × 1
- google × 1
- group × 1
- hash × 1
- hello world example × 1
- history × 1
- httpcontext × 1
- https × 1
- hubfs × 1
- ie 8 × 1
- if-doc × 1
- iis 8.0 × 1
- inheritance × 1
- installer × 1
- interfaces × 1
- interpreter × 1
- io × 1
- iobservable × 1
- ios × 1
- ipad × 1
- issue × 1
- jqueryui × 1
- kendochart × 1
- kendoui × 1
- learning × 1
- license × 1
- licensing × 1
- linux × 1
- macro × 1
- macros × 1
- maps × 1
- markerclusterer × 1
- markup × 1
- marshal × 1
- math × 1
- message × 1
- message passing × 1
- message-passing × 1
- metro style × 1
- micro orm × 1
- minimum-requirements × 1
- module × 1
- mono × 1
- msbuild × 1
- multidimensional × 1
- multiline × 1
- multithreading × 1
- mysql × 1
- mysqlclient × 1
- nancy × 1
- native × 1
- nested × 1
- nested loops × 1
- node × 1
- object relation mapper × 1
- object-oriented × 1
- offline × 1
- om × 1
- option × 1
- orm × 1
- osx × 1
- owin × 1
- paper × 1
- parameter × 1
- persistent data structure × 1
- phonegap × 1
- pola × 1
- powerpack × 1
- prefix tree × 1
- principle of least authority × 1
- programming × 1
- project euler × 1
- projekt_feladat × 1
- protected × 1
- provider × 1
- ptvs × 1
- quant × 1
- quotations × 1
- range × 1
- raphael × 1
- razor × 1
- rc × 1
- reactjs × 1
- real-time × 1
- reference × 1
- remote × 1
- remoting × 1
- rest sitelet × 1
- restful × 1
- round table × 1
- routing × 1
- rpc × 1
- runtime × 1
- scriptcs × 1
- scripting × 1
- service × 1
- session-state × 1
- sitelet website × 1
- sitlets × 1
- sqlentityconnection × 1
- standards × 1
- stickynotes × 1
- stress × 1
- strong name × 1
- structures × 1
- svg × 1
- targets × 1
- tdd × 1
- template × 1
- text parsing × 1
- time travel × 1
- tracing × 1
- tsunamiide × 1
- type inference × 1
- type providers × 1
- typeprovider × 1
- upload × 1
- url × 1
- vb × 1
- vb.net × 1
- vector × 1
- view.map × 1
- visal studio × 1
- visual f# × 1
- visual studio 11 × 1
- visual studio 2012 × 1
- visual studio shell × 1
- visualstudio × 1
- web api × 1
- webapi × 1
- webshaper × 1
- websharper f# google × 1
- windows 7 × 1
- windows 8 × 1
- windows-phone × 1
- winrt × 1
- xml × 1
- yield × 1
- zarovizsga × 1
Copyright (c) 2024 IntelliFactory. All rights reserved. | | | Trainings | | | |
Built with |
I'm very new to functional programming coming from C#. I'm tackling the Project Euler problems again (did the 23 first ones before when I was learning C#) and I'm quite baffled at the subpar performance of my solution to problem 5.
It reads as follow:
Now my incredibly primitive brute-force solution of C# tugs through this problem in roughly 25 seconds.
Now my F# solution uses brute forcing as well but at least it does a bit more discrimination and such so that it "should" in my mind run faster but it clocks out at ~45 secs so it's nearly twice as slow as the C# one.