The Feature Is Slow: Which Structure Fixes It?

Fix a feature that's slow because of how its data is kept, the way developers do: find the job it does most, try the plain fixes against it, and choose the structure whose cost card makes that job cheap, with every cost card from the course side by side.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Choose a data structure for a job by starting from the operation it does most
  • Justify a choice of structure with the Big-O of its main operations

Key takeaways

  • A slow feature is usually a job done often on the wrong structure: a list that's read from the top on every check, or a sorted list that slides everything along on every add.
  • Start from the job, not the structure. List what the code does to its data, and find the operation it does most often.
  • Choose the structure whose cost card makes that operation cheap, then check that the other operations, the order and the memory are good enough.
  • Order matters too. Whether the job needs first-come order, newest-first, sorted or no order at all often names the structure by itself.
  • Justify a choice with Big-O, such as "a set, because checking a name is O(1) on average and we check one on every sign-up."

Before this: every structure in this course arrived as the answer to one problem, and the lesson told you which. At work, the problem arrives alone.

Here's a ticket from a game studio, the morning its new game launches:

Sign-up is slow, and getting slower. 100,000 players already have accounts. When a new player picks a username, the form checks that nobody has it yet, and today every check takes longer than the one before. We expect another 100,000 sign-ups by tonight.

Nobody at work says "write me a set". They say "the leaderboard is slow", "sign-up takes forever when the site is busy", or "add a 'people you may know' box", and choosing the structure is your job. It's also what a technical interview tests, and what your teammates look for in a code review. This lesson works this ticket the way a developer would, and the method it uses works on every ticket after it.

What would you try?

Keep the list, and read it. That's today's code: the taken usernames in a list, read from the top on every check. A name that's taken early is found fast, but a free name, the one every new player hopes for, is only "free" after all 100,000 names are read. That's O(n) per check, and n grows with every sign-up, which is why each check is slower than the last.

Sort the list, and halve it. Binary search from Module 4 finds a name in about 17 looks among 100,000, O(log n). But a new player's name has to go into its place in the order, and every name after it slides one spot along: about 50,000 moves per sign-up, O(n). With 100,000 sign-ups tonight, that's about 5 billion moves. Checking got fast; adding got slow.

Keep the names in a set. A set (Have I Seen This Before? Sets) turns a name into the one place to look: checking is O(1) on average, and so is adding the new name. It doesn't keep the names in order, and nobody asked for that.

What we tried Check a name Add a name Where it breaks
A list, read from the top O(n): 100,000 reads for a free name O(1) every check, all day
A sorted list, halved O(log n): about 17 looks O(n): about 50,000 moves tonight's 100,000 sign-ups
A set O(1) on average O(1) on average nowhere for this job

The questions that lead to it

Look at what settled the choice. It wasn't "which structure is best?" It was four questions about the job:

  • What does the job do most? Check a name, on every sign-up.
  • What else does it do, and how often? Add the new name, as often.
  • What can be slow, or isn't needed at all? Listing every username in order: nobody asked.
  • Which structure's cost card makes the first two cheap? A set.

Those questions work on any ticket.

The method, named

This habit is what developers mean by choosing a data structure, and it's a method, not a talent:

  1. List what the job does to its data: add, find, remove, take the next one, list in order.
  2. Find the operation it does most, or the one that has to be fastest.
  3. Pick the structure whose cost card makes that operation cheap.
  4. Check the rest: the other operations, the order the job needs, and the memory.
  5. Start with your language's built-in version of it. Write your own only when there isn't one.

Every cost card, side by side

Step 3 needs the cost cards, so here they all are. n is the number of items, and "on average" means the usual case, as in Finding Maya's Coat Without a Ticket: Hash Tables.

Structure Fast at Slow at Order
Array, growing array (a list) Read by position O(1); add at the end O(1) on average Find by value O(n); add or remove at the front O(n) The order you put things in
Linked list Add or remove at the front O(1) Read by position O(n); find by value O(n) The order you put things in
Stack Push, pop and peek at the top O(1) Anything below the top Newest first
Queue Add at the back, take from the front O(1) Anything in the middle First come, first served
Hash table: dictionary or set Add, find and remove by key O(1) on average Anything that needs order; finding by value O(n) None
Balanced binary search tree (sorted map or set) Add, find and remove O(log n); smallest and largest O(log n) Reading by position Sorted
Heap (priority queue) Peek at the smallest O(1); add and take the smallest O(log n) Finding any other item O(n) Only "smallest first"
Trie Find a word, or every word with a prefix, in O(length of the word) Memory: a node per letter Alphabetical, if walked in order
Graph (adjacency list) A vertex's neighbors O(k); searches O(V + E) Checking one pair O(k), unless each list is a set None

