Why "Play Track 750,000" Is Instant and "Find Golden Hour" Isn't: Memory as Mailboxes

Find out why a music app plays track 750,000 in one step but has to search for a song by its title, and how a program keeps songs of different sizes without losing that one step.

Novice · Data Structures · Software Development · Updated

By

After this lesson you can

  • Explain why going to an item by its position takes one step, while finding an item by its value takes a search
  • Explain a reference as a note that says where in memory to find something

Key takeaways

  • Memory is a long row of numbered boxes. Each box's number is its address.
  • Going straight to a box by its number takes one step, however many boxes there are.
  • Finding a box by what's inside it means looking box by box, so it takes longer the more boxes there are.
  • A reference is a note in one box that says which box to look in. Linked lists, trees and graphs are built from references.
  • A million songs side by side play track 750,000 in one step, but finding "Golden Hour" by its title takes 750,001 looks.

Your music app has a million songs. Tap "play track 750,000", and it starts at once. Type "Golden Hour" into the search box instead, and the app reads titles one after another until it gets there. Both jobs end at the same song. One is instant on any phone; the other takes longer the more songs there are. Why can a computer go straight to a position, but not straight to a title?

What would you try?

Maybe the computer counts its way there. If playing track 750,000 meant counting "track 1, track 2, track 3…" up to 750,000, playing would be exactly as slow as searching: 750,000 steps either way. But it isn't slow. So the computer can't be counting.

Maybe it remembers where every title is. It would need a second list of a million titles with their positions, and finding "Golden Hour" in that list is the same search again.

So going to a position must work some other way, and searching by title must be missing whatever that is.

The questions that lead to it

What does the computer know about track 750,000 before it looks? Only its number.

What if every song's slot were the same size, side by side in one row, and you knew where the row starts? Then you could work out where slot 750,000 is with one sum: where the row starts, plus 750,000 slots. No counting, no searching: one step, however long the row is.

And what does a title tell you? Nothing about where it is. "Golden Hour" could be in any slot, so the only way to find it is to look.

That's exactly how a computer's memory works.

Memory as a row of mailboxes

A computer's memory is a very long row of small boxes, billions of them, each holding a little bit of data. Every box has a number, called its memory address, the way every mailbox in an apartment lobby has a number. A mail carrier with a letter for box 214 walks straight to 214; nobody opens box 1, then box 2. But ask "which box has the letter from Grandma?", and they'd have to open box after box.

When your program keeps songs side by side, they sit in boxes next to each other. A row of items stored side by side like that is called an array, and each item's position in it is its index. In almost every programming language, the first position is 0, not 1: think of it as "how many boxes from the start". A million tracks are numbered 0 to 999,999.

The code below makes a million tracks (made-up titles, Song 0 to Song 999999), puts "Golden Hour" at track 750,000, then does both jobs: it goes straight to track 750,000, and it searches for "Golden Hour" by title, counting the looks.

List<string> tracks = new List<string>();
for (int number = 0; number < 1000000; number++)
{
    tracks.Add("Song " + number);
}
tracks[750000] = "Golden Hour";

Console.WriteLine("Track 750000 is " + tracks[750000] + " (1 step)");

int looks = 0;
for (int position = 0; position < tracks.Count; position++)
{
    looks++;
    if (tracks[position] == "Golden Hour")
    {
        Console.WriteLine("Found Golden Hour at track " + position + " after " + looks + " looks");
        break;
    }
}
Track 750000 is Golden Hour (1 step)
Found Golden Hour at track 750000 after 750001 looks
void main() {
    List<String> tracks = new ArrayList<>();
    for (int number = 0; number < 1000000; number++) {
        tracks.add("Song " + number);
    }
    tracks.set(750000, "Golden Hour");

    IO.println("Track 750000 is " + tracks.get(750000) + " (1 step)");

    int looks = 0;
    for (int position = 0; position < tracks.size(); position++) {
        looks++;
        if (tracks.get(position).equals("Golden Hour")) {
            IO.println("Found Golden Hour at track " + position + " after " + looks + " looks");
            break;
        }
    }
}
Track 750000 is Golden Hour (1 step)
Found Golden Hour at track 750000 after 750001 looks
tracks = [f"Song {number}" for number in range(1000000)]
tracks[750000] = "Golden Hour"

