Advertisement
Guest User

Ghost speed comparison

a guest
Jul 31st, 2011
449
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.58 KB | None | 0 0
  1. # see http://stackoverflow.com/questions/6722985/fastest-way-in-python-to-find-a-startswith-substring-in-a-long-sorted-list-of-s
  2. import random
  3. import time
  4. import string
  5. from bisect import bisect_left
  6.  
  7. WORDLIST_FILENAME = "words.txt"
  8.  
  9. def load_words():
  10.     """
  11.    Returns a list of valid words. Words are strings of lowercase letters.
  12.    
  13.    Depending on the size of the word list, this function may
  14.    take a while to finish.
  15.    """
  16.     print "Loading word list from file..."
  17.     # inFile: file
  18.     inFile = open(WORDLIST_FILENAME, 'r', 0)
  19.     # wordlist: list of strings
  20.     wordlist = []
  21.     for line in inFile:
  22.         wordlist.append(line.strip().lower())
  23.     print "  ", len(wordlist), "words loaded."
  24.     return wordlist
  25.  
  26. def frag_wordexists_Peter_simple(wordlist, word_fragment):
  27.     return any(w.startswith(word_fragment) for w in wordlist)
  28.  
  29. def frag_wordexists_Peter_bisect_left(wordlist, word_fragment):
  30.     try:
  31.         return wordlist[bisect_left(wordlist, word_fragment)].startswith(word_fragment)
  32.     except IndexError:
  33.         return False # word_fragment is greater than all entries in wordlist
  34.  
  35. def trim_list_comprehension(wordlist, word_fragment):
  36.     """returns the wordlist containing only words starting with 'word_fragment'"""
  37.     wordlist = [w for w in wordlist if w.startswith(word_fragment)]
  38.     return wordlist
  39.  
  40. def trim_bisect(wordlist, word_fragment):
  41.     """returns the wordlist containing only words starting with 'word_fragment'"""
  42.     wordlist[bisect_left(wordlist, word_fragment):
  43.          bisect_left(wordlist, word_fragment[:-1] + chr(ord(word_fragment[-1])+1))]
  44.     return wordlist
  45.  
  46. # Actually load the dictionary of words and point to it with
  47. # the wordlist variable so that it can be accessed from anywhere
  48. # in the program.
  49. wordlist = load_words()
  50. trimwordlist_comprehension = wordlist[:]
  51. trimwordlist_bisect = wordlist[:]
  52. peter_simple_total = peter_bisect_total = trim_comp_total = trim_bisect_total = 0
  53.  
  54. for word_fragment in ("p", "py", "pyt", "pyth", "pytho"):
  55.     print "Testing '" + word_fragment + "' with Peter's simple test"
  56.     start = time.time()
  57.     if frag_wordexists_Peter_simple(wordlist, word_fragment):
  58.         runtime = time.time() - start
  59.         print runtime
  60.         peter_simple_total += runtime
  61.  
  62.     print "Testing '" + word_fragment + "' with Peter's bisect left test"
  63.     start = time.time()
  64.     if frag_wordexists_Peter_bisect_left(wordlist, word_fragment):
  65.         runtime = time.time() - start
  66.         print runtime
  67.         peter_bisect_total += runtime
  68.  
  69.     print "Testing '" + word_fragment + "' with trimming the list using a list comprehension"
  70.     start = time.time()
  71.     trimwordlist_comprehension = trim_list_comprehension(trimwordlist_comprehension, word_fragment)
  72.     if len(trimwordlist_comprehension):
  73.         runtime = time.time() - start
  74.         print runtime
  75.         trim_comp_total += runtime
  76.  
  77.     print "Testing '" + word_fragment + "' with trimming the list using Neil G's bisect"
  78.     start = time.time()
  79.     trimwordlist_bisect = trim_bisect(trimwordlist_bisect, word_fragment)
  80.     if len(trimwordlist_bisect):
  81.         runtime = time.time() - start
  82.         print runtime
  83.         trim_bisect_total += runtime
  84.  
  85. print ""
  86. print 'The totals for all strings "p", "py", "pyt", "pyth", "pytho" are as follows:'
  87. print "In total, Peter's simple test took " + str(peter_simple_total)
  88. print "In total, Peter's bisect left test took " + str(peter_bisect_total)
  89. print "In total, the list comprehension took " + str(trim_comp_total)
  90. print "In total, Neil G's bisect took " + str(trim_bisect_total)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement