[Newbies] Re: Another extension proposal - subsets
Actually, we don't need #permutationsDo: as we're only looking for combinations. With a few optimisations: combinations ^ self combinationsInto: (Set new: (2 raisedTo: self size)) combinationsInto: aSet (aSet includes: self) ifTrue: [^ self]. optimisation aSet add: self. self do: [:each | (self copyWithout: each) combinationsInto: aSet]. ^ aSet [(1 to: 8) asSet combinations] timeToRun 215 [(1 to: 9) asSet combinations] timeToRun 918 [(1 to: 10) asSet combinations] timeToRun 3989 [(1 to: 11) asSet combinations] timeToRun 16349 [(1 to: 12) asSet combinations] timeToRun 68780 So a little better, but I was expecting much more. What's worrying is this: (1 to: 10) asSet combinations size 1024 ((1 to: 10) asSet combinations collect: [:e | e hash]) asSet size 16 So, 1024 distinct Sets have only 16 distinct hashes between them? That seems pretty bad. It would probably be possible to get a little bit more out of the routine with a better (more appropriate) hash function. Even so, I don't think it will ever be as fast as your method but will happily be proved wrong! :) Z. cdrick wrote: Setsubsets | subsets | subsets := Set with: self. self asArray permutationsDo: [:e | subsets add: e asSet]. self do: [:e | subsets addAll: (self copyWithout: e) subsets]. ^ subsets nice too and frustrating how you got it quick :) I tried a recursive method too first but found the byte ressemblance so... My only consolation is that the recursive solution (subsets2) is slower and hardly work for Set with more than 10 elements. set := #(1 2 3 4 5) asSet. [ set subsets ] timeToRun . 1 [ set subsets2 ] timeToRun. 8 set := #(1 2 3 4 5 6 7) asSet. [ set subsets ] timeToRun . 5 [ set subsets2 ] timeToRun. 233 set := #(1 2 3 4 5 6 7 8 ) asSet. [ set subsets ] timeToRun . 11 [ set subsets2 ] timeToRun. 1683 set := (1 to: 10) asSet. [ set subsets ] timeToRun . 46 set := (1 to: 15) asSet. [ set subsets ] timeToRun . 2484 set := (1 to: 20) asSet. [ set subsets ] timeToRun . 559953 but here the result has (2 raisedTo: 20) 1 048 576 Sets :) set := (1 to: 50) asSet. [ set subsets ] timeToRun .I got a space is low wow :) I have to go, That was fun :) See you Cédrick ___ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners ___ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Re: [Newbies] Re: Another extension proposal - subsets
or withNicolas suggestion: SetasPowerset | subset | subset := (OrderedCollection new: (2 raisedTo: self size)) add: Set new; yourself. 1 to: self size do: [:subSize | don't copy anymore as there is the Set conversion self asArray combinations: subSize atATimeDo: [:subArray | subset add: subArray asSet]]. ^ subset asSet I'd still prefer #combinationsSize:do: instead of#combinations:atATimeDo: How about naming Collection#asPowerset ^ self asSet powersetInto: (Set new: (2 raisedTo: self size)) with Set#powersetInto: and putting that into the next release. /Klaus ___ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
[Newbies] Re: Another extension proposal - subsets
On Thu, 24 Jul 2008 18:27:48 +0200, Cedrick wrote: or withNicolas suggestion: SetasPowerset | subset | subset := (OrderedCollection new: (2 raisedTo: self size)) add: Set new; yourself. 1 to: self size do: [:subSize | don't copy anymore as there is the Set conversion self asArray combinations: subSize atATimeDo: [:subArray | subset add: subArray asSet]]. ^ subset asSet Ah, you francophones always want to see Blaise Pascal's triangle at work ;) Didn't check #combinations:* implementation, does it avoid #includes: ? I'd still prefer #combinationsSize:do: instead of #combinations:atATimeDo: +1 but it looks alt-w friendly already (like #detectSum: looks ;) How about naming Collection#asPowerset ^ self asSet powersetInto: (Set new: (2 raisedTo: self size)) with Set#powersetInto: and putting that into the next release. /Klaus ___ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Re: [Newbies] Re: Another extension proposal - subsets
Didn't check #combinations:* implementation, does it avoid #includes: ? I think so. It calls #combinationsAt:in: after: do: wich is recursive. I'd still prefer #combinationsSize:do: instead of #combinations:atATimeDo: +1 but it looks alt-w friendly already (like #detectSum: looks ;) Funny to see it was probably the original name. See the comment of #combinationsAt:in: after: (last line) Choose k of N items and put in aCollection. jj-1 already chosen. Indexes of items are in numerical order, to avoid the same combo being used twice. In this slot, we are allowed to use items in self indexed by nn+1 to self size. nn is the index used for position jj-1. (1 to: 6) combinationsSize: 3 do: [:each | Transcript cr; show: each printString] Cédrick How about naming Collection#asPowerset ^ self asSet powersetInto: (Set new: (2 raisedTo: self size)) with Set#powersetInto: and putting that into the next release. /Klaus ___ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners ___ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
Re: [Newbies] Does Plopp use Morphic?
Am 23.07.2008 um 23:36 schrieb Andy Burnett: I have just started playing with Plopp (very impressive). The reason I downloaded it was to see the sort of interfaces that people could build in Squeak. What I am wondering is whether the UI is built on top of Morphic, or whether it is completely different. Does anyone know? The 2D UI is Tweak, the 3D rendering Croquet. I'm pretty sure you could do the same kind of UI in Morphic though. Just hire great designers ;) - Bert - ___ Beginners mailing list Beginners@lists.squeakfoundation.org http://lists.squeakfoundation.org/mailman/listinfo/beginners
[Newbies] Re: Another extension proposal - subsets
Klaus D. Witzel wrote:
Squeak looks to be already fast in this case, your routine is almost
optimal :) Implementing it in Set so that Set's internal can be of
benefit won't bring these figures down much -- what remains is (aSet
includes: another), times #copyWithout: loop, and that seems to be
unavoidable.
It's significantly faster with a more appropriate hashing function:
{2-0 . 3-0 . 4-1 . 5-1 . 6-3 . 7-9 . 8-22 . 9-59 . 10-138 .
11-305 . 12-686 . 13-1640 . 14-4366 . 15-10550 . 16-28104 .
17-93373 . 18-303425}
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].
I think the problem is that most of the sets contain similar data so the
hashes (calculated with bitXor) tend towards to a small set of values.
This means there are a lot of collisions and each #add: and #includes:
is very expensive.
How about naming
Collection#asPowerset
^ self asSet powersetInto: (Set new: (2 raisedTo: self size))
with Set#powersetInto: and putting that into the next release.
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?
Z.
___
Beginners mailing list
Beginners@lists.squeakfoundation.org
http://lists.squeakfoundation.org/mailman/listinfo/beginners
