item access time: sets v. lists

[Paul McGuire]

"Neil Cerutti" <horpner at yahoo.com> wrote in message 
news:slrnei8189.1hg.horpner at FIAD06.norwich.edu...
> On 2006-10-04, Paul McGuire <ptmcg at austin.rr._bogus_.com> wrote:
>> "Neil Cerutti" <horpner at yahoo.com> wrote in message
>> news:slrnei7sc2.fs.horpner at FIAD06.norwich.edu...
>>
>
> It seems to be timing "testing for membership", not "random
> access". Random access is just seq[n]; at least, that's the
> assumption I made.
>
> Perhaps I read the test description out of context and got
> confused.
>

Oh, poor wording on my part, sorry.

You got me wondering what seq[n] would give me in the case of a set:

>>> z = set(range(100))
>>> z[30]
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: unindexable object
>>>

It really doesn't make any sense since sets are unordered.  So we couldn't 
compare lists and sets in this manner anyway.

I *did* learn that dicts and sets use a hash table, not a tree, which also 
helps explain why the initial construction of the 10000-element set takes so 
much longer than just simple assembly of the range into a list.

-- Paul