4 ms·

They're bad in the same way arrays are bad and "should never be used": appends often require reallocating the entire array, and are thus O(n) (although the real

They're bad in the same way arrays are bad and "should never be used": appends often require reallocating the entire array, and are thus O(n) (although the reallocs are usually better on average.)

jimmaswell 13y ago
I thought generally dynamic arrays were allocated more memory than the last allocation every time an appending happens, so that future appends are faster. Might've been the vector class from C++ I heard that about.
- kbolino 13y ago
  Indeed, and most implementations use exponential scaling when allocating a new array. So although your worst-case insertion time is O(n) from copying the entire array, over a sequence of n operations, this only happens log n times, so you have O(log n) amortized time. Edit: All the references to "constant amortized time" lead me to reevaluate this claim, and it's not correct. Let's say you start with an initial capacity of 2, and double the capacity when necessary. Then the cost of adding n elements to the list will be n + the sum of 2^i from i=1 to i=log(n), which is n + 2(n - 1) or O(n). Over n operations, that's O(1) amortized.
  - deleted 13y ago
    [deleted]
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 ago
  Its worth noting that for some use cases, amortized constant time isn't good enough.
stormbrew 13y ago
Typically it's considered to be amortized constant time since reallocations happen infrequently if implemented properly (the array has a growth factor and not just resize by one every append). http://stackoverflow.com/questions/200384/constant-amortized-time http://stackoverflow.com/questions/200384/constant-amortized...

They're bad in the same way arrays are bad and "should never be used": appends often require reallocating the entire array, and are thus O(n) (although the reallocs are usually better on average.)

jimmaswell 13y ago

I thought generally dynamic arrays were allocated more memory than the last allocation every time an appending happens, so that future appends are faster. Might've been the vector class from C++ I heard that about.

kbolino 13y ago
Indeed, and most implementations use exponential scaling when allocating a new array. So although your worst-case insertion time is O(n) from copying the entire array, over a sequence of n operations, this only happens log n times, so you have O(log n) amortized time. Edit: All the references to "constant amortized time" lead me to reevaluate this claim, and it's not correct. Let's say you start with an initial capacity of 2, and double the capacity when necessary. Then the cost of adding n elements to the list will be n + the sum of 2^i from i=1 to i=log(n), which is n + 2(n - 1) or O(n). Over n operations, that's O(1) amortized.
- deleted 13y ago
  [deleted]

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 ago
Its worth noting that for some use cases, amortized constant time isn't good enough.

stormbrew 13y ago

Typically it's considered to be amortized constant time since reallocations happen infrequently if implemented properly (the array has a growth factor and not just resize by one every append). http://stackoverflow.com/questions/200384/constant-amortized-time http://stackoverflow.com/questions/200384/constant-amortized...