A gentle introduction to arrays
And why they’re so fundamental to computer science
This is an ongoing series. Please check out the collection for the rest of the articles.
Arrays are fundamental to computer science. Whether you’re designing video games, optimizing operating systems, or proving algorithms, arrays are essential, fundamental tools. But while they make appearances in a wide variety of concepts and guises, their basic structure remains the same. This basic structure is the topic today. The post weaves through a variety of topics, but it’s primarily focused on three questions:
- What is an array?
- How are they designed?
- Why are they designed the way they are?
There is a related fourth question:
- How are arrays used?
But it won’t be answered until next post. To answer the first question informally, an array is a list of things. It doesn’t matter what the things are; they can be numbers, words, apple trees, or other arrays. Each thing in an array is called an item or element. Usually, arrays are enclosed in brackets with each item separated by commas, like this: [1, 2, 3]. The elements of [1, 2, 3] are 1, 2, and 3.
At this point you may be wondering why arrays get a whole post when they’re basically just lists with some fancy syntax and terminology. The key difference between arrays and everyday lists is in how arrays are used. If you make a grocery list, it will probably contain a handful of items. If you shop in bulk, it may be a page or so. Once you write the list, all you need to do with it is read it. “Duh”, you might say. What else would you do with it? With a grocery list, nothing. With an array? Quite a lot. This array might have thousands or millions of items. You might need to order it alphabetically. Or by the length of each item. Or by a property of each item, like its cost or weight. You might need to reverse its order or split it in half. Or merge it with another array. Or another ten arrays or even a thousand arrays. You will frequently need to know how many items are in it or how many items are in it that cost more than a certain amount. Very often you will need to compute an instruction for every item or remove items that don’t meet certain criteria. What if you have an array that contains arrays and you need to determine how many of these sub-arrays are identical? And the list goes on.
My point is that arrays in and of themselves are easy to understand. But because they are useful and easy to understand, they become the building blocks for very complicated structures and tasks. A close analogy would be playing cards; the playing cards themselves are easy to understand but their simplicity makes them the basis for some very complicated card games, like varieties of poker. The difficulty in explaining playing cards is not in literally describing what they are. That’s easy — they’re a collection of laminated paper rectangles with values ranging from 1 to 13 printed on one side; there are four of each card and some cards have special names: 1 is ace, 11 is jack, 12 is queen, and 13 is king. If that were all it took to understand poker then we’d all be experts. But that’s not all it takes to understand poker. There are many rules, like which hands of cards (i.e. arrays of cards) are valuable, when each player must ante up and when each card is placed (and whether it’s placed showing or hiding its value and whether it’s usable by all players or just one). Again, the list goes on and I’m only listing poker rules — the list is even larger when strategies are included.
The upshot is that in order to understand arrays, you must understand not only what they are but how they are used. And that’s why even their introduction gets its own post; arrays are used in so many different contexts that understanding them — really understanding their potential — takes a while. I want to provide solid ground for future posts on arrays to build on. Part of this solid ground is a fairly detailed explanation of how arrays are designed and why they’re designed this way.
To answer these questions, let’s start with a more precise definition of an array. An array consists of a fixed (which here means “unchanging”) number of elements. The number of elements in an array is call its length or size. So the size of [x, y, z] is 3. Cake has an instruction for this:
- size(x): Returns the size of x; x must be an array
So size([1,3,5,7]) returns 4 since the array [1,3,5,7] has 4 elements. An array can have any non-negative size. Non-negative implies positive or zero. It might sound strange to have a list of 0 items, but it’s possible and actually very common; an array with a size of 0 looks like this: [ ]. This is often called an empty array since it is empty of items. You can test for an empty array like this:
- empty(x): size(x) == 0
If the size of the array x is 0 then empty returns true, indicating that x is empty. If the size of x is not 0 then empty returns false, indicating that x is not empty — as in, x has at least 1 element. Notice that this new instruction, empty, is not defined in English, but by other Cake instructions. This makes empty a convenience; it is faster to write and is easier to read than the instructions from which it’s made, but it is not a necessary part of the language. Any program that includes empty could be rewritten without it by replacing empty with the instructions it is defined by.
In fact, that’s how programs are computed. At some point, all instructions are broken down into basic, indivisible sub-instructions that the processor can understand. Take note, however, that even though size is a basic, indivisible instruction in Cake, modern computer processors do not operate at such a high level; processors work at the level of numbers and Booleans and so arrays are ultimately composed of numbers that are used in specific ways. We will not go into the details of this just yet but be aware of the true identity of arrays: they are nothing but numbers, cleverly arranged and interpreted!
To understand this view of arrays as numbers, look at it from the following perspective. Like all matter is ultimately composed of subatomic particles, all arrays are ultimately composed of numbers. But this does not mean that the only way to look at matter is by looking at the particles that compose it; biology does not look at life atom by atom and neither does history. It is important to understand that ultimately, all matter is composed of these particles, but one should not always look through such a fine-grained lens. It is often useful to look at a higher level, ignoring the subatomic details. In fact, history views the world from a much more abstract level than subatomic particles — it even ignores molecules, cells, and often organs when it analyzes people. And this abstraction is not a weakness but a strength of history. We do not need to know the arrangement of every atom in England to understand the significance of the Magna Carta. In fact, bothering to know the arrangement of every atom in England distracts us from understanding the Magna Carta’s effect on constitutional law.
But while looking at England as tons of atoms is usually silly, knowing that England is ultimately made of tons of atoms is useful, especially when trying to understand more detailed aspects of England, like its geology and resources. And so it is with arrays and their basic components. It is important to remember that arrays are composed of numbers but we will not usually look at them from such a low level perspective. The key is to acknowledge the fundamental nature of arrays and keep this understanding in mind while we work at higher levels of abstraction. To use another example, thinking of your body as a collection of organs is a much too detailed perspective for most everyday decisions; but you better recognize you’re made of organs when you decide to put your body at risk by skydiving or driving a car. Arrays are the same; no matter how abstractly you look at them, they’re still just numbers when you zoom in far enough.
But I’m getting ahead of myself. Let’s finish the basics. A major unanswered question is how we retrieve an array’s elements; now that we have lists of things, how do we actually use the things in them? We need a way of identifying each element so we can pull it out of the array and use it. The answer lies in indexing. Each element gets its own index number that it can be identified with. This means that each index number must be unique. The starting element gets the index number 0 and each following element gets an index number 1 higher. So the index numbers for [4, 5, 6] are 0, 1, and 2. As you can see, the index numbers don’t depend on the value of each element — the first element gets an index of 0 whether the element’s value is 4 or 4000.
Regarding the whole starts-at-zero thing, you’re probably used to starting lists at 1, and counting up from the number 1, etc. That’s fine for everyday situations but computer science loves efficiency. Why does starting at 0 help efficiency? The explanation lies in how arrays are stored in memory. I don’t think I’ve mentioned it, but as you may know, computers remember what’s what by storing everything they need in their memory. Explaining every aspect of computer memory will take many, many posts, but we’ll sketch a rough outline for now.
Let me first explain computer memory with a brief analogy. Imagine a hotel. It’s a small hotel — a motel, really — and consists of just one long hall.
Like most hotels, each room gets a number. This hotel, however, is quite frugal and doesn’t want to spend any money buying labels for each room number. Those little placards with room numbers are just too expensive.
Instead, they’ve devised a clever scheme. When they give a guest their room key, say for Room 5, they tell the guest to count each door as they walk down the hallway, starting from 0. When they count to 5, they’ve reached their room. So a guest staying in Room 0 should enter the first door they pass, a guest staying in Room 1 should enter the second door they pass, etc. In general, a guest staying in Room x should walk past x doors to get to the right room.
While I hope no real hotel actually uses this scheme, you can see that it works. And here’s the benefit: you don’t need to waste time reading each placard to determine if you’re at the right room. If you need to go to Room 1001, you can sprint as fast as you can down the hallway counting doors as you go until you reach 1001. It would take a lot longer to find Room 1001 if you had to read every placard as you passed. Since computers can “sprint” through memory very fast, being able to count doors is a lot more useful than having to read a label attached to each one.
Now that you have a mental image to compare to, let’s drop the hotel analogy in favor of something a bit simpler. Let’s represent a number stored in memory with a number in a box, in this case 12:
Don’t worry about how this number is literally, physically stored; view them as doors in a hotel or any other unique spot in a collection of spots. Specifically, let’s say that every number stored in memory gets an address (just like every room in a hotel gets a room number). The address scheme could be anything we want — the first spot could be called “Spot A" and the second spot “Spot B" or the first could be “elephant” and the second “tiger” — but we want logical organization, not a zoo. Numbers are great for organization (which is why hotels use numbers and not animal names to identify rooms), so let’s use numbers to identify spots in memory. Let’s say the spots start at Spot 0, abbreviated S0. The next spot is S1, then S2, and so on. If you want to store something in memory, pick an address (say, S100) and place the thing there. If you want to access that thing later, pull it from the spot you originally stored it (in this case, S100). Since computers work in numbers, these “things” are always numbers. Make sure you understand the difference between address numbers like S0 and S100 and the numbers stored in them. S0 could store the number 15 or 200, it doesn’t matter. The address numbers are different than the numbers at these addresses.
So for now, storing one number is solved: pick a numerical address and place the number there. But how do we store an array of numbers? Like this:
In this case, the array being stored is [10, 15, 20]. Let’s say the first number, 10, is stored in S100. Then the next number, 15, is stored in S101. Thus, the last number in the array, 20, is stored in S102. If you wanted the first number, you would ask for the value in S100. If you wanted the second number, you would ask for the value in S101. Accordingly, if you wanted the third number, you would ask for the value in S102. Since the array is stored in memory as a few numbers in a row, let’s just say that the address of the array is the address of the first number (in this case, S100). There’s no other information involved with arrays, so why not? That way, if we want the first number in the array, we just pull from S100. If we want the second number, we pull from S100 + 1, which is S101. The third number is stored in S100 + 2, which is S102. So in general, the address of the xth item in an array is the address of the 0th item plus x. Since the address of the array as a whole is just the 0th item’s address, the address of the xth item is the address of the array plus x.
Do you see why it makes sense for arrays to start at 0? This way, the address of the array can simply be the address of its first element and each subsequent element gets an address one spot higher. So if the array’s address is x, the starting item’s address is x, the next item’s address is x + 1, etc. Therefore, the simplest way to index arrays is by starting at 0, not 1.
To reiterate the previously mentioned idea about abstraction, you don’t always need to think about arrays in such explicit detail — just as you don’t always need to think of them as numbers, you don’t always need to think of how they’re stored in memory. But the computer does need to think in these ways and if you’re going to tell a computer how to find an array in its memory, you need to tell it using its indexing scheme, which for efficiency reasons starts at 0. Even though you’re not viewing arrays at the level of memory indexing, you need to be aware of memory indexing, at least to the extent that you must access array items starting from 0. I promise you’ll get used to this idea soon enough. If you program enough, you’ll get so accustomed to starting arrays and other kinds of lists at 0 that you’ll start making all lists start at 0, even grocery lists, and start wondering why everyone else doesn’t also. You’ll probably have an awkward moment or two when other people read your lists and ask why you started them at 0. Then you’ll start rambling on about frugal hotels and the importance of efficiency and, well, you should probably just stick to starting grocery lists at 1.
I’m sure you have more questions about computer memory. Why does the programmer need to know the address of every value needed? Can’t the computer figure it out for us? Why can’t we just start arrays from 1 and have the computer subtract 1? How exactly are numbers stored in memory? How do you know, when looking at memory, where one value starts and the other ends? All of these questions lead to deeper insights into how computers work and I’ll get to them as soon as I can. But first we need to learn more about what we can do with arrays. A good start to this goal and a good end to this post is how to actually access array elements in Cake:
- a[x]: returns the xth item in the array a
Simple enough, I hope, given the previous paragraphs. Note that brackets, [ and ], are not the same as parentheses, ( and ). Also note that this instruction applies only to arrays, just like + and * apply only to numbers. Here’s an example of the above instruction so you can see this idea in action:
This expression returns 10 since the second item of the array (i.e. the item with an index of 1) is 10. So the first set of brackets, [8, 10, 15] create an array with 3 elements. The second set of brackets, because they come right after an array, match the instruction definition given above (a[x]: returns the xth item in a). In this context, the array [8, 10, 15] becomes a, so adding [1] after it returns the element in a with an index of 1. Since 1 refers to the second element in a, the result is 10. On the other hand,
returns 15 since the element with an index of 2 is 15. To give a more intricate example, take a look at this:
The element with an index of 1 is another array. Thus, the result is this array, [10, 15]. If you want to access an element inside this sub-array, you can use another set of brackets like this:
Take your time with this one and unfold it one step at a time. First, isolate the array you’re working with:
This is an array with 2 elements: 5 and [10, 15], which is itself an array. The next part of the code takes the array and applies [1] to it. This returns the element with an index of 1, which is [10, 15]. This simplifies the situation, making it look like this:
Since [0] returns the first element of the array, the final answer is 10. As usual, approach complex code by following one step at a time. It often helps to write down intermediate results like I did in the image above; no matter how long and complex a piece of code is, it can always be solved one step at a time, shrinking the pieces one by one. I want to end the post with a question I’ll answer in the next one. Given this big array of numbers,
how do you find the biggest number in this array? (For extra credit, can you provably and systematically find the biggest number in any array I give you?)
Image credit: bubble sort, poker hands, atom, hotel hallway, room number