Every cost card from the course in one table, a row per structure (array, linked list, stack, queue, hash table, binary search tree, heap, trie and graph) with what each is fast at, what it is slow at with its Big-O, and the order it keeps, so the structures can be compared at a glance

The difference in code

Here's the ticket's job: is a name taken? The program keeps 100,000 taken usernames in a list and in a set, then checks two names. It counts the names the list reads; the set answers with one lookup either way.

List<string> takenList = new List<string>();
for (int number = 0; number < 100000; number++)
{
    takenList.Add("user" + number);
}
HashSet<string> takenSet = new HashSet<string>(takenList);

foreach (string wanted in new string[] { "river_fox", "user42" })
{
    int reads = 0;
    foreach (string name in takenList)
    {
        reads++;
        if (name == wanted)
        {
            break;
        }
    }
    string answer = takenSet.Contains(wanted) ? "taken" : "free";
    Console.WriteLine(wanted + ": the list read " + reads + " names, the set made 1 lookup, " + answer);
}
river_fox: the list read 100000 names, the set made 1 lookup, free
user42: the list read 43 names, the set made 1 lookup, taken
void main() {
    List<String> takenList = new ArrayList<>();
    for (int number = 0; number < 100000; number++) {
        takenList.add("user" + number);
    }
    Set<String> takenSet = new HashSet<>(takenList);

    for (String wanted : new String[] {"river_fox", "user42"}) {
        int reads = 0;
        for (String name : takenList) {
            reads++;
            if (name.equals(wanted)) {
                break;
            }
        }
        String answer = takenSet.contains(wanted) ? "taken" : "free";
        IO.println(wanted + ": the list read " + reads + " names, the set made 1 lookup, " + answer);
    }
}
river_fox: the list read 100000 names, the set made 1 lookup, free
user42: the list read 43 names, the set made 1 lookup, taken
taken_list = []
for number in range(100000):
    taken_list.append(f"user{number}")
taken_set = set(taken_list)

for wanted in ["river_fox", "user42"]:
    reads = 0
    for name in taken_list:
        reads += 1
        if name == wanted:
            break
    answer = "taken" if wanted in taken_set else "free"
    print(f"{wanted}: the list read {reads} names, the set made 1 lookup, {answer}")
river_fox: the list read 100000 names, the set made 1 lookup, free
user42: the list read 43 names, the set made 1 lookup, taken
const takenList = [];
for (let number = 0; number < 100000; number++) {
  takenList.push(`user${number}`);
}
const takenSet = new Set(takenList);

for (const wanted of ["river_fox", "user42"]) {
  let reads = 0;
  for (const name of takenList) {
    reads++;
    if (name === wanted) {
      break;
    }
  }
  const answer = takenSet.has(wanted) ? "taken" : "free";
  console.log(`${wanted}: the list read ${reads} names, the set made 1 lookup, ${answer}`);
}
river_fox: the list read 100000 names, the set made 1 lookup, free
user42: the list read 43 names, the set made 1 lookup, taken
const takenList: string[] = [];
for (let number = 0; number < 100000; number++) {
  takenList.push(`user${number}`);
}
const takenSet = new Set<string>(takenList);

for (const wanted of ["river_fox", "user42"]) {
  let reads = 0;
  for (const name of takenList) {
    reads++;
    if (name === wanted) {
      break;
    }
  }
  const answer = takenSet.has(wanted) ? "taken" : "free";
  console.log(`${wanted}: the list read ${reads} names, the set made 1 lookup, ${answer}`);
}
river_fox: the list read 100000 names, the set made 1 lookup, free
user42: the list read 43 names, the set made 1 lookup, taken

A free name is the worst case for the list: it reads all 100,000 before it can say "free". On launch day, that's 100,000 reads per visitor, while the set does about the same small amount of work whatever its size. Both give the same answers, so a test with ten names would never show the difference. That's why the choice is made from the cost card, before the site is busy.

Try it. Change 100000 to 1000000 and run it again. The list's count for river_fox grows ten times; the set's lookup doesn't.

When the plain list is the right answer

A list is often fine, and the method says so when it is. A teacher's list of 30 names, read once a day in the order they joined, has nothing to speed up, and a set would lose the order. What's wrong is "a list, because lists are what I know". What's right is "a list, because we only ever add at the end and read them all in order".

Saying why, out loud

A choice isn't finished until you can say it in one sentence with its Big-O: "a set, because every sign-up checks a name, and checking and adding are both O(1) on average". Interviewers ask for exactly that sentence, and so do teammates reading your code a year later. When two structures both fit, say what each costs and pick the one that's cheap for the operation done most.

The next lessons hand you problems the course hasn't shown, and this time the structure is yours to choose.

Check yourself

2 questions to try on the lesson page.

So what

Every structure in this course is the right answer to some job. When a feature is slow, start from the job it does most, try the plain fixes against it, and say why with Big-O: that's how you find which one.

Key terms

Cheat sheets

Related