Algorithmic Efficiency and Heuristics: Reasonable and Unreasonable Time

Q: What is practice exercises in Python?

Exam topics: 3.17 Algorithmic Efficiency (AAP-4.A)

Intermediate35 min3 exercises45 XP

Prerequisites

Python For Loops: Iterate Over Anything with Examples Nested Loops: Patterns, Performance, and When to Avoid Them Python Functions: Define, Call, and Return Values Python itertools: Powerful Tools for Working with Iterables

0/3 exercises

Efficiency is how much computing work an algorithm needs, and it decides whether a program answers in the blink of an eye or would need longer than the age of the universe. Two correct algorithms for the same job can sit at opposite ends of that range.

What is the difference between a problem and an instance?

A problem is a general description of a task that may or may not be solvable with an algorithm: "sort a list of numbers" or "find the shortest route between two places". An instance of a problem includes specific input: sorting the list [29, 4, 17, 8], or finding the shortest route from your house to school on today's map.

Problems also come in two kinds that the exam names:

A decision problem has a yes-or-no answer. "Is there a route from home to the stadium shorter than 10 km?" "Does this playlist contain this song?"

An optimization problem asks for the best solution out of many possible ones. "What is the shortest route from home to the stadium?" "Which seats are cheapest for a group of six?"

Here is one decision question and one optimization question about the same data:

A decision question and an optimization question

routes_km = {"Main St": 7.2, "River Rd": 5.9, "Hill Ave": 8.4}

# Decision problem: yes or no.

short_route_exists = False

for name in routes_km:

if routes_km[name] < 6:

short_route_exists = True

print("Is there a route under 6 km?", short_route_exists)

# Optimization problem: the best of many.

best = "Main St"

for name in routes_km:

if routes_km[name] < routes_km[best]:

best = name

print("Shortest route:", best, routes_km[best], "km")

Output

Is there a route under 6 km? True
Shortest route: River Rd 5.9 km

How do you measure an algorithm's efficiency?

Efficiency is an estimate of the computational resources an algorithm uses, such as time or memory. Since a bigger input means more work, efficiency is usually described in terms of the size of the input: "for a list of n names, this algorithm does about n checks".

Computer scientists determine an algorithm's efficiency through formal, mathematical reasoning. You can also measure it informally by counting how many times a statement or group of statements runs. The program below counts the steps of three algorithms: one loop over n items, a loop inside a loop, and a loop over every possible group (subset) of the n items, where each item is either in or out of the group.

Counting steps as n grows

def steps_one_loop(n):

steps = 0

for i in range(n):

steps += 1

return steps

def steps_nested_loops(n):

steps = 0

for i in range(n):

for j in range(n):

steps += 1

return steps

def steps_every_subset(n):

steps = 0

for group in range(2 ** n): # each item in or out: 2 x 2 x ... x 2 groups

steps += 1

return steps

print(f"{'n':>3} {'one loop':>9} {'nested loops':>13} {'every subset':>13}")

for n in [4, 8, 12, 16]:

print(f"{n:>3} {steps_one_loop(n):>9} {steps_nested_loops(n):>13} "

f"{steps_every_subset(n):>13}")

Output

  n  one loop  nested loops  every subset
  4         4            16            16
  8         8            64           256
 12        12           144          4096
 16        16           256         65536

Each time n goes up by 4, the one-loop count goes up by 4, the nested-loop count grows a few times over, and the every-subset count is multiplied by 16. Adding one item doubles the number of subsets.

What makes a running time reasonable?

Algorithms whose step counts grow like a polynomial or slower are said to run in a reasonable amount of time. That includes constant (the same number of steps for any n), linear (n steps), square (n times n) and cube (n times n times n). Algorithms with exponential growth (like 2 to the power n) or factorial growth (n times n - 1 times n - 2, down to 1) are examples of algorithms that run in an unreasonable amount of time.

The difference is not about today's computers being slow. Here is how long each growth rate takes on a computer doing a billion steps every second:

From under a second to over a trillion years

import math

STEPS_PER_SECOND = 1_000_000_000

YEAR = 60 * 60 * 24 * 365

def how_long(steps):

seconds = steps / STEPS_PER_SECOND

if seconds < 1:

return "under a second"

if seconds < YEAR:

return f"{seconds / 86400:,.1f} days"

if seconds < 1e12 * YEAR:

return f"{seconds / YEAR:,.0f} years"

return "over a trillion years"

for n in [10, 20, 40, 60, 80]:

print(f"n = {n}: n squared {how_long(n ** 2)}, 2 to the n {how_long(2 ** n)},"

f" n! {how_long(math.factorial(n))}")

