1

The following 2 methods do the same thing. Which one is more efficient in terms of time/space complexity?

** Method A**
for student in group.students:
    for grade in student.grades:
        some_operation(grade)

** Method B**
for grade in [grade for student in group.students for grade in student.grades]
    some_operation(grade)
Peter Mortensen
  • 30,738
  • 21
  • 105
  • 131
cheng
  • 6,596
  • 6
  • 25
  • 27
  • 1
    B: consumes more memory because it builds an intermediate list. Use a generator expression instead: `for grade in (grade ...): some_operation(grade)`. – Bakuriu Sep 29 '16 at 20:57
  • @Bakuriu, "()" indicate generator? So the list of 'grades' won't be created as we loop thru it? – cheng Sep 29 '16 at 21:03
  • Related threads http://stackoverflow.com/questions/47789/generator-expressions-vs-list-comprehension http://stackoverflow.com/questions/19933753/generator-vs-list-comprehension – cheng Sep 29 '16 at 21:14

2 Answers2

1

Method B looks weird and redundant. You could shorten it to:

[some_operation(grade) for student in group.students for grade in student.grades]

But method A is better either way because it doesn't create a list. Making a list simply to throw it away is confusing to the reader and wastes memory.

Alex Hall
  • 34,833
  • 5
  • 57
  • 89
  • Agreed. Just don't like multiple levels of loops, because of my OCD. Any idea how to write concise yet equally efficient code in this case? – cheng Sep 29 '16 at 20:55
  • I strongly dislike this. list-comprehensions are expressions and should *not* be used to just calla function on a sequence of values. Besides: it consumes memory. If you have a scenario where you have millions of items on which to perform the action you probably don't want to create a useless list with million of elements. – Bakuriu Sep 29 '16 at 20:56
  • No, do not shorten method B to a single list comprehension. Method B does not create a new list; the list comprehension creates one that you immediately discard. – chepner Sep 29 '16 at 21:00
  • Agreed with Alex and @Bakuiu list comprehension is inefficient in space. – cheng Sep 29 '16 at 21:00
  • @cheng shorter code is not necessarily cleaner or clearer. Always choose to write code that is instantly obvious to a reader rather than trying hard to save lines. – Alex Hall Sep 29 '16 at 21:03
  • @Bakuriu yes but Method B already did that. I pointed out how to improve it but said it's still bad. – Alex Hall Sep 29 '16 at 21:04
  • @chepner both versions of method B create a list and discard it immediately. My version has no disadvantage unless it is assigned to a variable. – Alex Hall Sep 29 '16 at 21:07
  • A related question: nested loop vs generator expression, which one is more efficient? – cheng Sep 29 '16 at 21:15
  • @cheng if there is a difference, it is not significant. Do what is more appropriate semantically for the situation. – Alex Hall Sep 29 '16 at 21:26
  • @AlexHall I never said the original Method B was good, either. The list comprehension still has to *create* the list, whether or not you assign it to a variable. Never use a list comprehension just for the side effect of calling a function on each element of a list; just use a `for` loop as in Method A. – chepner Sep 29 '16 at 23:34
  • Yes, @chepner is right, do not shorten method B as it will create a new list. Instead, you can use a generator expression `for grade in (grade for student.....)` as they are **LAZY** and more efficient in this case(memory efficient). – Eyong Kevin Enowanyo Nov 19 '20 at 15:02
0

These have the same time complexity, O(nm), since it's a loop over another loop. So, the n is group.students, and m is students.grades. Functionally, these should be the same time complexity too since it's iterating over both lists either way.

Kevin London
  • 4,628
  • 1
  • 21
  • 29