[Python-Dev] When do sets shrink?

[Noam Raphael]

On 12/29/05, "Martin v. Löwis" <martin at v.loewis.de> wrote:
> Noam Raphael wrote:
> > The computer scientist in me prefers O() terms over changes in a
> > constant factor, but that's only me.
>
> That remark, I don't understand. In a hash table, most "simple"
> operations are O(n) as the worst-case time, except for operations
> that may cause resizing, which are O(n**2) (worst case).
>
> So you are proposing that .pop() might trigger a resize, thus
> changing from O(n) worst case to O(n**2) worst case? Why would
> a computer scientist prefer that?
>
Perhaps I'm not that great computer scientist, but simple operations
on hash tables are supposed to be O(1) in the average case (which is
what matters to me). This means that resizing is an O(n) operation in
the average case.

This means that just like list.append() and list.pop(), that are made
O(1) operations amortized, so can operations on hash table be made
O(1) amortized - all you need is to use the trick for setting bounds
so that resize operations will always happen after O(n) simple
operations.

> > Perhaps a note about it should be added to the documentation, though?
>
> Sure. Patches (to sf.net/projects/python) are welcome.

I will try to send one when sf becomes healthier.

Noam