1

There is a belief that a list comprehension is syntactic sugar for passing a generator expression to list (1, 2). While I can't pinpoint the internal dynamics to prove this isn't the case, I've been able to show that there is an O(n) difference between these two methods:

n = 100000

%timeit [i for i in range(n)]          # 6.03 ms per loop
%timeit list(i for i in range(n))      # 10 ms per loop

%timeit [i for i in range(n*10)]       # 117 ms per loop
%timeit list(i for i in range(n*10))   # 157 ms per loop

%timeit [i for i in range(n*100)]      # 1.18 s per loop
%timeit list(i for i in range(n*100))  # 1.66 s per loop

O(n) calculation:

Scaling = 1, differential = 4ms
Scaling = 10, differential = 40ms
Scaling = 100, differential = 480ms

I have looked at the output of dis.dis. This shows a different order of processing in the latter, but it's not clear to me what these function calls reference:

import dis

dis.dis('[i for i in range(n)]')

  1           0 LOAD_CONST               0 (<code object <listcomp> at 0x0000000004E82300, file "<dis>", line 1>)
              2 LOAD_CONST               1 ('<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_NAME                0 (range)
              8 LOAD_NAME                1 (n)
             10 CALL_FUNCTION            1
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 RETURN_VALUE

dis.dis('list(i for i in range(n))')

  1           0 LOAD_NAME                0 (list)
              2 LOAD_CONST               0 (<code object <genexpr> at 0x0000000004EF94B0, file "<dis>", line 1>)
              4 LOAD_CONST               1 ('<genexpr>')
              6 MAKE_FUNCTION            0
              8 LOAD_NAME                1 (range)
             10 LOAD_NAME                2 (n)
             12 CALL_FUNCTION            1
             14 GET_ITER
             16 CALL_FUNCTION            1
             18 CALL_FUNCTION            1
             20 RETURN_VALUE

Can someone clarify precisely what's happening here?

jpp
  • 159,742
  • 34
  • 281
  • 339
  • "a list comprehension is syntactic sugar for passing a generator expression to list" It is not. But list comprehensions are not implemented using generators. A function is made, you can introspect the code object, and it is essentially a loop with append. – juanpa.arrivillaga Aug 28 '18 at 08:43
  • @juanpa.arrivillaga, Thanks. For some reason, I couldn't find the dup, which explains this in more detail. – jpp Aug 28 '18 at 08:44
  • 1
    "I've been able to show that there is an O(n) difference between these two methods" I'm not sure what you mean here. My own timings show, as expected, that both scale linearly, with the list comprehension winning by a constant factor. – juanpa.arrivillaga Aug 28 '18 at 08:44
  • @juanpa.arrivillaga, Can you share your timings? I see *precisely* 4ms vs 40ms differential scaling `n` by 10, as per code in my question. This is O(n). – jpp Aug 28 '18 at 08:45
  • 1
    I'm not sure what you mean by "O(N) difference between the two", I'm getting `53 / 4 = 13.25` for the list comprehension and `72 / 5.8 = 12.41379` for the generator expression. Both scaled linearly, and the difference between them seems to be a constant factor. – juanpa.arrivillaga Aug 28 '18 at 08:47
  • Please be more specific. What *timings* do you see? As per my question, I see 6 -> 10, 117 -> 157. And (157-117) / (10-6) = 10, which is the *n* scaling factor. – jpp Aug 28 '18 at 08:48
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/178914/discussion-between-juanpa-arrivillaga-and-jpp). – juanpa.arrivillaga Aug 28 '18 at 08:48

0 Answers0