From: Max Motovilov (max_at_[hidden])
Date: 2008-03-12 21:21:15
Some final comments.
First, in the code I posted above "push_back< S, A>" should be replaced
with "push_front< S, A >", otherwise top-level sequence cannot be a list.
Second, while recursive implementation is very similar to the iterative,
it still generates the combinations in reverse order :) Not important
for applications I can think of, but still.
Finally, the performance comparison. I did it with GCC 4.2 on an Intel
dual core with 4G RAM running 64-bit Ubuntu Gutsy.
Iterative algorithm:
2^1 combinations: real 0m0.491s, user 0m0.432s, sys 0m0.048s
2^2 combinations: real 0m0.589s, user 0m0.488s, sys 0m0.084s
2^3 combinations: real 0m0.973s, user 0m0.624s, sys 0m0.060s
2^4 combinations: real 0m1.078s, user 0m0.824s, sys 0m0.120s
2^5 combinations: real 0m1.542s, user 0m1.424s, sys 0m0.092s
2^6 combinations: real 0m3.384s, user 0m3.012s, sys 0m0.212s
2^7 combinations: real 0m10.627s, user 0m8.781s, sys 0m0.320s
2^8 combinations: real 0m35.032s, user 0m33.582s, sys 0m0.652s
2^9 combinations: hit compiler limits, graceful exit
Recursive algorithm:
2^1 combinations: real 0m0.493s, user 0m0.420s, sys 0m0.072s
2^2 combinations: real 0m0.584s, user 0m0.480s, sys 0m0.100s
2^3 combinations: real 0m0.934s, user 0m0.716s, sys 0m0.076s
2^4 combinations: real 0m1.795s, user 0m1.408s, sys 0m0.088s
2^5 combinations: real 0m5.507s, user 0m4.740s, sys 0m0.192s
2^6 combinations: real 0m29.325s, user 0m27.294s, sys 0m0.584s
2^7 combinations: overwhelmed system resources after 5min, killed