Content deleted Content added
Link DADS |
Talk about the time-space tradeoff |
||
Line 18:
Many dynamic arrays also deallocate some of the underlying storage if its size drops below a certain threshold, such as 30% of the capacity.
In choosing the percentage by which to enlarge the table, there is a time-space tradeoff: the average time per insertion operation is about ''a''/(''a''−1), where ''a'' is the multiplier factor such as 2 by which the table size increases each time. On the other hand, ''capacity'' minus ''size'' space is allocated but not in use, a quantity bounded above by (''a''−1)''n''. The choice ''a''=2 is a commonly-used value, but depending on the application many values between about ''a''=1.2 and ''a''=4 may be suitable.
Dynamic arrays benefit from many of the advantages of arrays, including good [[locality of reference]] and [[data cache]] utilization, compactness (low memory use), and [[random access]]. They usually have only a small fixed additional overhead for storing information about the size and capacity. This makes dynamic arrays an attractive tool for building cache-friendly data structures.
| |||