[Newbies] Re: Another extension proposal -> subsets

nicolas cellier ncellier at ifrance.com
Fri Jul 25 09:23:57 UTC 2008


Zulq Alam <me <at> zulq.net> writes:

> 
> Nicolas Cellier wrote:
> 
> > Zulq,
> > the algorithm you are proposing is very simple but has major problems:
> > 
> > 1) it is not efficient for large size n: it will do (n factorial) loops when
> > only (2 raisedTo: n) are necessary
> 
> It's better than N! because it will not loop over a set already 
> processed. For instance, for a set of 5 elements it will try 81 sets but 
> only process 32 of these. Not 120 in either case (5 factorial).
> 

Apologies for this case of blindness!
I forgot the includes: test was cutting branches.

> > 
> > 2) each loop will result in a costly hash lookup.
> > Your hashBlock involve LargeInteger of size (B raisedTo: p) where
> 
> It doesn't need to. That was just a very rough attempt at producing a 
> hash that didn't evaluate to only 16 values. It should be possible to 
> create one that produces SmallIntegers but with a higher cardinality.
> 

Yes, modular arithmetic would be a way to go.
Beware, "small" LargeIntegers intermediate might still spoil the game...
Crafting a good hash is an art (see work from Andres Valloud).

> > 3) the algorithm must store all partitions even if we don't want to collect
 but
> > just to iterate on partitions.
> 
> Yes.
> 
> > 
> > No offense, but you'd better not bother opening a mantis issue for this
 time.
> > 
> 
> Agreed. I was just curious about why the naive algorithm was so slow and 
> then as a seperate question how one gets such changes in.
> 
> Z.
> 

Right, you did a good job exercizing your (and our) curiousity.
This is very enlightening.
Beginners should also learn using MessageTally spyOn: [],
to analyze were the real costs go.

Cheers



More information about the Beginners mailing list