Why searching in a set is much faster than in a list ?
Steve D'Aprano
steve+python at pearwood.info
Wed Sep 28 07:32:01 EDT 2016
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.
More information about the Python-list
mailing list