Output

n = 10:  n squared under a second,  2 to the n under a second,  n! under a second
n = 20:  n squared under a second,  2 to the n under a second,  n! 77 years
n = 40:  n squared under a second,  2 to the n 0.0 days,  n! over a trillion years
n = 60:  n squared under a second,  2 to the n 37 years,  n! over a trillion years
n = 80:  n squared under a second,  2 to the n 38,334,786 years,  n! over a trillion years

The universe is about 14 billion years old. A computer a thousand times faster only moves an exponential algorithm about 10 items further before it hits the same wall, because 2 to the power 10 is about 1,000.

Different correct algorithms for the same problem can have very different efficiencies. Both functions below decide whether a list of 1,000 student IDs contains a duplicate. The first compares every pair of IDs. The second walks the list once and remembers the IDs it has already seen:

Two correct algorithms, very different step counts

def has_duplicate_pairs(items):

checks = 0

for i in range(len(items)):

for j in range(i + 1, len(items)):

checks += 1

if items[i] == items[j]:

return True, checks

return False, checks

def has_duplicate_seen(items):

checks = 0

seen = set()

for item in items:

checks += 1

if item in seen:

return True, checks

seen.add(item)

return False, checks

ids = list(range(1000)) # 1,000 different IDs, so no duplicates

print("Compare every pair:", has_duplicate_pairs(ids))

print("Remember what was seen:", has_duplicate_seen(ids))

Output

Compare every pair: (False, 499500)
Remember what was seen: (False, 1000)

Same answer, but 499,500 checks against 1,000. Both are still reasonable (square and linear), so for 1,000 IDs either one finishes quickly; for a million IDs the gap becomes hours against a moment.

When is a heuristic the smart choice?

Some problems cannot be solved in a reasonable amount of time because there is no efficient algorithm for them. For those, people look for an approximate solution: a good answer, found quickly, instead of the perfect answer, found never.

A famous example is planning a delivery route: visit every stop once and come back home, driving the shortest total distance. Nobody has found an efficient algorithm that always gives the shortest route. The sure way is to try every order of the stops, and the number of orders grows factorially: 6 stops have 720 orders, 10 stops have 3,628,800, and 20 stops have more than 2 billion billion.

A heuristic is an approach that produces a solution that is not guaranteed to be the best, used when a technique that always finds the best solution is impractical. One simple heuristic for routes is nearest neighbor: from wherever you are, drive to the closest stop you have not visited yet. First, the sure way, checking every order of 6 stops (distances in km):

Brute force: try every order

import math

from itertools import permutations

stops = {

"Home": (1, 3),

"Library": (2, 4),

"Bakery": (3, 7),

"Park": (0, 0),

"School": (1, 5),

"Pool": (8, 5),

"Museum": (0, 8),

}

def route_length(route):

total = 0

for i in range(len(route) - 1):

total += math.dist(stops[route[i]], stops[route[i + 1]])

return total

checked = 0

best = None

for order in permutations(list(stops)[1:]):

route = ["Home"] + list(order) + ["Home"]

checked += 1

if best is None or route_length(route) < route_length(best):

best = route

print(f"Checked {checked} routes")

print("Shortest:", " -> ".join(best), f"({route_length(best):.1f} km)")

Output

Checked 720 routes
Shortest: Home -> Library -> School -> Museum -> Bakery -> Pool -> Park -> Home (27.1 km)

Now the heuristic. It never compares whole routes: at each stop it looks only at the distances to the stops still left. This box uses stops and route_length from the box above, so run that one first.

Heuristic: always go to the closest stop

def nearest_neighbor_route():

route = ["Home"]

unvisited = list(stops)[1:]

while unvisited:

here = stops[route[-1]]

closest = unvisited[0]

for name in unvisited:

if math.dist(here, stops[name]) < math.dist(here, stops[closest]):

closest = name

route.append(closest)

unvisited.remove(closest)

return route + ["Home"]

quick = nearest_neighbor_route()

print("Nearest neighbor:", " -> ".join(quick), f"({route_length(quick):.1f} km)")

print(f"That is {route_length(quick) / route_length(best) - 1:.0%} longer than the best route")

Output

Nearest neighbor: Home -> Library -> School -> Bakery -> Museum -> Park -> Pool -> Home (33.5 km)
That is 24% longer than the best route

The nearest-neighbor route is longer than the best one, because one greedy choice near the start leaves an expensive trip back at the end. But the heuristic did 21 distance comparisons in total (6 + 5 + 4 + 3 + 2 + 1), while the sure way built 720 complete routes. With 60 stops, the sure way would need more routes than there are atoms in the Earth; nearest neighbor would need fewer than 2,000 comparisons. A route that is a bit longer, delivered today, beats a perfect route delivered never.

