On Nov 28, 2007, at 10:37 PM, Xavier Noria wrote:
On Nov 28, 2007, at 9:54 PM, Xavier Noria wrote:
On Nov 28, 2007, at 8:58 PM, yitzle wrote:
In a personal email conversation, he realized what he was actually
looking for is the power set.
List::PowerSet
http://search.cpan.org/~nikc/List-PowerSet-0.01/lib/List/PowerSet.pm
If speed is an issue Algorith::Combinatorics provides subsets() in
XS:
I had done some benchmarks which are included in the distribution
but not this one.
I've found that List::PowerSet outperforms Algorithm::Combinatorics'
subset(). Time to revise that subroutine.
Indeed, the iterator provided by Algorithm::Combinatorics is faster
only for lists of sizes >= 7. (And gets to be twice as fast for size
16.)
The subroutine that gives you all the subsets in one shot has its own
implementation in List::PowerSet (it is not a wrapper around the
iterator). It is recursive and fast, and clever! I think it is that
fast because it actually runs basically in C:
[ map { [$first, @$_ ], [ @$_] } @$pow ];
given that map is an opcode.
For that call Algorithm::Combinatorics matches and performs slighly
better than List::PowerSet from size 14 on. I guess that's because it
creates less intermediate stuff.
Certainly there's room for improvement here.
-- fxn
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
http://learn.perl.org/
