[Newbies] Re: Another extension proposal -> subsets
cdrick65 at gmail.com
Fri Jul 25 08:07:26 UTC 2008
Yes.. Nico's solution is lot faster...
set := #(1 2 3 4 5) asSet.
[ set subsets "mine"] timeToRun ." 1"
[ set subsets2 "Zulk first" ] timeToRun. " 8"
[ set subsets4 "Nicolas"] timeToRun. " 1"
[ set subsets5 "Zulk"] timeToRun. " 2"
set := (1 to: 10) asSet.
[ set subsets ] timeToRun . " 46"
[ set subsets4 ] timeToRun. " 18"
[ set subsets5 ] timeToRun." 114"
set := (1 to: 15) asSet.
[ set subsets ] timeToRun ." 2484"
[ set subsets4 ] timeToRun. " 1598"
[ set subsets5 ] timeToRun." 12493"
Nicolas won ;) So maybe we can add this one and rename the
2008/7/25 Nicolas Cellier <ncellier at ifrance.com>:
> Klaus D. Witzel <klaus.witzel <at> cobss.com> writes:
>> On Thu, 24 Jul 2008 20:09:53 +0200, Zulq Alam wrote:
>> This is very good for small n :)
>> > combinations
>> > | combinations |
>> > combinations := (PluggableSet new: (2 raisedTo: self size))
>> > hashBlock:
>> > [:aSet |
>> > aSet
>> > inject: aSet size
>> > into: [:hash :each | hash * each hash + each]];
>> > yourself.
>> > self combinationsInto: combinations.
>> > ^ combinations
>> > combinationsInto: aSet
>> > (aSet includes: self) ifTrue: [^ self].
>> > aSet add: self.
>> > self do:
>> > [:each |
>> > (self copyWithout: each) combinationsInto: aSet].
>> > Even now, I'm still not clear on how one takes a change like this and
>> > drives it into a squeak release - Tests, Mantis, then what?
>> Put it on Mantis as enhancement into the collection category. The rest
>> follows automatically ;) I suggest to put something like "fast powerset
>> method for collections" into the summary line.
>> > Z.
> 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
> (2 raisedTo: 10) -> 1024
> (10 factorial) -> 3628800
> 2) each loop will result in a costly hash lookup.
> Your hashBlock involve LargeInteger of size (B raisedTo: p) where
> - B is the size of an elementary hash (presumably 4 bytes),
> - p the size of the partition (ranging from 0 to n)
> The cost of a single hash of size p involves p multiplications of growing size.
> Each multiplication of k digits has a cost k^2
> (this is the naive algorithm currently programmed in LargeInteger plugin).
> Thus a single hash costs (B^2+(2*B)^2+...+(p*B)^2)
> Combine this with the (n factorial) loops and you will understand the problem.
> 3) the algorithm must store all partitions even if we don't want to collect but
> just to iterate on partitions.
> No offense, but you'd better not bother opening a mantis issue for this time.
> Beginners mailing list
> Beginners at lists.squeakfoundation.org
More information about the Beginners