4 ms·
Right, but if you overallocate a bit you can ensure amortized constant time. (A comment in Python's list resize code claims that it does this, at least. You can
by koenigdavidmj 13y ago
Right, but if you overallocate a bit you can ensure amortized constant time. (A comment in Python's list resize code claims that it does this, at least. You can look at http://hg.python.org/cpython/file/d047928ae3f6/Objects/listobject.c http://hg.python.org/cpython/file/d047928ae3f6/Objects/listo... , function 'list_resize' for their sizing algorithm.)
- tracker1 13y ago.Net's System.Text.StringBuilder does the same... and you can choose the starting provision... When it runs out of space underneath, it will double the allocation for text. Which works pretty well. I wrote a utf-8 character encoder for use with PostgreSQL early in the C#/.Net 1.0 days, and allocated a StringBuilder for the output at 3x the original string size (up to 8K), which worked very well.
- gizmo686 13y agoIts worth noting that for some use cases, amortized constant time isn't good enough.