Specific heuristics like nearest neighbor are not on the exam. What the exam asks is when a heuristic is the right call: when finding the guaranteed best answer would take an unreasonable amount of time.

Check your understanding

Which of the following is an instance of a problem, rather than a general problem?

AFinding the largest number in a listBFinding the largest number in the list [8, 3, 12, 5]CSorting a list of names into alphabetical orderDDeciding whether a whole number is prime

Which of the following is an optimization problem?

AIs there a seating plan in which no two friends sit next to each other?BWhat is the cheapest way to buy 30 pencils from packs of 4, 6 and 10?CDoes this list of usernames contain the name "skater7"?DIs 91 evenly divisible by 7?

Each option describes how many steps an algorithm takes for an input of n items. Which algorithms run in a reasonable amount of time? Select two answers.

Select 2 answers.

An³ steps (n times n times n)B2ⁿ steps (2 multiplied by itself n times)Cn! steps (n times n - 1 times n - 2, down to 1)D50n steps (50 times n)

How many times does the statement count ← count + 1 run in this code segment?

count ← 0
REPEAT 5 TIMES
{
  REPEAT 4 TIMES
  {
    count ← count + 1
  }
  count ← count + 1
}
DISPLAY(count)

A9B20C25D45

Run this pseudocode

The procedure below is called with a list of n numbers. How many times does total ← total + 1 run?

PROCEDURE countPairs(numbers)
{
  total ← 0
  FOR EACH a IN numbers
  {
    FOR EACH b IN numbers
    {
      total ← total + 1
    }
  }
  RETURN(total)
}

AnBn + nCn times nD2 multiplied by itself n times

Run this pseudocode

An algorithm finds the best team by checking every possible group of members in a club of n members. One more person joins the club. What happens to the number of groups the algorithm checks?

AIt doubles.BIt goes up by 1.CIt goes up by n.DIt stays the same.

A delivery company plans a route through 60 stops each morning. Checking every possible order of the stops would take far too long. Which approach is most appropriate?

AUse a heuristic that quickly builds a short route, even though it may not be the shortest possibleBCheck every possible order on a faster computer, since speed is the only obstacleCGive up, because no algorithm can produce any route through 60 stopsDVisit the stops in alphabetical order, because every order has the same total distance

Which of the following best describes a heuristic?

AAn approach that finds a good solution in a reasonable time, without a guarantee that it is the best solutionBAn algorithm that always finds the best solution by checking every possibilityCA problem for which no algorithm can ever give a correct answerDA method that makes any exponential algorithm run in polynomial time while still guaranteeing the best answer

Practice exercises

How Many Routes?

Write Code

Write count_routes(stops) that returns how many different orders there are to visit stops places. The first place can be any of the stops, the second any of the remaining stops - 1, and so on, so the answer is stops x (stops - 1) x ... x 1. Use a loop.

count_routes(3)  ->  6
count_routes(5)  ->  120

def count_routes(stops):

# Multiply stops x (stops - 1) x ... x 1

pass

Count the Pair Checks

Write Code

The "compare every pair" duplicate check from the lesson runs this loop over a list of n items:

for i in range(n):
    for j in range(i + 1, n):
        checks += 1

Write pair_checks(n) that returns how many times checks += 1 runs. You can run the loop and count, or find a pattern.

pair_checks(4)   ->  6
pair_checks(10)  ->  45

def pair_checks(n):

# Return how many times checks += 1 runs for n items

pass

Nearest Neighbor Route

Write Code

Write nearest_neighbor_route(stops). stops is a dictionary from a place name to its (x, y) position, and the first key is the starting point. Build a route with the nearest-neighbor heuristic: from the current place, go to the closest place not visited yet, until every place is visited, then return to the start.

Return the route as a list of names, starting and ending with the first key. If two places are equally close, choose the one that comes first in the dictionary. Use math.dist(a, b) for the distance between two positions.

nearest_neighbor_route({"A": (0, 0), "B": (5, 0), "C": (1, 0)})
->  ['A', 'C', 'B', 'A']

import math

def nearest_neighbor_route(stops):

# Start at the first key, keep going to the closest unvisited place

pass

Exam topics: 3.17 Algorithmic Efficiency (AAP-4.A)

What is the difference between a problem and an instance?

How do you measure an algorithm's efficiency?

What makes a running time reasonable?

When is a heuristic the smart choice?

Check your understanding

Practice exercises

Related Tutorials