In article <mailman.3057.1351554215.27098.python-l...@python.org>, Ian Kelly <ian.g.ke...@gmail.com> wrote:
> On Mon, Oct 29, 2012 at 5:24 PM, Roy Smith <r...@panix.com> wrote: > > I think you're missing the point of "amortized constant time". Yes, the > > first item appended to the list will be copied lg(20,000,000) ~= 25 > > times, because the list will be resized that many times(*). But, on > > average (I'm not sure if "average" is strictly the correct word here), > > each item will be copied only once. > > > > Still, it always stuck me as odd that there's no preallocate() method. > > There are times when you really do know how many items you're going to > > add to the list, and doing a single allocation would be a win. And it > > doesn't cost anything to provide it. I suppose, however, if you're > > adding enough items that preallocating would really matter, then maybe > > you want an array instead. > > > > (*) I don't know the exact implementation; I'm assuming each resize is a > > factor of 2. > > The growth factor is approximately 1.125. "Approximately" because > there is also a small constant term. The average number of copies per > item converges on 8. Wow, that's surprising. It also makes it that much more surprising that there's no way to pre-allocate. -- http://mail.python.org/mailman/listinfo/python-list
