Re: ordered sets operations on lists..
Bengt Richter wrote: > Perhaps newbies should be advised that > > [x for x in l1 if x in set(l2)] But the resulting list is a representative of bag not a set ( contains multiple occurrences of elements ): >>> [x for x in [3, 3] if s in Set([3])] [3,3] Same with Raymonds solution: >>> filter(Set([3]).__contains__, [3,3]) [3, 3] Kay -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
On 2/12/06, Felipe Almeida Lessa <[EMAIL PROTECTED]> wrote: > Em Dom, 2006-02-12 às 23:15 -0500, Steve Holden escreveu: > > Given that Python 2.4 doesn't even perform simple constant folding for > > arithmetic expressions > > [snip] > > May I ask why doesn't it perform such optimization? Is there any special > difficulties in doing so with the Python compiler? It does in 2.5 thanks to Raymond Hettinger: >>> import dis [18110 refs] >>> def simple(): print 1+2 ... [18136 refs] >>> dis.dis(simple) 1 0 LOAD_CONST 3 (3) 3 PRINT_ITEM 4 PRINT_NEWLINE 5 LOAD_CONST 0 (None) 8 RETURN_VALUE [18635 refs] >>> Simple, low-hanging fruit like this are covered by the peephole optimizer already. Anything more complex, though, is difficult thanks to things being so dynamic and thus not easy to guarantee to be correct between compile-time and run-time. -Brett -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Felipe Almeida Lessa wrote: > Em Dom, 2006-02-12 às 23:51 -0500, Steve Holden escreveu: > >>The basic answer is that so far no developer has felt it worthwhile to >>expend time on adding these optimizations. > > > 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). > 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. > >>>Also, IIRC Psyco does optimize these constant expressions. Or am I >>>wrong? >>> >> >>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. > > > 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? > 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/ -- http://mail.python.org/mailman/listinfo/python-list
RE: ordered sets operations on lists..
Delaney, Timothy (Tim) wrote: > Adding such optimisations to Python may improve it's benchmark scores, Blegh! Time to give myself a good kicking! Tim Delaney -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Em Dom, 2006-02-12 às 23:51 -0500, Steve Holden escreveu: > The basic answer is that so far no developer has felt it worthwhile to > expend time on adding these optimizations. 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). > > Also, IIRC Psyco does optimize these constant expressions. Or am I > > wrong? > > > 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. 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" -- http://mail.python.org/mailman/listinfo/python-list
RE: ordered sets operations on lists..
Steve Holden wrote: > The basic answer is that so far no developer has felt it worthwhile to > expend time on adding these optimizations. Mainly because it's rare to find such constructs in anything except contrived examples ... Nearly every time you use a literal, it's being added to (subtracted from, etc) a non-literal. Adding such optimisations to Python may improve it's benchmark scores, but that's about it. The real gains are to be found in reducing function call overhead, attribute access, etc - and as a result there has been considerable effort expended in those areas. FWIW, there are some of us who do occasionally do bytecode optimisations, but we know it's just a bit of fun. I've yet to do any bytecode manipulation that's significantly improved performance. You're best of leaving such things to Pysco, and concentrating on algorithmic improvements. Tim Delaney -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Felipe Almeida Lessa wrote: > Em Dom, 2006-02-12 às 23:15 -0500, Steve Holden escreveu: > >>Given that Python 2.4 doesn't even perform simple constant folding for >>arithmetic expressions >>[snip] > > > May I ask why doesn't it perform such optimization? Is there any special > difficulties in doing so with the Python compiler? > 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. > Also, IIRC Psyco does optimize these constant expressions. Or am I > wrong? > 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/ -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Em Dom, 2006-02-12 às 23:15 -0500, Steve Holden escreveu: > Given that Python 2.4 doesn't even perform simple constant folding for > arithmetic expressions > [snip] 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" -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Alex Martelli wrote:
> Bengt Richter <[EMAIL PROTECTED]> wrote:
>...
>
>>>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.
>>>
>>
>>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.
>
>
> 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.
>
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
>>> dis.dis(compile("print 1+2", '', 'exec'))
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/
--
http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Bengt Richter <[EMAIL PROTECTED]> wrote: ... > >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. > > > 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. 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
On Sat, 11 Feb 2006 10:24:04 -0800, [EMAIL PROTECTED] (Alex Martelli) wrote: >Raymond Hettinger <[EMAIL PROTECTED]> wrote: > ... >> The intersection step is unnecessary, so the answer can be simplified a >> bit: >> >> >>> filter(set(l2).__contains__, l1) >> [5, 3] >> >>> filter(set(l1).__contains__, l2) >> [3, 5] > >...and if one has time to waste, "setification" being only an >optimization, it can also be removed: filter(l2.__contains__, 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. > 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Raymond Hettinger <[EMAIL PROTECTED]> wrote: ... > The intersection step is unnecessary, so the answer can be simplified a > bit: > > >>> filter(set(l2).__contains__, l1) > [5, 3] > >>> filter(set(l1).__contains__, l2) > [3, 5] ...and if one has time to waste, "setification" being only an optimization, it can also be removed: filter(l2.__contains__, 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 -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Raymond Hettinger wrote: > The intersection step is unnecessary, so the answer can be simplified a > bit: > > >>> filter(set(l2).__contains__, l1) > [5, 3] > >>> filter(set(l1).__contains__, l2) > [3, 5] stand corrected. -- http://mail.python.org/mailman/listinfo/python-list
Re: 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) [bonono] > what do you mean by "direct" way ? ugly(some said) one liner ? > > filter(set(l1).intersection(set(l2)).__contains__, l1) > filter(set(l1).intersection(set(l2)).__contains__, l2) The intersection step is unnecessary, so the answer can be simplified a bit: >>> filter(set(l2).__contains__, l1) [5, 3] >>> filter(set(l1).__contains__, l2) [3, 5] -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Amit Khemka wrote: > Hello, Is there a *direct* way of doing set operations on lists which > preserve the order of the input lists ? Nope > 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]) 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 [EMAIL PROTECTED] -- http://mail.python.org/mailman/listinfo/python-list
Re: ordered sets operations on lists..
Amit Khemka wrote: > 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]) > what do you mean by "direct" way ? ugly(some said) one liner ? filter(set(l1).intersection(set(l2)).__contains__, l1) filter(set(l1).intersection(set(l2)).__contains__, l2) -- http://mail.python.org/mailman/listinfo/python-list
ordered sets operations on lists..
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. -- http://mail.python.org/mailman/listinfo/python-list
