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

[Marko Rauhamaa]

Chris Angelico <rosuav at gmail.com>:

> On Wed, Sep 28, 2016 at 6:46 PM, Marko Rauhamaa <marko at pacujo.net> wrote:
>> 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.

With sets, you can only check for membership.

Lists are mappings that map indices to objects.

> "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,
> but membership inclusion checks are definitely up there among primary
> purposes of sets.)

Yes. However, membership is a feature of lists as well.


Marko