[Python-Dev] When do sets shrink?

[Donovan Baarda]

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")
> 
> </F>

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/