Sequential Processing of Arrays

Suppose you walk into a room and start asking people for their birthdays. How long do you expect to wait before someone shares a birthday with a person you already asked? Most people give an answer that is much larger than what actually happens. That gap between expectation and reality is the starting point for this article. It also introduces one of the most useful properties of arrays, random access, and shows how a simple array lets a program answer the question quickly.

To answer that kind of question in code, a program has to keep track of what it has already seen. The way an array does this, and the reason the access pattern matters, is the subject of the rest of this article. We will look at two ways of visiting the elements of an array, and then trace a birthday simulation step by step to see which one it needs.

Up to this point, the array processing examples in the course have used sequential access. In sequential access, the elements of an array are processed one after another, in the order they appear in the array. You start at the first position, move to the second, then the third, and so on until you finish. Many useful tasks look like this, such as totaling all the values in a list or scanning for the largest one.

The phrase describes the shape of the work. A program that totals a list visits every position once, in order, and it has no need to skip around. The same array could also be used in a different way, and that different way is random access.

One of the big advantages of arrays is that they allow random access. Because every slot can be reached by its index, reading the element at position 2 costs the same kind of step as reading the element at position 0 or at the last position. Nothing in the array forces you to pass through the slots in between. The diagram below shows a small array with five positions. Each cell can be reached by its index, and the program can read one cell without inspecting any other cell.

The figure is a small illustration with five positions instead of 365. To check day number 2, the program names used[2] and reads it. It does not need to inspect used[0] or used[1] first. Those two cells hold true and false respectively, but they have no bearing on the lookup of position 2. This direct reach is what makes random access useful when the next value to examine could be anywhere in the array.

To simulate the birthday experiment, the program must remember which birthdays it has already seen. There are 365 possible birthdays, and ignoring leap years is part of the setup. For each possible birthday, the program needs one piece of information: has someone with this birthday already been found? The answer is a boolean value. Gathering 365 boolean answers into one structure is exactly what an array is for.

Before you look at the answer, make a prediction. The array is created fresh, and no birthdays have been recorded at all. What will the program find in each slot before any simulation step has run, and what should it do when the first birthday arrives?

New boolean arrays start with false in every slot, so unseen birthdays need no setup before they are checked. When day 2 is drawn, the program reads used[2], finds false, and records the day as used by writing true into that same slot. The diagram shows the state after that first draw: only the slot at index 2 has changed.

Each time the simulation picks a person, the birthday it draws could be any day from 0 to 364. The next birthday has no relationship to the previous one, so the program cannot know in advance which slot it will need. A purely sequential scan would waste effort walking past slots that have nothing to do with the new birthday. Random access solves this neatly: the program computes the day number, reads used at that index, and either stops or records the day as used.

The two access patterns answer different kinds of questions. Sequential access suits tasks where every element must be visited in order, such as totaling values or scanning for a maximum. Random access suits tasks where the next element to examine depends on information that arrives while the program runs. The birthday problem is of the second kind. The next day number is not known in advance, so a sequential scan from position 0 would have to walk past many unrelated slots before reaching the right one.