ordered sets operations on lists..

[Amit Khemka]

Hello, Is there a *direct* way of doing set operations on lists which
preserve the order of the input lists ?
For Ex. l1 = [1, 5, 3, 2, 4, 7]
l2 = [3, 5, 10]

and (l1 intersect l2) returns [5, 3] .... (and (l2 intersect l1)
returns [3, 5])

thanks in advance,
amit.

--
----
Amit Khemka -- onyomo.com
Endless the world's turn, endless the sun's Spinning, Endless the quest;
I turn again, back to my own beginning, And here, find rest.

[bonono@gmail.com]

Re: ordered sets operations on lists..


Amit Khemka wrote:[color=blue]
> Hello, Is there a *direct* way of doing set operations on lists which
> preserve the order of the input lists ?
> For Ex. l1 = [1, 5, 3, 2, 4, 7]
> l2 = [3, 5, 10]
>
> and (l1 intersect l2) returns [5, 3] .... (and (l2 intersect l1)
> returns [3, 5])
>[/color]
what do you mean by "direct" way ? ugly(some said) one liner ?

filter(set(l1). intersection(se t(l2)).__contai ns__, l1)
filter(set(l1). intersection(se t(l2)).__contai ns__, l2)

[Scott David Daniels]

Re: ordered sets operations on lists..

Amit Khemka wrote:[color=blue]
> Hello, Is there a *direct* way of doing set operations on lists which
> preserve the order of the input lists ?[/color]
Nope
[color=blue]
> For Ex. l1 = [1, 5, 3, 2, 4, 7]
> l2 = [3, 5, 10]
>
> and (l1 intersect l2) returns [5, 3] .... (and (l2 intersect l1)
> returns [3, 5])[/color]

However:
intersection = set(list1) & set(list2)
[element for element in list1 if element in intersection]
or
[element for element in list2 if element in intersection]
Give you the result you'd like.

--Scott David Daniels
scott.daniels@a cm.org

[Raymond Hettinger]

Re: ordered sets operations on lists..

[Amit Khemka][color=blue][color=green]
> > Hello, Is there a *direct* way of doing set operations on lists which
> > preserve the order of the input lists ?
> > For Ex. l1 = [1, 5, 3, 2, 4, 7]
> > l2 = [3, 5, 10]
> >
> > and (l1 intersect l2) returns [5, 3] .... (and (l2 intersect l1)[/color][/color]

[bonono][color=blue]
> what do you mean by "direct" way ? ugly(some said) one liner ?
>
> filter(set(l1). intersection(se t(l2)).__contai ns__, l1)
> filter(set(l1). intersection(se t(l2)).__contai ns__, l2)[/color]

The intersection step is unnecessary, so the answer can be simplified a
bit:
[color=blue][color=green][color=darkred]
>>> filter(set(l2). __contains__, l1)[/color][/color][/color]
[5, 3][color=blue][color=green][color=darkred]
>>> filter(set(l1). __contains__, l2)[/color][/color][/color]
[3, 5]

[bonono@gmail.com]

Re: ordered sets operations on lists..


Raymond Hettinger wrote:[color=blue]
> The intersection step is unnecessary, so the answer can be simplified a
> bit:
>[color=green][color=darkred]
> >>> filter(set(l2). __contains__, l1)[/color][/color]
> [5, 3][color=green][color=darkred]
> >>> filter(set(l1). __contains__, l2)[/color][/color]
> [3, 5][/color]

stand corrected.

[Alex Martelli]

Re: ordered sets operations on lists..

Raymond Hettinger <python@rcn.com > wrote:
...[color=blue]
> The intersection step is unnecessary, so the answer can be simplified a
> bit:
>[color=green][color=darkred]
> >>> filter(set(l2). __contains__, l1)[/color][/color]
> [5, 3][color=green][color=darkred]
> >>> filter(set(l1). __contains__, l2)[/color][/color]
> [3, 5][/color]

....and if one has time to waste, "setificati on" being only an
optimization, it can also be removed: filter(l2.__con tains__, l1) etc
(very slow for long lists, of course).

Personally, I'd always use (depending on guesses regarding lengths of
lists) [x for x in l1 if x in l2] or the setified equivalent, of course.


Alex

[Bengt Richter]

Re: ordered sets operations on lists..

