Simple Problem but tough for me if i want it in linear time

[Steven D'Aprano]

On Wed, 18 Aug 2010 16:03:58 +0200, Frederic Rentsch wrote:

> On Mon, 2010-08-16 at 23:17 +0000, Steven D'Aprano wrote:
>> On Mon, 16 Aug 2010 20:40:52 +0200, Frederic Rentsch wrote:
>> 
>> > How about
>> > 
>> >>>> [obj for obj in dataList if obj.number == 100]
>> > 
>> > That should create a list of all objects whose .number is 100. No
>> > need to cycle through a loop.
>> 
>> What do you think the list comprehension does, if not cycle through a
>> loop?
>> 
>> 
>> --
>> Steven
> 
> What I think is that list comprehensions cycle through a loop a lot
> faster than a coded loop (for n in ...:). 

I think measurement beats intuition:


[steve at wow-wow ~]$ python -m timeit '[str(i) for i in xrange(100000)]'
10 loops, best of 3: 84 msec per loop

[steve at wow-wow ~]$ python -m timeit 'L=[]
> for i in xrange(100000):
>     L.append(str(i))
> '
10 loops, best of 3: 105 msec per loop


But wait... we're not comparing apples with apples. There's an extra name 
lookup in the for-loop that the list comp doesn't have. We can fix that:


[steve at wow-wow ~]$ python -m timeit 'L=[]; append = L.append
for i in xrange(100000):
    append(str(i))
'
10 loops, best of 3: 86.7 msec per loop


The difference between 84 and 86 msec is essentially measurement error. 
Hell, the difference between 84 and 104 msec is not terribly significant 
either.



> As at the time of my post only
> coded loops had been proposed and the OP was concerned about speed, I
> thought I'd propose a list comprehension.

Yes, but the OP was concerned with asymptotic speed (big-oh notation), 
and both a for-loop and a list-comp are both O(N).

Frankly, I think the OP doesn't really know what he wants, other than 
premature optimization. It's amazing how popular that is :)



-- 
Steven