Huddled Masses
Posts Tagged ‘Fibonacci’
February 4th, 2008 | 
Author: So, I posted a story about Fibonacci sequences and noticed that the recursion in PowerShell is really rather slow. But I also noticed something interesting — I had expected that recursing using a function would be a little cheaper (and faster) than recursing using the pipeline, and it turns out that it’s not. At all.
I’d love to hear some thoughts on why I got the speed results I got here. At first I thought it was something about type coercion, but as you can see, I tried casting everything to no avail. There’s no difference if I don’t output anything, and in fact, the non-recursive algorithm can trivially output every Fibonacci number in the sequence without affecting it’s time (I actually altered it so it didn’t to keep the output clean).
Obviously I expected the recursive algorithms to be slow and scale badly because of the amount of work involved, but how is it that the pipeline-recursive “filter” outperforms the plain old recursive function (albeit by an infinitesimal fraction)?
[08]: function fibfunction([int]$i){ if($i -lt 2) { 1 }else{ [int](fibfunction ($i-1)) + [int](fibfunction ($i-2)) } }
[09]: filter fibfilter{ if($_-lt2){1}else{[int]([int]$_-1|fibfilter)+[int]([int]$_-2|fibfilter)}}
[10]: [int]$size = 18
[11]: fibfunction $size
4181
[12]: $size | fibfilter
4181
[13]: [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
4181
[14]: get-history -count 3 | fl CommandLine,@{l="Duration"; e={$_.EndExecutionTime - $_.StartExecutionTime}}
CommandLine : fibfunction $size
Duration : 00:00:02.4764040
CommandLine : $size | fibfilter
Duration : 00:00:02.2137255
CommandLine : [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
Duration : 00:00:00.0048825
[15]: [int]$size = 21
[16]: fibfunction $size
17711
[17]: $size | fibfilter
17711
[18]: [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
17711
[19]: get-history -count 3 | fl CommandLine,@{l="Duration"; e={$_.EndExecutionTime - $_.StartExecutionTime}}
CommandLine : $null = fibfunction $size
Duration : 00:00:10.5764715
CommandLine : $null = $size | fibfilter
Duration : 00:00:09.6282900
CommandLine : $null = [int]$a,[int]$b = 0,1; 0..$size|%{$a,$b = ($a+$b),$a}; $a
Duration : 00:00:00.0058590
P.S.: The numbers in braces with the colon (like [18]: ... ) is my prompt.
Posted in Huddled | 
Tags: Fibonacci, Performance, PowerShell, Recursion, Scripting, Timing | 
4 Comments »
Scott Hanselman has been posting weekly snippets of code in various languages … today he did Fibonacci sequences … by the way, the point of his posts is to get you to read code in other languages, not necessarily showing the best way to do things in any of the languages represented — you only solve fibonacci sequences recursively in demos, not in real life. Well, except perhaps in tightly optimized tail-recursion languages, maybe in Haskell …
In C#
int fib(int x) { return (x<2) ? 1 :fib(x-1) + fib(x-2) }
fib(20);
In PowerShell
filter fib{ if($_-lt2){1}else{($_-1|fib)+($_-2|fib)}}
20 | fib
That’s just beautiful 
... incidentally, by default, PowerShell will only recurse up to 100 levels in the stack, so it kind-of sucks at recursive calls. You could also write that as a traditional function in powershell, but the way powershell passes arguments to functions makes it really awkward. I’ll put it on multiple lines so you can read it easier.
function fib($i){
if($i -lt 2) {
1
}else{
# yes, every one of these parentheses is required
(fib ($i-1)) + (fib ($i-2))
}
}
fib 20
As a side note, that function actually runs measurably slower than the pipeline method … but speeds up noticeably if you stick a few [int] type specifiers in the right places so PowerShell doesn’t have to infer types — something to think about.