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 _______________________________________________ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners