[Haskell-cafe] Can Haskell outperform C++?

[Richard O'Keefe]

On 17/05/2012, at 2:04 PM, Gregg Lebovitz wrote:

> Richard,
> 
> Thank you. This is an example of what I had in mind when I talked about changing the playing field. Do you have a slide deck for this lecture that you would be willing to share with me? I am very interested in learning more.


No slide deck required.  The task is "generating alternating permutations".

Method 1: generate permutations using a backtracking search;
          when a permutation is generated, check if it is alternating.

Method 2: use the same backtracking search, but only allow extensions
	  that preserve the property of being an alternating permutation.

For n=12 the second method is 94 times faster than the first, and the
ratio increases with growing n.  At the time I wrote the program I had not
heard of Bauslaugh and Ruskey's constant-average-time algorithm for generating
alternating permutations.  Experimentally the Method 2 backtracking search
appears to take constant time per solution anyway.

 n (time ms):       En         n!

 1 (    0.0):        1          1      <- method 1
 1 (    0.0):        1                 <- method 2
 2 (    0.0):        1          2
 2 (    0.0):        1
 3 (    0.0):        2          6
 3 (    0.0):        2
 4 (    0.0):        5         24
 4 (    0.0):        5
 5 (    0.0):       16        120
 5 (    0.0):       16
 6 (    0.1):       61        720
 6 (    0.0):       61
 7 (    0.6):      272       5040
 7 (    0.1):      272
 8 (    4.4):     1385      40320
 8 (    0.3):     1385
 9 (   35.2):     7936     362880
 9 (    1.4):     7936
10 (  359.7):    50521    3628800
10 (    9.3):    50521
11 ( 4035.7):   353792   39916800
11 (   67.0):   353792
12 (49584.6):  2702765  479001600      <- method 1
12 (  528.1):  2702765                 <- method 2

Those times are in C; SWI Prolog (which compiles to an abstract instruction
set that is then interpreted by portable C) was about 24 times slower.
A factor of 94 comfortably exceeds a factor of 24...