Hi,
I want to repeatedly search a list to test whether that list contains a given
element X.
Of course, I can use membership testing using "in" (list._contains__).
But how is this method implemented? It seems to just walk through the whole
list from
beginning to end (see timeit code below). Is it faster to do a binary search on
a sorted list,
given that this task has to be done repeatedly? Can such a program be scaled to
lists
that do not fit into memory (maybe using shelve?)?
This is the function I made:
import bisect
def binarySearch(haystack, needle):
return haystack[bisect.bisect_right(haystack, needle) - 1] == needle
# needle is at the beginning of the sequence
>>> t = timeit.Timer("""import bisect
def binarySearch(haystack, needle):
return haystack[bisect.bisect_right(haystack, needle) - 1] == needle
binarySearch(range(10**7), 0)""")
>>> t.timeit(100)
16.737915573068676
>>> t2 = timeit.Timer("0 in range(10**7)")
>>> t2.timeit(100)
16.304621956142682
>>>
# needle is at the end of the sequence
>>> t = timeit.Timer("""import bisect
def binarySearch(haystack, needle):
return haystack[bisect.bisect_right(haystack, needle) - 1] == needle
binarySearch(range(10**7), 10**7-1)""")
>>> t.timeit(100)
16.954997632380582
>>> t2 = timeit.Timer("10**7-1 in range(10**7)")
>>> t2.timeit(100)
36.3686376341127
Thank you in advance!
Regards,
Albert-Jan
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
All right, but apart from the sanitation, the medicine, education, wine, public
order, irrigation, roads, a
fresh water system, and public health, what have the Romans ever done for us?
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
