fast way to filter a set?

Fortepianissimo

unread,

Sep 17, 2003, 12:01:37 PM9/17/03

to

I know I can do things like

s=Set(range(1,11))
s=Set(filter(lambda x:x%2==0,s))

But this seems a bit slow since filter returns a list which then must
be converted back to a set. Any tips? Thanks!

Nicola Mingotti

unread,

Sep 17, 2003, 12:51:59 PM9/17/03

to

fortepi...@yahoo.com.tw (Fortepianissimo) writes:

Can you ?
I tried python2.3 and 2.2 and it replies
: "NameError: name 'Set' is not defined" .

There is a PEP but it seems it's steel 'under consideration'.
http://www.python.org/peps/pep-0218.html

May be , if this proposal is accepted you
one day could write :
{ x for x in S if x%2 == 0 } # S be a set .

bye.

Skip Montanaro

unread,

Sep 17, 2003, 12:24:07 PM9/17/03

to

fortepianissimo> I know I can do things like
fortepianissimo> s=Set(range(1,11))
fortepianissimo> s=Set(filter(lambda x:x%2==0,s))

fortepianissimo> But this seems a bit slow since filter returns a list
fortepianissimo> which then must be converted back to a set. Any tips?

The only thing which comes to mind is:

>>> s = sets.Set(range(1,11))
>>> s
Set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
>>> keys = list(s)
>>> dummy = [s.discard(x) for x in keys if x%2]
>>> s
Set([2, 4, 6, 8, 10])

You still create a list, but don't create a second set.

Skip

fortepianissimo

unread,

Sep 17, 2003, 12:41:48 PM9/17/03

to

But this created two lists (keys and dummy)? Compared to the filter()
method, which created a list and a new set, maybe your suggestion is
still a bit faster...

__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com

Peter Otten

unread,

Sep 17, 2003, 1:13:09 PM9/17/03

to

Nicola Mingotti wrote:

> fortepi...@yahoo.com.tw (Fortepianissimo) writes:
>
>> I know I can do things like
>>
>> s=Set(range(1,11))
>> s=Set(filter(lambda x:x%2==0,s))
>>
>> But this seems a bit slow since filter returns a list which then must
>> be converted back to a set. Any tips? Thanks!
>
> Can you ?
> I tried python2.3 and 2.2 and it replies
> : "NameError: name 'Set' is not defined" .

In 2.3 it works if you do

from sets import Set

first.

Peter

Peter Otten

unread,

Sep 17, 2003, 1:22:14 PM9/17/03

to

Fortepianissimo wrote:

The Set constructor accepts any iterable, so you can do it all with
iterators instead of temporary lists:

from sets import Set
from itertools import ifilter

s = Set(range(1, 11))
print Set(ifilter(lambda x: x % 2 == 0, s))

Peter

Stefan Franke

unread,

Sep 17, 2003, 1:25:25 PM9/17/03

to

Try:

from itertools import ifilter

s=Set(xrange(1,11))
s=Set(ifilter(lambda x:x%2==0,s))

Mike C. Fletcher

unread,

Sep 17, 2003, 1:03:58 PM9/17/03

to

fortepianissimo wrote:

>But this created two lists (keys and dummy)? Compared to the filter()
>method, which created a list and a new set, maybe your suggestion is
>still a bit faster...
>
>

Generators will probably be the easiest way to avoid the list-creation
overhead...

>>> from __future__ import generators
>>> def fget( s, function ):
... for item in s:
... if function(item):
... yield item
...
>>> r = Set.Set( range(20))
>>> Set.Set( fget(r, lambda x: x%2))
[19, 1, 3, 17, 5, 7, 9, 11, 13, 15]
>>>

HTH,
Mike

>--- Skip Montanaro <sk...@pobox.com> wrote:
>
>
>> fortepianissimo> I know I can do things like
>> fortepianissimo> s=Set(range(1,11))
>> fortepianissimo> s=Set(filter(lambda x:x%2==0,s))
>>
>> fortepianissimo> But this seems a bit slow since filter returns a
>>list
>> fortepianissimo> which then must be converted back to a set. Any
>>tips?
>>
>>

...
_______________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder
http://members.rogers.com/mcfletch/

Skip Montanaro

unread,

Sep 17, 2003, 1:41:37 PM9/17/03

to

fortepianissimo> But this created two lists (keys and dummy)? Compared
fortepianissimo> to the filter() method, which created a list and a new
fortepianissimo> set, maybe your suggestion is still a bit faster...

You asked for alternatives. I offered one. I'll let you do the performance
testing. ;-)

Skip

fortepianissimo> --- Skip Montanaro <sk...@pobox.com> wrote:
>>
fortepianissimo> I know I can do things like
fortepianissimo> s=Set(range(1,11))
fortepianissimo> s=Set(filter(lambda x:x%2==0,s))
>>
fortepianissimo> But this seems a bit slow since filter returns a
>> list
fortepianissimo> which then must be converted back to a set. Any
>> tips?
>>

>> The only thing which comes to mind is:
>>
>> >>> s = sets.Set(range(1,11))
>> >>> s
>> Set([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
>> >>> keys = list(s)
>> >>> dummy = [s.discard(x) for x in keys if x%2]
>> >>> s
>> Set([2, 4, 6, 8, 10])
>>
>> You still create a list, but don't create a second set.
>>
>> Skip

fortepianissimo> __________________________________
fortepianissimo> Do you Yahoo!?
fortepianissimo> Yahoo! SiteBuilder - Free, easy-to-use web site design software
fortepianissimo> http://sitebuilder.yahoo.com

fortepianissimo

unread,

Sep 17, 2003, 2:05:15 PM9/17/03

to

Actually I like your idea most (out of other iterator approach) - now
if we could do an in-place set filtering... (maybe have a different
version of set.discard() which takes a lambda expression?)

__________________________________
Do you Yahoo!?

Yahoo! SiteBuilder - Free, easy-to-use web site design software

http://sitebuilder.yahoo.com

John J. Lee

unread,

Sep 18, 2003, 9:06:32 AM9/18/03

to

fortepianissimo <fortepi...@yahoo.com.tw> writes:

> Actually I like your idea most (out of other iterator approach) - now
> if we could do an in-place set filtering... (maybe have a different

[...]

You can, with ifilter -- see Peter Otten's post. I guess you're
talking specifically about in-place filtering with comprehensions,
though?

Would have been a nice use for (sadly rejected) generator
comprehensions:

s2 = Set([yield x for x in s if x%2])

Not sure why Skip introduced that 'keys' list -- this works:

s2 = Set([x for x in s if x%2])

John