On Sat, 11 Feb 2006 10:24:04 -0800, aleaxit@yahoo.c om (Alex Martelli) wrote:
[color=blue]
>Raymond Hettinger <python@rcn.com > wrote:
> ...[color=green]
>> The intersection step is unnecessary, so the answer can be simplified a
>> bit:
>>[color=darkred]
>> >>> filter(set(l2). __contains__, l1)[/color]
>> [5, 3][color=darkred]
>> >>> filter(set(l1). __contains__, l2)[/color]
>> [3, 5][/color]
>
>...and if one has time to waste, "setificati on" being only an
>optimization , it can also be removed: filter(l2.__con tains__, l1) etc
>(very slow for long lists, of course).
>
>Personally, I'd always use (depending on guesses regarding lengths of
>lists) [x for x in l1 if x in l2] or the setified equivalent, of course.
>[/color]
Perhaps newbies should be advised that

[x for x in l1 if x in set(l2)]

is not a (well) setified equivalent? I could see them being tempted.

Regards,
Bengt Richter

[Alex Martelli]

Re: ordered sets operations on lists..

Bengt Richter <bokr@oz.net> wrote:
...[color=blue][color=green]
> >Personally, I'd always use (depending on guesses regarding lengths of
> >lists) [x for x in l1 if x in l2] or the setified equivalent, of course.
> >[/color]
> Perhaps newbies should be advised that
>
> [x for x in l1 if x in set(l2)]
>
> is not a (well) setified equivalent? I could see them being tempted.[/color]

You mean, newbies should be advised that Python does NOT hoist any
computations whatsoever from the body of a loop (including LCs and
genexps), so if you want anything hoisted you need to hoist it yourself?
Yes, it is a point worth making, since the lack of hoisting is a
frequent cause of performance loss.


Alex

[Steve Holden]

Re: ordered sets operations on lists..

Alex Martelli wrote:[color=blue]
> Bengt Richter <bokr@oz.net> wrote:
> ...
>[color=green][color=darkred]
>>>Personally , I'd always use (depending on guesses regarding lengths of
>>>lists) [x for x in l1 if x in l2] or the setified equivalent, of course.
>>>[/color]
>>
>>Perhaps newbies should be advised that
>>
>> [x for x in l1 if x in set(l2)]
>>
>>is not a (well) setified equivalent? I could see them being tempted.[/color]
>
>
> You mean, newbies should be advised that Python does NOT hoist any
> computations whatsoever from the body of a loop (including LCs and
> genexps), so if you want anything hoisted you need to hoist it yourself?
> Yes, it is a point worth making, since the lack of hoisting is a
> frequent cause of performance loss.
>[/color]
Of course now 2.5 is planning to include the AST parser there's fruitful
ground for optimization studies that will perform hoisting automatically
(should anyone be looking for a project ;-)

Given that Python 2.4 doesn't even perform simple constant folding for
arithmetic expressions
[color=blue][color=green][color=darkred]
>>> dis.dis(compile ("print 1+2", '', 'exec'))[/color][/color][/color]
1 0 LOAD_CONST 0 (1)
3 LOAD_CONST 1 (2)
6 BINARY_ADD
7 PRINT_ITEM
8 PRINT_NEWLINE
9 LOAD_CONST 2 (None)
12 RETURN_VALUE

even hoisting could be seen as an "advanced" optimization.

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[Felipe Almeida Lessa]

Re: ordered sets operations on lists..

Em Dom, 2006-02-12 às 23:15 -0500, Steve Holden escreveu:[color=blue]
> Given that Python 2.4 doesn't even perform simple constant folding for
> arithmetic expressions
> [snip][/color]

May I ask why doesn't it perform such optimization? Is there any special
difficulties in doing so with the Python compiler?

Also, IIRC Psyco does optimize these constant expressions. Or am I
wrong?

Cheers,
Felipe.

--
"Quem excele em empregar a força militar subjulga os exércitos dos
outros povos sem travar batalha, toma cidades fortificadas dos outros
povos sem as atacar e destrói os estados dos outros povos sem lutas
prolongadas. Deve lutar sob o Céu com o propósito primordial da
'preservação' . Desse modo suas armas não se embotarão, e os ganhos
poderão ser preservados. Essa é a estratégia para planejar ofensivas."

-- Sun Tzu, em "A arte da guerra"

[Steve Holden]

Re: ordered sets operations on lists..

