Cache memory and its effect on list searching

Chris Angelico rosuav at gmail.com
Fri Dec 16 23:55:01 EST 2016


On Sat, Dec 17, 2016 at 3:44 PM,  <sohcahtoa82 at gmail.com> wrote:
>> python3 listsearch.py
> Python version:  sys.version_info(major=3, minor=5, micro=2, releaselevel='final', serial=0)
> building hashes...
> sorting...
> creating set...
> Unsorted list: 1.7384763684627569
> Sorted: 9.248799958145042
> set: 1.4614161294446149e-06
> binary search: 0.00010902164328108199
> binary search with bisect: 1.7829276782066472e-05
>
> Yup.  set is definitely the way to go!

More than that: the lists are searched in linear time, the binary
seach runs in logarithmic time, but the set lookup is constant time.
Doesn't matter how big your set is, you can test for membership with
one hash lookup.

ChrisA


More information about the Python-list mailing list