[Tutor] binary vs. linear search

[Tim Wilson]

Hi everyone,

I was looking through my brand-new, still-shiny copy of the Python
Cookbook tonight and discovered a very short little algorithm for doing
a binary search (p. 46). I've been playing around with a python module
that's useful for solving word puzzles of the type you hear on NPR's
Weekend Edition Sunday (with Will Shortz). I had the idea that some of
these puzzles would make excellent assignments for my beginning
programming students.

A recent one required finding a six-letter word that after moving the
first letter to the end and finding a new word and then moving the front
letter to the back again would make another new word. There are a couple
such words.

To solve this with Python I loaded the dictionary from my Linux system
into a Python list (45,392 words), pulled out all the six-letter words
(6,175 of them), moved the letters, and checked to see if the altered
words existed in the dictionary list.

After discovering the binary search algorithm I decided to compare its
performance to my first attempt. (For testing purposes I moved only one
letter, producing a larger list to check against the dictionary.)

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?

-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