[Python-Dev] When do sets shrink? (original) (raw)

Donovan Baarda abo at minkirri.apana.org.au
Thu Dec 29 17:52:28 CET 2005

On Thu, 2005-12-29 at 17:17 +0100, Fredrik Lundh wrote:

Noam Raphael wrote:

> I'm not saying that practically it must be used - I'm just saying that > it can't be called a heuristic, and that it doesn't involve any "fancy > overkill size hinting or history tracking". It actually means > something like this: > 1. If you want to insert and the table is full, resize the table to > twice the current size. > 2. If you delete and the number of elements turns out to be less than > a quarter of the size of the table, resize the table to half of the > current size. sure sounds like a heuristic algorithm to me... (as in "not guaranteed to be optimal under all circumstances, even if it's probably quite good in all practical cases")

My problem with this heuristic is it doesn't work well for the probably-fairly-common use-case of; fill it, empty it, fill it, empty it, fill it...etc.

As Guido pointed out, if you do have a use-case where a container gets very big, then shrinks and doesn't grow again, you can manually cleanup by creating a new container and del'ing the old one. If the implementation is changed to use this heuristic, there is no simple way to avoid the re-allocs for this use-case... (don't empty, but fill with None... ugh!).

My gut feeling is this heuristic will cause more pain than it would gain...

-- Donovan Baarda <abo at minkirri.apana.org.au> http://minkirri.apana.org.au/~abo/

More information about the Python-Dev mailing list