Python

Effiency in list searching

Please support our Python advertiser: Programming Forums - DaniWeb Sister Site

Thread Solved

•

Join Date: Oct 2008

Posts: 13

Reputation: Devlan is an unknown quantity at this point

Solved Threads: 0

Devlan

Offline

Newbie Poster

Effiency in list searching

Oct 12th, 2008

A real simple one, just a question of understanding the python syntax I suppose. I won't waste your time by throwing the whole program at you, I think my question can be boiled down to this:

Help with Code Tags

(Toggle Plain Text)

a = ["cat"]
b = ["bark"]
wordinsa = input("Word: ")
a.append(wordinsa)
wordinsb = input("Word: ")
b.append(wordinsb)
wordq = input("Try: ")
if wordq in a:
    c = a.index(wordq)
    print wordq
    print
    print b[c]
else:
    print "Nope"

Basically a dictionary built out of lists; the real thing jumps to back to main menu, works real nice actually.
But I was thinking just now, when the program checks for matches in list a, it compares the entire strings of wordq and the ones in the list. If one were to rewrite it a little, perhaps like this:
maybe add in another if-statement checking if the first letter of the word is present?
maybe add a loop checking letter for letter?

...would it be possible to gain a little extra effiency this way, though the program is longer?
After all, the lists in the real thing can be as long as any Britannica Encyclopedia you'd care to name.
I know about dictionaries and tuples and so on, this is more of an attempt to get a general grasp of the flow in a computer program!

•

Join Date: Oct 2004

Posts: 4,113

Reputation: vegaseat is just really nice

Solved Threads: 944

vegaseat

Offline

DaniWeb's Hypocrite

Re: Effiency in list searching

Oct 12th, 2008

You are assuming the word at index in list 'a' makes sense with the word with the same index in list 'b'. Somewhat dangerous. It would be simpler to make a dictionary with a:b (key:value) pairs, this way things that belong together stay together. Also, dictionary searches are highly optimized and very fast.

Last edited by vegaseat; Oct 12th, 2008 at 12:44 pm.

May 'the Google' be with you!

•

Join Date: Dec 2006

Posts: 1,062

Reputation: woooee is a jewel in the rough

Solved Threads: 299

woooee

Offline

Veteran Poster

Re: Effiency in list searching

Oct 12th, 2008

Definitely use a dictionary or SQL database if there are a lot of entries. It is hundreds or thousands of times faster depending. The time consuming part of the code is looping through the list twice. Using a try/except to check the list once with no "in" statement is a workaround, but just a workaround and not better than using a dictionary. As for checking letter by letter, that's what the existing or any compare/find/index has to do. There is no way to find something comparing an entire word to an entire word. The only shortcut that I know of would be to group words according to length. Thus, a five letter word would only look at other 5 letter words, and not words of other lengths.

 Help with Code Tags 
 Python Syntax (Toggle Plain Text) 
##if wordq in  a:     ## omit this line - duplicate list checking
try:
   c = a.index(wordq)
   print wordq
   print
   print b[c]
except:
   print wordq, "wasn't found in 'a'"
##if wordq in  a:     ## omit this line - duplicate list checking
try:
   c = a.index(wordq)
   print wordq
   print
   print b[c]
except:
   print wordq, "wasn't found in 'a'"

Edit: There is also sets if dictionaries are more than you want to do at this time. Both dictionaries and sets use a hash as an index, so the execution times should be similiar for both.

 Help with Code Tags 
 Python Syntax (Toggle Plain Text) 
list1 = ['a', 'b', 'c', 'd']
list2 = ['b']
set1=set(list1)
set2=set(list2)
set3= set1.intersection(set2)
print "set3 =", set3
 
set5=set(["z"])
set6=set1.intersection(set5)
print "set6 =", set6
list1 = ['a', 'b', 'c', 'd']
list2 = ['b']
set1=set(list1)
set2=set(list2)
set3= set1.intersection(set2)
print "set3 =", set3

set5=set(["z"])
set6=set1.intersection(set5)
print "set6 =", set6

Last edited by woooee; Oct 12th, 2008 at 2:34 pm.

•

Join Date: Oct 2008

Posts: 13

Reputation: Devlan is an unknown quantity at this point

Solved Threads: 0

Devlan

Offline

Newbie Poster

Re: Effiency in list searching

Oct 12th, 2008

Yea, I realise using lists for this purpose isn't exactly the optimal way of going about it, but it was part of a task a while back and it just got me thinking in those tracks... how does this work, how could you make this particular method work more efficently.

Thanks for the input woooee, I wasn't aware of that "intersect"-command. So much to learn...