Arrays — Cost of flexible size
by Deepakumar M,
Let’s see the flexibility provided by programming languages and their associated costs.
Most of the programming languages supports initializing arrays without defining the size. For example, vectors in C++, arrays in many interpreted languages. So what’s special with this flexibility? Since the size is not provided explicitly, what’s the size to be set initially?
That’s a technique used in many places. Start with smaller value, grow very fast upto a threshold and then grow slowly. So for our array, initially the language compiler/interpreter will set the size as 1. When the size is insufficient it will just double the size(varies between languages). Based on your free memory and programming language, threshold differs. Lets create an array without defining the size and see what happens when we insert 5 elements.
Initially this is how our array will be.
After inserting 10,
Now let’s insert one more element — 20. There is no enough memory and so the size has to be doubled now. But doubling the size is not simple always. Say your compiler has allocated the memory for the array where there is only space for storing one element and the memory cells next to it are already filled.
Here are steps that the compiler will do now.
So after inserting 20 our array will be,
Let’s insert 30 — again the size will be doubled now. This makes the array size to be 4 now.
After inserting 40,
Finally let’s add one more element 50.
So now we can insert 3 more elements without doing any additional work. The same set of steps is applicable when we push the elements into the front of the array. Why can’t we just increase the size of array by 1 at each step? — if we do so, these steps has to be done every time when we push an element to the array which can be avoided.
So far one point is very clear — defining the size of array while initializing it is always a best choice as it simplifies the work for the language interpreters. It is obvious that for inserting one element, the time complexity will be O(1) in the best case, O(N) in the worst case where N is the number of elements in the array before insertion. Since the complexity is not same for all insertions, we would do the amortized time complexity analysis here. In that way, when we insert N elements into an array, the amortized time complexity for inserting one element into the array will be O(1). We can discuss more on this later, may be as a separate blog.
Many compiled languages intentionally provides the flexibility with different data types. This would easily enforce the developer to use them only in places where they are necessary. For example, vectors in C++. In some interpreted languages you can’t see much difference in performance. That’s because the way the arrays were implemented in that language were different. Still it is good to define the size while initialization.
It’s clear that in arrays, the cost of flexible size over predefined size are unwanted I/O operations and extra CPU cycles.
Of course there are places where the size of the array can’t be found upfront where we need worry about this cost factor.
When we visualize this as a technique, this can be applied in many places. Let’s discuss few scenarios where it is used or it can be used.
We might come up with different techniques and they might be appropriate in some situations too. For example like our brain we can learn initially and we can come up with a approximate values which is very much close. Like how we are guessing the capacity of a tank or no. of spoons of salt needed for the food, just by looking at them. Choosing between the techniques depends on the scenarios and its purely a personal choice even in programming languages .
With the clarity of understanding the difference between declaring arrays with or without size, in our next blog let’s discuss how in many interpreted languages, different data types can be added to an array without compromising the random access.
We at CaratLane are solving some of the most intriguing challenges to make our mark in the relatively uncharted omnichannel jewellery industry. If you are interested in tackling such obstacles, feel free to drop your updated resume/CV to email@example.com!