Searching a List

Книга: Practical Programming, Fourth Edition

Назад: Chapter 13: Searching and Sorting

As you have already seen in Table 6, , Python lists have a method called index that searches for a particular item:

	index(value, start=0, stop=9223372036854775807, /) method of builtins.list
	instance
	Return first index of value.

	Raises ValueError if the value is not present.

Linear search is the simplest way to find a value in a list

List method index starts at the front of the list and examines each item in turn. For reasons that will soon become clear, this technique is called linear search. Linear search is used to find an item in an unsorted list. If there are duplicate values, the algorithm will find the leftmost one:

	>>> ['d', 'a', 'b', 'a'].index('a')
	1

You’ll write several versions of linear search to demonstrate how to compare different algorithms that all solve the same problem.

After you perform this analysis, you will see that you can search a sorted list much faster than an unsorted list.

An Overview of Linear Search

Linear search starts at index 0 and examines each item sequentially. At each index, ask this question: is the value you are looking for at the current index? You’ll see three variations of this. All of them use a loop of some kind, and they are all implementations of this function:

	from typing import Any

	def linear_search(lst: list, value: Any) -> int:
	"""Return the index of the first occurrence of value in lst, or return
	-1 if value is not in lst.

	>>> linear_search([2, 5, 1, -3], 5)
	1
	>>> linear_search([2, 4, 2], 2)
	0
	>>> linear_search([2, 5, 1, -3], 4)
	-1
	>>> linear_search([], 5)
	-1
	"""

	# examine the items at each index i in lst, starting at index 0:
	# is lst[i] the value we are looking for? if so, stop searching.

The algorithm in the function body describes what every variation will do to look for the value.

It is helpful to have a visual representation of how linear search works. (These pictures will be used throughout this chapter for both searching and sorting.)

Because these versions examine index 0 first, then index 1, then index 2, and so on, this means that partway through your searching process you encounter this situation (note that len(lst) is the index of the first item not on the list):

There is a part of the list that has been examined and another part that remains to be examined. Let’s use variable i to mark the current index.

Here’s a concrete example of searching for a value in a list that starts like this: [2, -3, 5, 9, 8, -6, 4, 15, …]. You don’t know how long the list is, but let’s say that after six iterations, you have examined items at indices 0, 1, 2, 3, 4, and 5. Index 6 is the index of the next item to examine:

That vertical line divides the list into two: the part you have examined and the part you haven’t. Because you stop when you find the value, you know that the value isn’t in the first part:

An invariant describes the data being used in a loop

This picture is sometimes referred to as an invariant of linear search. An invariant is something that remains unchanged throughout a process. But variable i is changing—how can that picture be an invariant? Here is a text version of the picture:

lst[0:i] doesn't contain value, and 0 <= i <= len(lst)

This word version states that you know the value wasn’t found before index i and that i is somewhere between 0 and the length of the list. If your code matches that word version, that word version is an invariant of the code, and so is the picture version.

You can use invariants to come up with the initial values of your variables. For example, with linear search, at the very beginning the entire list is unknown—you haven’t examined anything:

Variable i refers to 0 at the beginning, because then the section with the label value not here is empty; further, lst[0:0] is an empty list, which is precisely what you want according to the word version of the invariant. So, the initial value of i should be 0 in all of your versions of linear search.

The while Loop Version of Linear Search

Let’s develop your first version of linear search. You need to refine your comments to bring them closer to Python norms:

	Examine every index i in lst, starting at index 0:
	Is lst[i] the value you are looking for? if so, stop searching

Here’s a refinement:

	i = 0 # The index of the next item in lst to examine

	While the unknown section isn't empty, and lst[i] isn't
	the value you are looking for:
	add 1 to i

That’s easier to translate. The unknown section is empty when i == len(lst), so it isn’t empty as long as i != len(lst). Here is the code:

	from typing import Any

	def linear_search(lst: list, value: Any) -> int:
	"""Return the index of the first occurrence of value in lst, or return
	-1 if value is not in lst.

	>>> linear_search([2, 5, 1, -3], 5)
	1
	>>> linear_search([2, 4, 2], 2)
	0
	>>> linear_search([2, 5, 1, -3], 4)
	-1
	>>> linear_search([], 5)
	-1
	"""

	i = 0 # The index of the next item in lst to examine.

	# Keep going until we reach the end of lst or until we find value.
	while i != len(lst) and lst[i] != value:
	i = i + 1

	# If we fell off the end of the list, we didn't find value.
	if i == len(lst):
	return -1
	else:
	return i

This version uses variable i as the current index and marches through the values in lst, stopping in one of two situations: when you have run out of values to examine, or when you find the value you are looking for.

The first check in the loop condition, i != len(lst), makes sure that you still have values to look at; if you were to omit that check, then if value isn’t in lst, you would end up trying to access lst[len(lst)], which would result in an IndexError.

The second check, lst[i] != value, causes the loop to exit when value is found. The loop body increments i; enter the loop when you haven’t reached the end of lst, and when lst[i] isn’t the value you are looking for.

After the loop terminates, if i == len(lst), then value wasn’t in lst, so you return -1. Otherwise, the loop terminated because value was found at index i.

