Cache memory and its effect on list searching

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

On Sat, Dec 17, 2016 at 3:44 PM,  <sohcahtoa82 at> wrote:
>> python3
> 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.


More information about the Python-list mailing list