Cache memory and its effect on list searching

[Chris Angelico]

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