Why searching in a set is much faster than in a list ?

[Steve D'Aprano]

On Wed, 28 Sep 2016 07:07 pm, Chris Angelico wrote:

> On Wed, Sep 28, 2016 at 6:46 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
>> Lawrence D’Oliveiro <lawrencedo99 at gmail.com>:
>>
>>> On Wednesday, September 28, 2016 at 6:51:17 PM UTC+13, ast wrote:
>>>> I noticed that searching in a set is faster than searching in a list.
>>>
>>> That’s why we have sets.
>>
>> I would have thought the point of sets is to have set semantics, just
>> like the point of lists is to have list semantics.
> 
> And set semantics are what, exactly? Membership is a primary one.

Yep, that's pretty much it...

> "Searching in a set" in the OP's language is a demonstration of the
> 'in' operator, a membership/containment check.
> 
> (Other equally important set semantics include intersection and union,

Both of those revolve on membership testing.

The union of A and B is the set of all elements in A plus those in B; the
intersection of A and B is the set of all elements in both A and B.


> but membership inclusion checks are definitely up there among primary
> purposes of sets.)

I can't think of a set operation (apart from add and remove) which doesn't
resolve around membership.




-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.