Content deleted Content added
Tag: Reverted |
StarfarerVI (talk | contribs) Unreal Engine has an interesting growth factor that's similar to Python, which I believe is valuable to note. |
||
| (19 intermediate revisions by 16 users not shown) | |||
Line 1:
{{Short description|List data structure to which elements can be added/removed}}
[[File:Dynamic array.svg|thumb|Several values are inserted at the end of a dynamic array using geometric expansion. Grey cells indicate space reserved for expansion. Most insertions are fast ([[constant time]]), while some are slow due to the need for [[Memory management|reallocation]] ({{math|Θ(''n'')}} time, labelled with turtles). The ''logical size'' and ''capacity'' of the final array are shown.]]
In [[computer science]], a '''dynamic array''', '''growable array''', '''resizable array''', '''dynamic table''', '''mutable array''', or '''array list''' is a [[random access]], variable-size list [[data structure]] that allows elements to be added or removed. It is supplied with standard libraries in many modern mainstream programming languages. Dynamic arrays overcome a limit of static [[array data type|arrays]], which have a fixed capacity that needs to be specified at allocation.▼
▲In [[computer science]], a '''dynamic array''', '''growable array''', '''resizable array''', '''dynamic table''', '''mutable array''', or '''array list''' is a [[random access]], variable-size
A dynamic array is not the same thing as a [[dynamic memory allocation|dynamically allocated]] array, which is an [[Array data structure|array]] whose size is fixed when the array is allocated, although a dynamic array may use such a fixed-size array as a back end.<ref name="java_util_ArrayList">See, for example, the [http://hg.openjdk.java.net/jdk6/jdk6/jdk/file/e0e25ac28560/src/share/classes/java/util/ArrayList.java source code of java.util.ArrayList class from OpenJDK 6].</ref>▼
▲A dynamic array is not the same thing as a [[dynamic memory allocation|dynamically allocated]] array or [[variable-length array]], either of which is an
== Bounded-size dynamic arrays and capacity ==
Line 20 ⟶ 22:
if (a.size == a.capacity)
// resize a to twice its current capacity:
a.capacity
// (copy the contents to the new memory ___location here)
a[a.size]
a.size
</syntaxhighlight>
As ''n'' elements are inserted, the capacities form a [[geometric progression]]. Expanding the array by any constant proportion ''a'' ensures that inserting ''n'' elements takes [[Big O notation|''O''(''n'')]] time overall, meaning that each insertion takes [[Amortized analysis|amortized]] constant time. Many dynamic arrays also deallocate some of the underlying storage if its size drops below a certain threshold, such as 30% of the capacity. This threshold must be strictly smaller than 1/''a'' in order to provide [[hysteresis]] (provide a stable band to avoid repeatedly growing and shrinking) and support mixed sequences of insertions and removals with amortized constant cost.
Line 30 ⟶ 32:
== Growth factor ==
The growth factor for the dynamic array depends on several factors including a space-time trade-off and algorithms used in the memory allocator itself. For growth factor ''a'', the average time per insertion operation is {{citation needed span|text=about ''a''/(''a''−1), while the number of wasted cells is bounded above by (''a''−1)''n''|date=January 2018}}. If memory allocator uses a [[First fit algorithm|first-fit allocation]] algorithm, then growth factor values such as ''a''=2 can cause dynamic array expansion to run out of memory even though a significant amount of memory may still be available.<ref name=":0">{{Cite web|title = C++ STL vector: definition, growth factor, member functions|url = http://www.gahcep.com/cpp-internals-stl-vector-part-1/|access-date = 2015-08-05|archive-url = https://web.archive.org/web/20150806162750/http://www.gahcep.com/cpp-internals-stl-vector-part-1/|archive-date = 2015-08-06|url-status = dead}}</ref> There have been various discussions on ideal growth factor values, including proposals for the [[golden ratio]] as well as the value 1.5.<ref>{{Cite web|url = https://groups.google.com/forum/#!topic/comp.lang.c++.moderated/asH_VojWKJw%5B1-25%5D|title = vector growth factor of 1.5|website = comp.lang.c++.moderated|publisher = Google Groups
Below are growth factors used by several popular implementations:
Line 41 ⟶ 43:
|-
|[[Python (programming language)|Python]] PyListObject<ref>[https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58 List object implementation] from github.com/python/cpython/, retrieved 2020-03-23.</ref>
|~1.125 (n + (n >> 3))
|-
|[[Microsoft Visual C++]] 2013<ref>{{Cite web|title = Dissecting the C++ STL Vector: Part 3 - Capacity & Size|url = https://hadibrais.wordpress.com/2013/11/15/dissecting-the-c-stl-vector-part-3-capacity/|website = Micromysteries|access-date = 2015-08-05|first = Hadi|last = Brais| date=15 November 2013 }}</ref>
|1.5 (3/2)
|-
Line 54 ⟶ 56:
|Facebook folly/FBVector<ref>{{Cite web|title = facebook/folly|url = https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md|website = GitHub|access-date = 2015-08-05}}</ref>
|1.5 (3/2)
|-
|[[Unreal Engine]] TArray<ref>{{Cite web |date=2025-02-26 |title=Nested TArrays in structs and memory |url=https://forums.unrealengine.com/t/nested-tarrays-in-structs-and-memory/2357416/3 |access-date=2025-05-26 |website=Epic Developer Community Forums |language=en}}</ref>
|~1.375 (n + ((3 * n) >> 3))
|-
|Rust Vec<ref>{{Cite web|title=rust-lang/rust|url=https://github.com/rust-lang/rust/blob/fd4b177aabb9749dfb562c48e47379cea81dc277/src/liballoc/raw_vec.rs#L443|access-date=2020-06-09|website=GitHub|language=en}}</ref>
|2
|-
|[[Go (programming language)|Go]] slices<ref>{{Cite web|title = golang/go|url = https://github.com/golang/go/blob/master/src/runtime/slice.go#L188|website=GitHub|access-date = 2021-09-14}}</ref>
|between 1.25 and 2
|-
|[[Nim (programming language)|Nim]] sequences<ref>{{Cite web |title=The Nim memory model |url=http://zevv.nl/nim-memory/#_growing_a_seq |access-date=2022-05-24 |website=zevv.nl}}</ref>
|2
|-
|[[Steel Bank Common Lisp|SBCL]] ([[Common Lisp]]) vectors<ref>{{Cite web |title = sbcl/sbcl|url= https://github.com/sbcl/sbcl/blob/master/src/code/array.lisp#L1200-L1204|website=GitHub|access-date=2023-02-15}}</ref>
|2
|-
|[[C Sharp (programming language)|C#]] ([[.NET]] 8) List
|2
|}
Line 85 ⟶ 102:
Bagwell (2002)<ref>{{Citation | title=Fast Functional Lists, Hash-Lists, Deques and Variable Length Arrays | first1=Phil | last1=Bagwell | year=2002 | publisher=EPFL | url=http://citeseer.ist.psu.edu/bagwell02fast.html}}</ref> presented the VList algorithm, which can be adapted to implement a dynamic array.
Naïve resizable arrays -- also called "the worst implementation" of resizable arrays -- keep the allocated size of the array exactly big enough for all the data it contains, perhaps by calling [[realloc]] for each and every item added to the array. Naïve resizable arrays are the simplest way of implementing a resizable array in C. They don't waste any memory, but appending to the end of the array always takes Θ(''n'') time.<ref name="sitarski96" /><ref>
Mike Lam.
[https://w3.cs.jmu.edu/lam2mo/cs240_2015_08/files/04-dyn_arrays.pdf "Dynamic Arrays"].
</ref><ref>
[https://users.cs.northwestern.edu/~jesse/course/cs214-fa19/lec/17-amortized.pdf "Amortized Time"].
</ref><ref>
[https://iq.opengenus.org/hashed-array-tree/ "Hashed Array Tree: Efficient representation of Array"].
</ref><ref>
[https://people.ksp.sk/~kuko/gnarley-trees/Complexity2.html "Different notions of complexity"].
</ref>
Linearly growing arrays pre-allocate ("waste") Θ(1) space every time they re-size the array, making them many times faster than naïve resizable arrays -- appending to the end of the array still takes Θ(''n'') time but with a much smaller constant.
Naïve resizable arrays and linearly growing arrays may be useful when a space-constrained application needs lots of small resizable arrays;
they are also commonly used as an educational example leading to exponentially growing dynamic arrays.<ref>
Peter Kankowski.
[https://www.strchr.com/dynamic_arrays "Dynamic arrays in C"].
</ref>
== Language support ==
[[C++]]'s [[Vector (C++)|<code>std::vector</code>]] and [[Rust (programming language)|Rust]]'s <code>std::vec::Vec</code> are implementations of dynamic arrays, as are the <code>ArrayList</code><ref>Javadoc on {{Javadoc:SE|java/util|ArrayList}}</ref> classes supplied with the [[Java (programming language)|Java]] API<ref name=Bloch>{{cite book | title= "Effective Java: Programming Language Guide" |last=Bloch| first=Joshua| publisher=Addison-Wesley | edition=third | isbn=978-0134685991| year=2018}}</ref>{{rp|236}} and the [[.NET Framework]].<ref>[https://msdn.microsoft.com/en-us/library/system.collections.arraylist ArrayList Class]</ref><ref name=Skeet>{{cite book |last=Skeet|first=Jon|title= C# in Depth |date=23 March 2019 |publisher= Manning |isbn= 978-1617294532}}</ref>{{rp|22}}
The generic <code>List<></code> class supplied with version 2.0 of the .NET Framework is also implemented with dynamic arrays. [[Smalltalk]]'s <code>OrderedCollection</code> is a dynamic array with dynamic start and end-index, making the removal of the first element also O(1).
[[Python (Programming Language)|Python]]'s <code>list</code> datatype implementation is a dynamic array the growth pattern of which is: 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...<ref>[https://github.com/python/cpython/blob/bace59d8b8e38f5c779ff6296ebdc0527f6db14a/Objects/listobject.c#L58 listobject.c (github.com)]</ref>
[[Delphi (programming language)|Delphi]] and [[D (programming language)|D]] implement dynamic arrays at the language's core.
Line 103 ⟶ 137:
[[Common Lisp]] provides a rudimentary support for resizable vectors by allowing to configure the built-in <code>array</code> type as ''adjustable'' and the ___location of insertion by the ''fill-pointer''.
== See also ==
* [[Stack (data structure)]]
* [[Queue (data structure)]]
== References ==
| |||