Space versus Time
Not just for Computer Scientists.
I tend to ponder quite a bit during meals. On my road to enlightenment/lunch today, a blob of text caught my eye outside the restaurant:
That is quite the list of open hours. Let’s say we had a “processor” that took as input the current day of the week and as output returned the hours for the restaurant. What are the steps the processor needs to execute to find the open hours of this pizzeria?
- Jump to the row that matches the input day
- Output the hours in the second column
Pretty simple, right? There’s a cost though, which we can measure by the number of rows that are in the table. There are 7, one for each day of the week. Remarkably though (or not if you consider the lunch and dinner rush), 6 of the 7 days’ opened hours are the same. Maybe we can be more efficient in signage space?
The Prolific Oven introduced a new operator, a date range. Here are our processor steps now:
- For each row in the table, check if the input day fits within the date range
- If we found a row that fits, output the hours in the second column
Our signage has reduced to 4 rows (even more so if The Prolific Oven’s hours were as simple as Premier Pizza’s) but our program’s complexity has increased. It takes a bit more time to figure out the hours.
One last example from a Silicon Valley lunch titan:
Our processor’s steps are:
- Output 11am-10pm.
There’s still a cost here! To do this, our processor had to understand a new term, “daily”, which is in fact not one of the 7 days of the week. If we optimize for this job by teaching that concept to the processor though, we have the simplest signage and the shortest compute time.
Analogies have holes, but if I may indulge my inner lecturer, we have 3 opposing concepts to optimize:
- Data memory — How much signage do we want to display?
- Compute time — How many steps does the processor needs to take?
- Instruction memory — What all is the processor capable of understanding?
Maybe John von Neumann would have enjoyed Chipotle.
