To my letter on the Cryptarithm test
(proposed by Mark Engelberg <[EMAIL PROTECTED]> )
>> [..]
>> As to me, i still agree to pay 17 times for the functionality.
>> But is the test all right, what people think?
>> And he compared the Haskell program with the C++ program that uses
>> the next_permutation function.
>> [..]
Manuel M. T. Chakravarty <[EMAIL PROTECTED]> writes
> If you don't know the implementation of next_permutation,
> how can you ensure that both programs actually go through
> the same sequence of permutations. Depending on the two
> algorithms involved one program may do a single permutation
> to reach the goal and the other program 1000 permutations.
> This has nothing to do with the programming languages
> involved.
No.
There are 10! = 3628800 permutations on [0..9].
Both the C++ program and the Haskell one start with p0 = [0..9]
- this is tested by inserting of printing into C++ program.
Then, i inserted the counter, and it shows that the permutation
No 3628800 (the last one) is reverse [0..9].
The Haskell program acts the same.
So, there is no need to investigate further this next_permutation
(unless it is written by hand in assembly! - hardly so).
It is hard to imagine next_permutation so treacherous as to
generate in the middle a great number of wrong permutations.
Both programs go through the same list of permutations.
Only i improved the test now to more fair (to my mind).
Now it shows the ratio * 6 *.
I wonder, what might this all mean. There remain minor questions.
The test is:
generate all the permutations starting from p0 = [0..9] and
ending with pLast = reverse [0..9], and find the first
permutation p among them satisfying `condition',
condition p = all (< 20) p && p==pLast
`condition' is set so that only the last permutation would suffice
it.
Also for each p it runs testing p(i) < 20 for i <- [0..9],
and only then proceeds with p==pLast.
This aims to deminish the relative cost of `(ao ks)++'.
For the latter costs 5 operations on average, while p==pLast
costs 1-2 operations on average
(and i do not know how to get free of this `++', neither how to
measure its cost by experiment).
This makes the program to do something with the permutation that
costs near the same as to generate the next permutation.
I think this example is a more real one.
In the C program, the functions condition1(x), condition2(x)
are introduced for the vector x, which correspond to
`all (< 20) p', `p==pLast' respectively.
These functions are programmed explicitly, as the cycles for i
from 0 to 9. This is to uniform it with the Haskell program.
Compilation: g++ -O3 t.cc
ghc-4.04 -c -fvia-C -O2 -O2-for-C t.hs
RESULT: C++ is 6 times faster.
Platform: PC i-586, Linux Debian
g++ version:
g++ -v says
`gcc version egcs-2.90.29 980515 (egcs-1.0.3 release)'
But this mess with platforms and versions, is not, probably, so
important, because people can compile and run this program in their
own environments - and correct the performance result.
What do you think of it?
------------------
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 = putStr $ shows (find condition $ permutations p0) "\n"
where
(p0, pLast) = ([0..9], reverse [0..9])
condition p = all (< 20) p && p==pLast
-- C++ -------------------------------------------------------------
#include <vector>
#include <algorithm>
#include <iostream.h>
using namespace std;
int condition1 (vector<long> x)
{int i = 0;
while (i < 10 & x[i] < 10) i++;
return (i > 9);
}
int condition2 (vector<long> x)
{int i = 0;
while ( i < 20 & x[i]==9-i ) i++;
return (i > 9);
}
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 (!(condition1(x) & condition2(x)))
{
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';
}