print(f"Track 750000 is {tracks[750000]} (1 step)")

looks = 0
for position in range(len(tracks)):
    looks += 1
    if tracks[position] == "Golden Hour":
        print(f"Found Golden Hour at track {position} after {looks} looks")
        break
Track 750000 is Golden Hour (1 step)
Found Golden Hour at track 750000 after 750001 looks
const tracks = [];
for (let number = 0; number < 1000000; number++) {
  tracks.push("Song " + number);
}
tracks[750000] = "Golden Hour";

console.log(`Track 750000 is ${tracks[750000]} (1 step)`);

let looks = 0;
for (let position = 0; position < tracks.length; position++) {
  looks++;
  if (tracks[position] === "Golden Hour") {
    console.log(`Found Golden Hour at track ${position} after ${looks} looks`);
    break;
  }
}
Track 750000 is Golden Hour (1 step)
Found Golden Hour at track 750000 after 750001 looks
const tracks: string[] = [];
for (let number = 0; number < 1000000; number++) {
  tracks.push("Song " + number);
}
tracks[750000] = "Golden Hour";

console.log(`Track 750000 is ${tracks[750000]} (1 step)`);

let looks = 0;
for (let position = 0; position < tracks.length; position++) {
  looks++;
  if (tracks[position] === "Golden Hour") {
    console.log(`Found Golden Hour at track ${position} after ${looks} looks`);
    break;
  }
}
Track 750000 is Golden Hour (1 step)
Found Golden Hour at track 750000 after 750001 looks

One step against 750,001 looks, for the same song. Notice the off-by-one: the song at position 750,000 was found on look number 750,001, because the count starts at 1 and the positions at 0. That gap trips up every programmer at some point, so it's worth noticing now.

Try it. Put "Golden Hour" at track 0 instead of 750000, and run it again: the first line now shows Song 750000, and the search finds "Golden Hour" on its first look. Then change the line that prints the track to read tracks[1000000]. There's no track 1,000,000 (they're numbered 0 to 999,999), so your language stops with an error: C# and Java say the index is out of range, Python says list index out of range, and JavaScript and TypeScript quietly give back undefined.

When a song doesn't fit: a note that says where to look

There's a catch in "every slot is the same size". Songs aren't. A title can be 3 letters or 40, and the audio of a 41-minute live recording is far bigger than a 3-minute single. So how do a million different-sized songs sit in a row of same-sized slots?

  • Make every slot big enough for the biggest song? Then a million slots each waste room for 41 minutes of audio.
  • Let a long song spill over into the next few slots? Then slot 750,000 is no longer track 750,000, and the one-step sum stops working.

The way out: each slot holds a small note of the same size, saying where the song really is: "look in box 512". That note is called a reference. Following it is one more step, just like going to any box by its number, so going to track 750,000 is still a step or two, never a search.

References are how one piece of data points to another. They're why two variables in a program can both "hold" the same list: really, both hold the same note, pointing at one list. References: Two Names, One Object in the next chapter shows that in code. And they're how the structures later in this course are built: a linked list is a chain of notes, each saying where the next item is; a tree is notes pointing down to children; a graph is notes pointing to neighbors.

A row of eight numbered mailboxes, 0 to 7, each holding one song title card, with an arrow going straight to box 6, labeled "one step"; below, box 40 holds a note that reads "look in box 512", with a dotted arrow to box 512, which holds a long song: Golden Hour (Live), 41 minutes

Check yourself

2 questions to try on the lesson page.

So what

"Go to a position" and "find a value" sound alike, but one is a single step and the other is a search. Most of the speed differences in this course, and most of the questions an interviewer asks, come back to that difference, and to the notes that say where to look.

Key terms

Cheat sheets