How much should I add when resizing an array?
arrays, java, optimization
Solution
It's recommended to double the size of the array when resizing. Doubling the size leads to amortized linear-time cost.
The naive idea is that there are two costs associated with the resize value:
- Copying performance costs - costs of copying the elements from previous array to new one, and
- Memory overhead costs - cost of the allotted memory that is not used.
If you were to re-size the array by adding one element at a time, the memory overhead is zero, but the copying cost becomes quadratic. If you were to allocate too much slots, the copying cost will be linear, but the memory overhead is too much.
Doubling leads to a linear amortized cost (i.e. over a long time, the cost of copying is linear with respect to the size of the array), and you are guaranteed not to waste more than half of the array.
UPDATE: By the way, apparently Java's `ArrayList` expands by (3/2). This makes it a bit more memory conservative, but cost a bit more in terms of copying. Benchmarking for your use wouldn't hurt.
MINOR Correction: Doubling would make the cost resizing linear amortized, but would ensure that you have a amortized constant time insertion. Check CMU's lecture on Amortized Analysis.
Problem
I'm having a contest with another student to make the fastest version of our homework assignment, and I'm not using an ArrayList for performance reasons (resizing the array myself cut the benchmark time from 56 seconds to 4), but I'm wondering how much I should resize the array every time I need to. Specifically the relevant parts of my code are this: ``` private Node[] list; private int size; // The number of items in the list private static final int N; // How much to resize the list by every time public MyClass(){ list = new Node[N]; } public void add(Node newNode){ if(size == list.length){ list = Arrays.copyOf(list, size + N); } list[size] = newNode; size++; } ``` TL;DR: What should I make `N`?