Array On Steroids

I’ve learned that certain things which may be totally acceptable in one programming language aren’t okay in another. That customs, syntax or indices don’t necessarily translate. Even few things we find to be unacceptable and downright horrifying aren’t universal.

Such is a case of our beloved array too.

Below is the list of languages whose array indices/index starts at 1:

Even you, R ? I am in two minds about learning you now.

Yes, take a moment to digest this fact that we still have programming languages where array indexes start at 1.

Okay, is this post about should array index start at 1 or 0?

Nope. This post is about a comment which I received on my blog post of arrays. (If you haven’t read the post, please do else following 500 words may be a big bouncer.)

I read this comment, answered vaguely in my brain and fell off the planet for few weeks.

Some cyborg comments made me stumble on this comment again.

I decided to dig a bit deeper into what I was thinking was correct and this comment inspired a whole new blog post. (This is one of the ways to make me write on any topic you want. Drop a comment, wait for few weeks for me to return to the planet)

Yeah I know you might be wondering, I don’t write in Python, why should I care?

Cuz, this is one of the ways strings are stored in memory irrespective of any languages you write in.

How?

Let’s take a small example:

I want to store names of all super-awesome people who took time to comment on my blog post by using array(list in python; just different names)

[‘Maxim’, ‘Naneee’, ‘Barun’, ‘Anand’, ‘Jan’, ‘Sumanth’, ‘Amal’, ‘Nikhil’, ‘Sharadhra’, ‘Root’, ‘Deepak’]

There’s an issue here. Our second bullet point in our array definition says equal size elements meaning each cell of the array must use the same number of bytes.

Our names array have strings made up of different lengths. How do we maintain this equal size thing-y?

Problem?

A Dumb Vs Wise Move:

Dumb Move: We can define an upper limit i.e each cell to hold the maximum length of string but that would be wasteful.

Wise Move: Referential array(array of object references)

Referential Arrays:

Array storing references to strings

Two things we need to know about Referential Array:

  1. Here, instead of storing elements sequentially we store address/references at which the actual name string (element) resides.
  2. Bits required to store each string memory address is fixed/equal sized.(64 bits per address)

Variable size problem solved. But there’s one small disadvantage.

Along with a number of bits required to store that string of different length, there’s an extra overhead of using 64 bits of the memory address for object reference.

But, does it answer Maxim question?

Not Yet!

Array on steroids — Dynamic Array

Other terms used: Resizable Array/ Mutable(changeable) Array

  • For JAVA-lovers: Standard Arrays are of fixed size in Java but Array List is not. This is your List ADT( java.util.List, rings a bell?). Not baked directly in language but it is still there.
  • For Javascript/ Ruby: Array size is never fixed, highly resizable.
  • For Non-Pythoners: List is just a different name for an array in Python.

In many ways, Hermit crab is like dynamic arrays. Allow me to explain the similarities between them.

  • Hermit crab is born with some fixed size shell. When we declare our array/list, we often construct it with some particular length.
  • As a hermit crab grows its shell becomes a tighter fit. Similarly, we can add elements to our list or an array up-to a particular limit.
  • To solve its small shell problem, hermit crab moves to a bigger shell. To solve our fixed length problem, our languages use something called as a dynamic array to accommodate the newest elements.
  • When hermit crab chooses a new shell, it often looks for a bigger shell than its current size considering future possibility of growing. In our dynamic array/list, they maintain an internal array which is often much greater than the current length.
  • There is still a possibility that the newest shell may run out of space, so hermit crab searches for a new bigger shell. Our internal array maintained may run out of capacity, so they internally request for a new, larger array and copies old content from an array to the new one.
  • The old shell which isn’t needed by hermit crab can be used by some other crab as it quite comfy with the new one. Similarly, our old array is no longer needed and is reclaimed by the system.

Python List & Tuple Or Java’s Array List is based on this strategy.

I know too word-y and looks a bit scary too, but I’ve underlined few words in pink. We’ve deep dived into each term in totally (un)scary way.

So, equal size elements and concern of using multiple data types in an array without fear of running out space comes from dynamic arrays.

I hope this answers your question. And Thank you Maxim for inspiring me to write this post.

Yes, I am giving you full credit.

Next Up:

  •  Implementing Dynamic Array
  • Amortized Analysis of Dynamic Array

Stay Tuned!

Get new blog posts delivered straight to your inbox. No Spam. I Promise.

Email *


You may also like

Leave a Reply

Your email address will not be published. Required fields are marked *