Felipe Almeida Lessa wrote:[color=blue]
> Em Dom, 2006-02-12 às 23:15 -0500, Steve Holden escreveu:
>[color=green]
>>Given that Python 2.4 doesn't even perform simple constant folding for
>>arithmetic expressions
>>[snip][/color]
>
>
> May I ask why doesn't it perform such optimization? Is there any special
> difficulties in doing so with the Python compiler?
>[/color]
As well to ask why the sky is blue, and has those little white things in
it (unless you live in Arizona) :-)

The basic answer is that so far no developer has felt it worthwhile to
expend time on adding these optimizations.
[color=blue]
> Also, IIRC Psyco does optimize these constant expressions. Or am I
> wrong?
>[/color]
Psyco does some very advanced things, but it does them all at run-time.
Unless I misunderstand (not unheard of), there are no circumstances
under which Psyco will improve run-time for a piece of code that is only
executed once.

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[Felipe Almeida Lessa]

Re: ordered sets operations on lists..

Em Dom, 2006-02-12 às 23:51 -0500, Steve Holden escreveu:[color=blue]
> The basic answer is that so far no developer has felt it worthwhile to
> expend time on adding these optimizations.[/color]

I always thought these small optimizations could lead Python to be
faster overall. I remember about this every time I see CPython vs.
IronPython benchmarks (.NET and Mono do some nice optimizations at
compile and run times).
[color=blue][color=green]
> > Also, IIRC Psyco does optimize these constant expressions. Or am I
> > wrong?
> >[/color]
> Psyco does some very advanced things, but it does them all at run-time.
> Unless I misunderstand (not unheard of), there are no circumstances
> under which Psyco will improve run-time for a piece of code that is only
> executed once.[/color]

Sorry, I think I should have been clearer. Yes, Psyco only helps at
runtime (when the function is called), but those constant folds only
practically help on parts of the code that are called many times anyway,
right?

--
"Quem excele em empregar a força militar subjulga os exércitos dos
outros povos sem travar batalha, toma cidades fortificadas dos outros
povos sem as atacar e destrói os estados dos outros povos sem lutas
prolongadas. Deve lutar sob o Céu com o propósito primordial da
'preservação' . Desse modo suas armas não se embotarão, e os ganhos
poderão ser preservados. Essa é a estratégia para planejar ofensivas."

-- Sun Tzu, em "A arte da guerra"

[Steve Holden]

Re: ordered sets operations on lists..

Felipe Almeida Lessa wrote:[color=blue]
> Em Dom, 2006-02-12 às 23:51 -0500, Steve Holden escreveu:
>[color=green]
>>The basic answer is that so far no developer has felt it worthwhile to
>>expend time on adding these optimizations.[/color]
>
>
> I always thought these small optimizations could lead Python to be
> faster overall. I remember about this every time I see CPython vs.
> IronPython benchmarks (.NET and Mono do some nice optimizations at
> compile and run times).
>[/color]
Indeed it is true that on some benchmarks IronPython is faster than
CPython. I suspect this was helped by the fact that IronPython is Jim's
third implementation of Python (I believe he was familiar with CPython
before he started on Jython, formerly known as JPython).

The fact remains that until someone writes the code it can't be included
in the implementation. Performance optimization, unfortunately, doesn't
have the same glamorous cachet as more esoteric language features.[color=blue]
>[color=green][color=darkred]
>>>Also, IIRC Psyco does optimize these constant expressions. Or am I
>>>wrong?
>>>[/color]
>>
>>Psyco does some very advanced things, but it does them all at run-time.
>>Unless I misunderstand (not unheard of), there are no circumstances
>>under which Psyco will improve run-time for a piece of code that is only
>>executed once.[/color]
>
>
> Sorry, I think I should have been clearer. Yes, Psyco only helps at
> runtime (when the function is called), but those constant folds only
> practically help on parts of the code that are called many times anyway,
> right?
>[/color]
Right. Technically constant folding is a win for a single execution, but
only if you don't take the slightly-increased compile time into account :-)

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/

[Kay Schluehr]

Re: ordered sets operations on lists..

Bengt Richter wrote:
[color=blue]
> Perhaps newbies should be advised that
>
> [x for x in l1 if x in set(l2)][/color]

But the resulting list is a representative of bag not a set ( contains
multiple occurrences of elements ):
[color=blue][color=green][color=darkred]
>>> [x for x in [3, 3] if s in Set([3])][/color][/color][/color]
[3,3]

Same with Raymonds solution:
[color=blue][color=green][color=darkred]
>>> filter(Set([3]).__contains__, [3,3])[/color][/color][/color]
[3, 3]

Kay