SECTION 07 / 31

Create on the first visit; accumulate on later visits

1 min read
Illustrative cricket scores: 20 followed by 30 gives an accumulated total 50. These are constructed examples, not real match results.
Illustrative cricket scores: 20 followed by 30 gives an accumulated total 50. These are constructed examples, not real match results.
runs = {}
foreach scoreRow in matchRows {
    player = scoreRow.Player
    if (isKey(runs,player)) {
        runs[player] = runs[player] + scoreRow.Runs
    }
    else {
        runs[player] = scoreRow.Runs
    }
}

For Kohli’s first illustrative 20, create runs[Kohli]=20. For a later 30, read 20 and replace it with 20+30=50. Writing runs[Kohli]=30 would erase the earlier total. Writing runs[Kohli]=runs[Kohli]+20 before the key exists would read an absent value.

The course assumes direct dictionary lookup, update and built-in isKey take constant time. “Random access” means direct access by a key; it does not mean choosing a random key. The lecture’s manual isKey scans keys(D), sets found=True on a match and uses exitloop. That manual version can inspect every key, so it is linear in the number of keys. Keep the assumed built-in and the demonstration scan separate.

Procedure manualIsKey(D,k)
    found = False
    foreach candidate in keys(D) {
        if (candidate == k) {
            found = True
            exitloop
        }
    }
    return(found)
End manualIsKey

These are the course’s abstract data-structure assumptions. Real languages can implement lists and dictionaries differently. Iterating over every key still costs work for every entry; a constant-time lookup does not make a whole scan constant time.

Try it yourself

A dictionary already stores runs[A]=20. What does runs[A]=30 leave?

Show explained answer

30. To accumulate a new 30, assign runs[A]=runs[A]+30, giving 50.

Try it yourself

Does manualIsKey prove dictionary lookup is constant time?

Show explained answer

No. It is a correct linear search demonstration. The efficient built-in isKey is an assumed primitive.

Try it yourself

If there are m keys and a key is missing, how many candidates can the manual search inspect?

Show explained answer

All m keys. Only then can it report absence.

YOUR STUDY PROGRESS

Finished this section? Save your progress.

Back to top ↑