I would be curious to see the average length of dictionary keys (except Smalltalk) and see the performance penalty between set and array for the do: Stef
2009/12/4 Lukas Renggli <renggli@gmail.com>:
Actually the code can be further optimized:
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result container | result := Set basicNew setTally: tally array: array copy. container := result array. 1 to: container size do: [ :index | (container at: index) ifNotNil: [ :assoc | container at: index put: assoc key ] ]. ^ result
This is roughly 22 times faster than the current implementation, and 5 times faster than the squeak implementation.
The system doesn't seem to break with this change :-)
Lukas
Yes Levente considered this implementation as keysAsSet, but did not pushed it in trunk so far. You must also consider that each further usage of a Set will add a performance penalty vs an Array, especially do:
Nicolas
2009/12/4 Lukas Renggli <renggli@gmail.com>:
I wonder if ever something along the following lines was considered?
Dictionary>>keys "Answer a Set containing the receiver's keys."
| result | result := Set basicNew. result setTally: tally array: (array collect: [ :each | each isNil ifFalse: [ each key ] ]). ^ result
This returns a Set, so it wouldn't break any semantics. In my benchmark this is roughly 8x faster than the current implementation, and 2x faster than the optimized Squeak implementation.
The drawback is that it makes some heavy assumptions on the internal structure of Dictionary, Association and Set.
Lukas
2009/12/4 Henrik Sperre Johansen <henrik.s.johansen@veloxit.no>:
A small addendum ;) On 03.12.2009 22:13, Nicolas Cellier wrote:
3) identify thise sending a potential inefficient message (includes:) insert keys asSet in this case (only if includes: is in a loop!)
3b. If the keys collection isn't used for anything else, change to use includesKey: instead.
Cheers, Henry
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- Lukas Renggli http://www.lukas-renggli.ch
-- Lukas Renggli http://www.lukas-renggli.ch
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project