F# performance bug?
let test1fun x = [for i in 1..x-> i]
let test2fun x y= [for i in 1..x
do for i in 1..y-> i]
let singlesearcher i =
let rec searcher j agg =
if j > i
then agg
else searcher (j+1) (i::agg)
searcher 1 []
let doublesearcher i j =
le开发者_如何学编程t rec searcher k l agg =
if k > i
then searcher 1 (l+1) agg
else if l > j
then agg
else searcher (k+1) l ((k,l)::agg)
searcher 1 1 []
executing the above with #time and 10000 for all inputs yields
list comprehension/singlesearcher-> negligable
cross product -> 320
list comprehension crossproduct -> 630
Why is the nested list comprehension more than twice the the functional version?
Yes. List comprehension is usually slower than directly using F# list or array. (On my machine, I also find similar timing with you.)
Let's look into how they are implemented. The list comprehension version is actually quite complicated:
a sequence/
IEnumerable<int>
is created using the comprehension syntax. This is just a lazy sequence, little time is spent here.then this sequence is transformed into F# List by using something like
Seq.toList
. The actual time is spent here. There are a lot ofHasNext
MoveNext
andswitch (state)
like code executed here. With so many function calls, you cannot expect it fast.
While the functional version doublesearcher
is properly optimized into a tail recursion. This is a more direct version than list comprehension, and few function calls are used therein.
Usually we don't care these small performance difference for sequence, lists or arrays if the operation is not very critical. I think in your example, the generation is anyway one-time. The two time timing is not a big problem. For other cases, e.g. the dot product of two vectors, using arrays could save a lot of time because this operation is executed for a lot of times.
精彩评论