Real knowledge is to know the extent of one's ignorance.
- Confucius
We were informally introduced to the concept of generator comprehension as a part of our lab exercise. However, the format of our introduction led us to believe that generator comprehension is in some ways faster than list comprehension. How true is this exactly? I did a brief investigation.
import time
def list_via_comprehension(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n using list comprehension."""
start = time.time()
l = [i for i in range(n)]
end = time.time()
return end - start
def list_via_loop(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n using a loop."""
start = time.time()
l = []
for i in range(n):
l.append(i)
end = time.time()
return end - start
def generator_to_list(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n by converting a generator into a list."""
start = time.time()
l = (i for i in range(n))
list(l)
end = time.time()
return end - start
def list_via_generator(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n by extracting each item from a generator using the
next() method."""
start = time.time()
l = (i for i in range(n))
try:
while True:
next(l)
except Exception:
end = time.time()
return end - start
if __name__ == "__main__":
n = 10000000
print("It takes {} seconds to create a list of {}".format(
list_via_comprehension(n), n), "consecutive integers via comprehension.")
print("It takes {} seconds to create a list of {}".format(
list_via_loop(n), n), "consecutive integers via for loop.")
print("It takes {} seconds to create a list of {}".format(
generator_to_list(n), n), "consecutive integers by converting",
"a generator into a list.")
print("It takes {} seconds to create a list of {}".format(
list_via_generator(n), n), "consecutive integers by using the next",
"method.")
According to this, it seems that using a generator is less efficient. What if we gave every item a more demanding calculation to perform, such as i ** 2?It takes 0.9541211128234863 seconds to create a list of 10000000 consecutive integers via comprehension.
It takes 1.6146352291107178 seconds to create a list of 10000000 consecutive integers via for loop.
It takes 1.520693063735962 seconds to create a list of 10000000 consecutive integers by converting a generator into a list.
It takes 1.9292449951171875 seconds to create a list of 10000000 consecutive integers by using the next method.
import time
def list_via_comprehension(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n using list comprehension."""
start = time.time()
l = [i ** 2 for i in range(n)]
end = time.time()
return end - start
def list_via_loop(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n using a loop."""
start = time.time()
l = []
for i in range(n):
l.append(i ** 2)
end = time.time()
return end - start
def generator_to_list(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n by converting a generator into a list."""
start = time.time()
l = (i ** 2 for i in range(n))
list(l)
end = time.time()
return end - start
def list_via_generator(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n by extracting each item from a generator using the
next() method."""
start = time.time()
l = (i ** 2 for i in range(n))
try:
while True:
next(l)
except Exception:
end = time.time()
return end - start
if __name__ == "__main__":
n = 10000000
print("It takes {} seconds to create a list of {}".format(
list_via_comprehension(n), n), "consecutive integers via comprehension.")
print("It takes {} seconds to create a list of {}".format(
list_via_loop(n), n), "consecutive integers via for loop.")
print("It takes {} seconds to create a list of {}".format(
generator_to_list(n), n), "consecutive integers by converting",
"a generator into a list.")
print("It takes {} seconds to create a list of {}".format(
list_via_generator(n), n), "consecutive integers by using the next",
"method.")
At this point, it becomes clear that generators are less efficient when it comes to creating a list of items. However, what if we want to know whether a particular item in a list exists.
It takes 6.058269023895264 seconds to create a list of 10000000 consecutive integers via comprehension.
It takes 6.724354028701782 seconds to create a list of 10000000 consecutive integers via for loop.
It takes 6.631842136383057 seconds to create a list of 10000000 consecutive integers by converting a generator into a list.
It takes 7.01439094543457 seconds to create a list of 10000000 consecutive integers by using the next method.
import time
def list_via_comprehension(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n using list comprehension."""
start = time.time()
if any([i for i in range(n)]):
end = time.time()
return end - start
else:
return False
def list_via_loop(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n using a loop."""
start = time.time()
l = []
for i in range(n):
if i:
end = time.time()
return end - start
return False
def generator_to_list(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n by converting a generator into a list."""
start = time.time()
l = (i for i in range(n))
if any (list(l)):
end = time.time()
return end - start
else:
return False
def list_via_generator(n: int) -> float:
"""Return the time it took to create a list of consecutive integers
from 0 to n by extracting each item from a generator using the
next() method."""
start = time.time()
l = (i for i in range(n))
if any(l):
end = time.time()
return end - start
else:
return False
if __name__ == "__main__":
n = 10000000
print("It takes {} seconds to find whether a list of {}".format(
list_via_comprehension(n), n), "integers had a True value using",
"list comprehension.")
print("It takes {} seconds to find whether a list of {}".format(
list_via_loop(n), n), "integers had a True value using for loop.")
print("It takes {} seconds to find whether a list of {}".format(
generator_to_list(n), n), "integers had a True value by converting",
"a generator into a list.")
print("It takes {} seconds to find whether a list of {}".format(
list_via_generator(n), n), "integers had a True value by using the",
"next method.")
It takes 1.2131540775299072 seconds to find whether a list of 10000000 integers had a True value using list comprehension.
It takes 0.0 seconds to find whether a list of 10000000 integers had a True value using for loop.
It takes 1.554197072982788 seconds to find whether a list of 10000000 integers had a True value by converting a generator into a list.
It takes 0.0 seconds to find whether a list of 10000000 integers had a True value by using the next method.
Since the second value in the list is a True value, both loops and generator seems to be equally fast. For our final investigation, we shall refer back to the any_pythagorean_triples(start, finish) example in our lab.
import time
def any_pythagorean_triples_generator(start: int, finish: int) -> bool:
"""Return whether there is at least one pythagorean triple formed
of integers from start to finish
start, finish --- positive integers
>>> any_pythagorean_triples(1, 4)
False
>>> any_pythagorean_triples(1, 5)
True
"""
start_time = time.time()
# are there any...
if any(
# pythagorean triples in the *generator* --- notice the (...) not [...]
# look up generator comprehensions, and experiment with changing
# it back to [...] and calling any_pythagorean_triples(500, 1000)
((i**2 + j**2) == k**2
for i in range(start, finish + 1)
for j in range(start, finish + 1)
for k in range(start, finish + 1))):
end_time = time.time()
return end_time - start_time
else:
return False
def any_pythagorean_triples_loop(start: int, finish: int) -> bool:
"""Return whether there is at least one pythagorean triple formed
of integers from start to finish
start, finish --- positive integers
>>> any_pythagorean_triples(1, 4)
False
>>> any_pythagorean_triples(1, 5)
True
"""
start_time = time.time()
for i in range(start, finish + 1):
for j in range(start, finish + 1):
for k in range(start, finish + 1):
if (i**2 + j**2) == k**2:
end_time = time.time()
return end_time - start_time
return False
if __name__ == "__main__":
start = 500
finish = 1000
print("It takes {} seconds to find whether there is at least one".format(
any_pythagorean_triples_generator(start, finish)),
"pythagorean triple formed from integers {} to {}".format(
start, finish), "using a generator.")
print("It takes {} seconds to find whether there is at least one".format(
any_pythagorean_triples_loop(start, finish)),
"pythagorean triple formed from integers {} to {}".format(
start, finish), "using a loop.")
It takes 0.021003007888793945 seconds to find whether there is at least one pythagorean triple formed from integers 500 to 1000 using a generator.
It takes 0.02050304412841797 seconds to find whether there is at least one pythagorean triple formed from integers 500 to 1000 using a loop.
Conclusion
- List Comprehensions are always the fastest at creating a complete list of items, and performing any amount of calculations on all the items. This is because python has optimized this procedure.
- Converting a Generator Comprehension into a list is only slightly faster than creating a list using a for loop.
- Generator Comprehensions should not be used to create lists via iteration using next().
- Generator Comprehensions are significantly faster than List Comprehension at finding whether a particular value exists in the list (i.e. True).
- However, a loop is slightly faster than a Generator Comprehension at finding whether a particular value exists.
- Generator Comprehension's main purpose is for saving memory. (i.e. Generators are for Performance, not Efficiency.)
No comments:
Post a Comment