C
Chris
This is an ill-defined question, but here goes:
My app uses lots of int arrays. We usually don't know how large the
array will ultimately be when we first start populating it. So we grow
the array as necessary, which involves creating a new, larger array and
copying the data over from the old one.
The question is, when we create a larger array, how large should it be?
Assume that all arrays will eventually grow to a random size, unknowable
in advance. Assume also that we want to optimize for both memory and speed.
At one extreme, we could grow each array an element at a time, that is,
the new size would be the old size + 1. This is memory efficient, but
slow and generates a lot of garbage. At the other extreme, we could
allocate huge arrays at the beginning and double them each time we
needed more space. This would be fast because we would seldom need to
extend the arrays, but very memory inefficient.
What's a good tradeoff?
Just for reference, java.util.ArrayList uses this formula internally:
int newCapacity = (oldCapacity * 3)/2 + 1;
My app uses lots of int arrays. We usually don't know how large the
array will ultimately be when we first start populating it. So we grow
the array as necessary, which involves creating a new, larger array and
copying the data over from the old one.
The question is, when we create a larger array, how large should it be?
Assume that all arrays will eventually grow to a random size, unknowable
in advance. Assume also that we want to optimize for both memory and speed.
At one extreme, we could grow each array an element at a time, that is,
the new size would be the old size + 1. This is memory efficient, but
slow and generates a lot of garbage. At the other extreme, we could
allocate huge arrays at the beginning and double them each time we
needed more space. This would be fast because we would seldom need to
extend the arrays, but very memory inefficient.
What's a good tradeoff?
Just for reference, java.util.ArrayList uses this formula internally:
int newCapacity = (oldCapacity * 3)/2 + 1;