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

Steven D'Aprano steve-REMOVE-THIS at cybersource.com.au
Thu Aug 19 04:47:28 CEST 2010

```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:
>>
>> >
>> >>>> [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

```