item access time: sets v. lists

[Paul McGuire]

"David Isaac" <aisaac0 at verizon.net> wrote in message 
news:4cSUg.7864$753.4683 at trnddc05...
> Paul M. wrote:
>> Random access to item in list/set when item exists
>> set  -> 0.000241650824337
>> list -> 0.0245168031132
>>
>> Random access to item in list/set when item does not exist
>> set  -> 0.000187733357172
>> list -> 0.522086186932
>
>
> OK, that's a much better set of answers
> including to questions I did not
> even know I wanted to ask until
> I saw your post.  But, how to
> explain the above??
>
> Thanks,
> Alan Isaac
>
>

Searching for an item in a list is a linear search, and all 10000 items must 
be checked before determining that  a non-existent item is not in the list, 
and sure enough, our list takes about 20 times as long to find that 10500 is 
not in the range 10000 as it does to find 500 in the range 10000.  By 
contrast, a set (and also the keys in a dict) use a tree structure to index 
more quickly into the list of items, so this access (and determination of 
non-existence) will be much faster, especially so for a large list.

-- Paul