(^110) | Chapter 5: Searching
If time is critical and the collection is large, this extra comparison incurred for
each element will be noticeable, and so there is another solution. Instead of
placing anilvalue in an empty slot, place a specially identified element known as
thesentinel. The sentinel always returnsfalsewhen tested for equality to any
item. For example, if the searched-fortis known to be a positive integer, you
might use –1 as a sentinel to avoid the extra comparison.
Analysis
If the item being sought belongs to the collection and is equally likely to be found
at any of its indexed locations (alternatively, if it is equally likely to be emitted by
an iterator at any position), then on average SEQUENTIALSEARCH probes
elements (as we presented in Chapter 2). That is, you will inspect about half the
elements in the collection for each item you find. The best case is when the item
being sought is the first element in the collection. This algorithm exhibits linear
growth in the average and worst cases. If you double the size of the collection, this
should approximately double the amount of time spent searching.
To show SEQUENTIALSEARCHin action, we construct an ordered collection of
thenintegers in the range [1,n]. Although the collection is ordered, this informa-
tion is not used by the searching code. We ran a suite of 100 trials; in each trial we
execute 1,000 queries for a random targett, and of these 1,000 queries, 1,000p
are guaranteed to findtin the collection (indeed, the targettis negative for failed
searches). We aggregate the time to execute these queries and discarded the best
and worst performing trials. Table 5-1 shows the average of the remaining 98
trials at four specificpvalues. Note how the execution time approximately
doubles as the size of the collection doubles. You should also observe that for
each collection sizen, the worst performance occurs in the final column where the
targett does not exist in the collection.
Example 5-4. Sequential search with check for empty slot
def sequentialSearch(collection, t)
collection.each {
|i| if (i != nil) && (i == t) then return true; end
}
return false
end
- In Ruby, you have the advantage thatnilcan be used as a comparison value for any object. So the
extra comparison in Example 5-4 is really not needed.
Table 5-1. Sequential Search performance (in seconds)
n p=1.0 p=0.5 p=0.25 p=0.0
4,096 0.0081 0.0106 0.0111 0.0138
8,192 0.016 0.0223 0.0236 0.0297
1
2
---n^1
2+---
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use