I compared Haskell to C++ on the Criptarithm solver
suggested several days ago by
Mark Engelberg <[EMAIL PROTECTED]>.
C++ was 17 times faster than ghc-4.04. (I expected 10 times).
The compilation keys were g++ -O2
ghc -c -fvia-C -O2 -O2-for-C
Here is the story.
Mark Engelberg spoke of the task of finding first permutation,
satisfying certain equation.
And he compared the Haskell program with the C++ program that uses
the next_permutation function.
Now, for the correct comparison, we reformulate slightly the program
`find':
find in the generated list the first permutation equal to
[9,8,7,6,5,4,3,2,1,0].
As it is easy to test, both the below Haskell program and
next_permutation from C++ library generate the permutations
starting with [0..9] and ending with [9,8,7,6,5,4,3,2,1,0].
Hence, both programs test each permutation on 10 elements.
As to me, i still agree to pay 17 times for the functionality.
But is the test all right, what people think?
How do you think, next_permutation - is it compiled from C,
or written in assembly?
And what about Mercury, or others?
------------------
Sergey Mechveliani
[EMAIL PROTECTED]
-- Haskell ---------------------------------------------------------
import List (find)
permutations :: [Int] -> [[Int]]
-- build the full permutation list given an ordered list
permutations [] = [[]]
permutations (j:js) = addOne $ permutations js
where
addOne [] = []
addOne (ks:pms) = (ao ks)++(addOne pms)
ao [] = [[j]]
ao (k:ks) = (j:k:ks):(map (k:) $ ao ks)
main = let xs = [0..9]
rxs = reverse xs
in
putStr $ shows (find (== rxs) $ permutations xs) "\n"
-- C++ ----------------------------------------------------------
#include <vector>
#include <algorithm>
#include <iostream.h>
using namespace std;
void main()
{
long t,h,i,r,y,w,e,l,v,n;
long temp[10] = {0,1,2,3,4,5,6,7,8,9};
vector<long> x(temp,temp+10);
while (1)
{
if (x[0]==9 & x[1]==8 & x[2]==7 & x[3]==6 & x[4]==5 & x[5]==4 &
x[6]==3 & x[7]==2 & x[8]==1 & x[9]==0
) break;
next_permutation(x.begin(), x.end());
}
cout << x[0] << x[1] << x[2] << x[3] << x[4] << x[5] << x[6] <<
x[7] << x[8] << x[9] << '\n';
}
