Cache memory and its effect on list searching
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...
> 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