I am implementing a stack using an array. And it needs to grow at some point as I push items on to the stack. So I am wondering how much should it be resized? Should I resize it by a constant number? Please let me know.
Asked
Active
Viewed 1,236 times
0
-
2You could use an ArrayList instead of an array, and leave the resizing to the framework. – Blorgbeard May 25 '16 at 01:34
6 Answers
3
From one hand, you don't want to do it too often, especially on big sets of data. From the other hand, you don't want to waste to much memory. Usually good strategy could be to multiply size by 2 (or 1.5, if you more concerned about memory over performance). With doubling it will adapt to possible growth, and it will be predictable number of growth operations.
amaksr
- 7,555
- 2
- 16
- 17
-
Possibly a flag you could set via the constructor to tell the class if you want preference to performance or memory? Such as a 1-10 int value that ranges from 10% to say 1000% size increase for example – 2ARSJcdocuyVu7LfjUnB May 25 '16 at 01:43
1
IIRC the .net framework tries to double the size of a list when necessary, could be a good approach for you as well.
AD.Net
- 13,352
- 2
- 28
- 47
1
It almost entirely depends what your stack need to do and what purpose, but on a general purpose stack it's often the most beneficial to double the stack once it reaches the limit. This can be easily shown using amortized analysis. I'm pretty sure you will find the proof on that somewhere in the internet :P
But if you're lazy just look here for a brief explanation
1
You want to multiply the array size by some constant (e.g. 1.75) it does not really matter what it is.
By multiplying you are implementing the stack in such a way that adding an element takes Amortized Constant Time.
Example:
Start:
- Array Size: 2
- Assignments: 0
- Total Assignments: 0
- Average Assignments per add: n/a
Add 1st element:
- Array Size: 2
- Assignments: 1: //adding value to array
- Total Assignments: 1
- Average Assignments per add: 1
Add 2nd element:
- Array Size: 2
- Assignments: 2: //adding value to array
- Total Assignments: 2
- Average Assignments per add: 1
Add 3rd element:
- Array Size: 4 // double array
- Assignments: 3: // copy old values to new array + add new value
- Total Assignments: 5
- Average Assignments per add: 5/3 ~ 2
Add 4th element:
- Array Size: 4 // double array
- Assignments: 1: // copy old values to new array + add new value
- Total Assignments: 6
- Average Assignments per add: 5/4 ~ 2
Add 5th element:
- Array Size: 8 // double array
- Assignments: 5: // copy old values to new array + add new value
- Total Assignments: 11
- Average Assignments per add: 11/5 ~ 2
Add 6th element:
- Array Size: 8 // double array
- Assignments: 1: // copy old values to new array + add new value
- Total Assignments: 12
- Average Assignments per add: 12/6 = 2
... As you continue the average assignments per add will stay around 2
0
The amount that you should resize is really dependent on what you are adding to the array. Also you should resize it by a constant so you don't have to go thru a more complicated method to resize the array.
Madusha Silva
- 65
- 1
- 1
- 9
-
-
doubling the array would at some point be redundant and the size would exponentially grow, i would recommend increasing by 1.5 times of the size of the array at a time. – Madusha Silva May 25 '16 at 01:22
0
Just double the size, that's conventional approach.
elricfeng
- 364
- 1
- 8
-
-
Because in most case it's not a big issue whether we increase it by 2, or 3 or 1.5 times. We just want it be larger when we reach the limit, and you know 2 is always appreciate in the world of computer science, and 1.5 seems complicate, also it's a bit waste of space if more than 2. So just pick 2. – elricfeng May 25 '16 at 01:36