On 12/29/05, Donovan Baarda <[EMAIL PROTECTED]> wrote: > Without some sort of fancy overkill size hinting or history tracking, > that's probably as good a heuristic as you can get.
I'm sorry, but it's not correct. There's a simple resize scheduling algorithm that is proven to take, when you sum things up, O(1) per each simple operation, and that keeps the amount of used memory always proportional to the number of elements in the set. 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. Noam _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
