[Tutor] binary vs. linear search

[Tim Wilson]

On Fri, Aug 23, 2002 at 07:06:16PM -0700, Sean 'Shaleh' Perry wrote:
> On Friday 23 August 2002 06:57 pm, Tim Wilson wrote:
> >
> > Here are the two algorithms:
> >
> > def isWord(word, wordList):    # binary search
> >     wordList.sort()
> >     item_insert_point = bisect.bisect(wordList, word)
> >     is_present = wordList[item_insert_point-1:item_insert_point] ==
> > [word]
> >     if is_present:
> >         return 1
> >     return 0
> >
> >
> > def isWord(word, wordList):    # regular python search
> >     if word in wordList:
> >         return 1
> >     return 0
> >
> >
> > The results for looking for 6,175 words in a list of 45,392 words are:
> >
> > binary:  3m 25s
> > regular: 2m 58s
> >
> > I was surprised to find the binary search slower in this case. Can
> > anyone explain why?
> >
> 
> The binary search does more work.  You call list.sort(), bisect() and even do 
> a list splice.  To make it truly fair passing the two functions a sorted 
> list.

Thanks Sean. I removed the wordList.sort() from the binary search
function and the time for execution dropped to just over 1 sec.!!!!
Yikes! Now that I think about it, the time to sort a 6,175 item list
6,175 times is signficant. Duh. As long as I make sure I pass a sorted
list to the function, the performance gain over the regular linear
search is impressive to say the least.

-Tim

-- 
Tim Wilson      |   Visit Sibley online:   | Check out:
Henry Sibley HS |  http://www.isd197.org   | http://www.zope.com
W. St. Paul, MN |                          | http://slashdot.org
wilson@visi.com |  <dtml-var pithy_quote>  | http://linux.com