[Tutor] searching for a value in an array

[Gregor Lingl]

Danny Yoo schrieb:

>I think you'll like this one: it's basically what you just said:
>
>###
>  
>
>>>>print 'bob' in ['jane', 'hector', 'alissa', 'john', 'lisa', 'bob',
>>>>        
>>>>
>...                 'iris']
>1
>###
>
>The 'in' operator returns true if it can find our item in a list, and
>false otherwise.  What Python does here is a "linear" scan:  it'll march
>through our list until it either runs out of list, or if it finds 'bob'.
>
>
>There are faster ways of seeing if someone is present in a group of
>people: we can use a dictionary:
>
>###
>  
>
>>>>people = { 'jane' : 1, 'hector' : 1, 'alissa' : 1 }
>>>>'jane' in people
>>>>        
>>>>
>1
>  
>
>>>>'bob' in people
>>>>        
>>>>
>0
>###
>  
>
Faster ways?

 >>> txt = """The 'in' operator returns true if it can find our item in 
a list, and
false otherwise.  What Python does here is a "linear" scan:  it'll march
through our list until it either runs out of list, or if it finds 'bob'.


There are faster ways of seeing if someone is present in a group of
people: we can use a dictionary:

###

 >>> people = { 'jane' : 1, 'hector' : 1, 'alissa' : 1 }
 >>> 'jane' in people

1

 >>> 'bob' in people

0""".split()
 >>> txt
['The', "'in'", 'operator', 'returns', 'true', 'if', 'it', 'can', 
'find', 'our', 'item', 'in', 'a', 'list,', 'and', 'false', 'otherwise.', 
'What', 'Python', 'does', 'here', 'is', 'a', '"linear"', 'scan:', 
"it'll", 'march', 'through', 'our', 'list', 'until', 'it', 'either', 
'runs', 'out', 'of', 'list,', 'or', 'if', 'it', 'finds', "'bob'.", 
'There', 'are', 'faster', 'ways', 'of', 'seeing', 'if', 'someone', 'is', 
'present', 'in', 'a', 'group', 'of', 'people:', 'we', 'can', 'use', 'a', 
'dictionary:', '###', '>>>', 'people', '=', '{', "'jane'", ':', '1,', 
"'hector'", ':', '1,', "'alissa'", ':', '1', '}', '>>>', "'jane'", 'in', 
'people', '1', '>>>', "'bob'", 'in', 'people', '0']
 >>> txtdict={}
 >>> for item in txt: txtdict[item]=1

 >>> txtdict
{'and': 1, 'seeing': 1, 'What': 1, '"linear"': 1, 'false': 1, '0': 1, 
'people': 1, 'is': 1, 'There': 1, 'it': 1, 'list,': 1, 'through': 1, 
'are': 1, 'in': 1, 'operator': 1, 'our': 1, 'find': 1, 'if': 1, 
"'jane'": 1, '1,': 1, 'use': 1, 'group': 1, 'item': 1, 'ways': 1, 
"'hector'": 1, '1': 1, "'bob'.": 1, 'returns': 1, 'does': 1, 'out': 1, 
'=': 1, 'until': 1, '###': 1, 'can': 1, 'we': 1, 'someone': 1, 'march': 
1, "'bob'": 1, 'otherwise.': 1, "'in'": 1, 'here': 1, 'dictionary:': 1, 
'>>>': 1, 'The': 1, 'true': 1, 'present': 1, 'a': 1, 'runs': 1, ':': 1, 
'faster': 1, 'of': 1, 'list': 1, 'or': 1, 'Python': 1, 'either': 1, 
'scan:': 1, '{': 1, "'alissa'": 1, '}': 1, 'finds': 1, 'people:': 1, 
"it'll": 1}
 >>> import time
 >>> def checktime(value, collection, reps=100000):
    t = time.time()
    i = 0
    while i < reps:
        i+=1
        value in collection
    print time.time()-t

   
 >>> checktime("bob",txt)
2.98500001431
 >>> checktime("The",txt)
0.360999941826
 >>> checktime("Python",txt)
0.900999903679
 >>> checktime("'bob'",txt)
2.8939999342
 >>> checktime("0",txt)
3.08400011063
 >>> checktime("bob",txtdict)
0.320999979973
 >>> checktime("The",txtdict)
0.340000033379
 >>> checktime("Python",txtdict)
0.340999960899
 >>> checktime("0",txtdict)
0.330999970436
 >>> checktime("'bob'",txtdict)
0.330999970436
 >>>

Indeed!
Gregor