The for Loop Version of Linear Search

The first version evaluates two Boolean subexpressions each time the loop is executed. But the first check, i != len(lst), is almost unnecessary; it evaluates to True nearly every time through the loop, so the only effect it has is to make sure you don’t attempt to index past the end of the list. You can instead exit the function as soon as you find the value:

	i = 0 # The index of the next item in lst to examine

	For each index i in lst:
	If lst[i] is the value you are looking for:
	return i

	If you get here, value was not in lst, so you return -1

In this version, let’s use Python’s for loop to examine each index.

	from typing import Any

	def linear_search(lst: list, value: Any) -> int:
	# Same docstring as before
	for i in range(len(lst)):
	if lst[i] == value:
	return i

	return -1

With this version, you no longer need the first check because the for loop controls the number of iterations. This for loop version is significantly faster than your first version; you’ll see how much faster it is shortly.

Sentinel Search

The last linear search you will study is called the sentinel search. (A sentinel is a guard whose job it is to stand watch.) One problem with the while loop linear search is that you check i != len(lst) every time through the loop, even though it can never evaluate to False except when value is not in lst. So, let’s play a trick: add value to the end of lst before the search. That way, you are guaranteed to find it! You also need to remove it before the function exits so that the list looks unchanged to whoever called this function:

	Set up the sentinel: append value to the end of lst

	i = 0 # The index of the next item in lst to examine

	While lst[i] is not the value you are looking for:
	Add 1 to i

	Remove the sentinel

	return i

Let’s translate that to Python:

	from typing import Any

	def linear_search(lst: list, value: Any) -> int:
	# Same docstring as before

	# Add the sentinel.
	lst.append(value)

	i = 0

	# Keep going until we find value.
	while lst[i] != value:
	i += 1

	# Remove the sentinel.
	lst.pop()

	# If we reached the end of the list we didn't find value.
	if i == len(lst):
	return -1
	return i

All three of your linear search functions are correct. Which one you prefer is essentially a matter of taste: some programmers dislike returning in the middle of a loop—they won’t like the second version. Others dislike modifying parameters in any way—they won’t like the third version. Still, others may dislike the extra check that occurs in the first version.

Timing the Searches

Here is a program that you can use to time the three searches on a list with about ten million values:

	import time
	import linear_search_1
	import linear_search_2
	import linear_search_3

	from typing import Callable, Any

	def time_it(search: Callable[list[list, Any]], L: list, v: Any) -> float:
	"""Time how long it takes to run function search to find
	value v in list L.
	"""

	t1 = time.perf_counter()
	search(L, v)
	t2 = time.perf_counter()
	return (t2 - t1) * 1000.0

	def print_times(v: Any, L: list) -> None:
	"""Print the number of milliseconds it takes for linear_search(v, L)
	to run for list.index, the while loop linear search, the for loop
	linear search, and sentinel search.
	"""

	# Get list.index's running time.
	t1 = time.perf_counter()
	L.index(v)
	t2 = time.perf_counter()
	index_time = (t2 - t1) * 1000.0

	# Get the other three running times.
	while_time = time_it(linear_search_1.linear_search, L, v)
	for_time = time_it(linear_search_2.linear_search, L, v)
	sentinel_time = time_it(linear_search_3.linear_search, L, v)

	print("{0}\t{1:.2f}\t{2:.2f}\t{3:.2f}\t{4:.2f}".format(
	v, while_time, for_time, sentinel_time, index_time))

	L = list(range(10000001)) # A list with just over ten million values

	print_times(10, L) # How fast is it to search near the beginning?
	print_times(5000000, L) # How fast is it to search near the middle?
	print_times(10000000, L) # How fast is it to search near the end?

This program uses the function perf_counter in the built-in module time. The function time_it will call whichever search function it’s given on v and L and returns the time it took for that search. The function print_times calls time_it with the various linear search functions you have been exploring and prints the corresponding search times.

Linear Search Running Time

The running times of the three linear searches are compared with those of Python’s list.index in Table 9, .

This comparison used a list of 10,000,001 items and three test cases: an item near the front, an item roughly in the middle, and the last item. Except for the first case, where the speeds differ by very little, your while loop linear search takes about six times as long as the one built into Python. The for loop search and sentinel search take about three and three and a half times longer, respectively.

Table 9. Running Times for Linear Search (in milliseconds)

Case	while	for	sentinel	list.index
First	0.01	0.00	0.00	0.01
Middle	262.31	131.36	153.95	44.19
Last	525.36	262.34	307.87	88.17

What is more interesting is the way the running times of these functions increase with the number of items they have to examine. Roughly speaking, when they have to look through twice as much data, every one of them takes twice as long. This observation is reasonable because indexing a list, adding 1 to an integer, and evaluating the loop control expression require the computer to do a fixed amount of work. Doubling the number of times the loop has to be executed, therefore, doubles the total number of operations, which in turn should double the total running time. That is why this kind of search is called linear: the time required to perform it grows linearly with the amount of data being processed.

Назад: Chapter 13: Searching and Sorting

Дальше: Binary Search