Issue 6: Comprehensions and Efficiency

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.")

Here were the results:

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.

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?

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.")

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.

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.

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.")   
    

Our final results were as follow:

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.)

Issue 5: Using Recursion on an Iterative Problem

Shoot for the moon. Even if you miss, you'll land among the stars.
- Les Brown  


As a part of our lab, we were given the exercise of making an recursive function for a standard iterative problem. Our goal was simple, produce the reversal of a string s, recursively. The challenge was the "recursively".

Anyone can do this problem with iteration; in fact, this is made even easier with python's ability to use more than just integers as the loop variable (a foreach loop really). 

def rev_string_iterative(s: str) -> str:
    """Return the reversal of string s, recursively.
    
    >>> rev_string_iterative("") == ""
    True
    >>> rev_string_iterative("H") == "H"
    True
    >>> rev_string_iterative("Hi") == "iH"
    True
    >>> rev_string_iterative("Hello!") == "!olleH"
    True
    """
    rev_string = ""
    for letter in s:
        rev_string = letter + rev_string
        
    return rev_string

However, should one attempt to solve this problem recursively, the very fact that there is an iteration solution that you're explicitly trying to avoid causes a great deal of conflict. This is because the recursive solution is awfully similar to the iterative solution. It is very easy to overlook a simple answer when you're trying to avoid anything similar to it.

We end up with something like this:

def rev_string_recursive(s: str) -> str:
    """Return the reversal of string s, recursively.
    
    >>> rev_string_recursive("") == ""
    True
    >>> rev_string_recursive("H") == "H"
    True
    >>> rev_string_recursive("Hi") == "iH"
    True
    >>> rev_string_recursive("Hello!") == "!olleH"
    True
    """
    if len(s) == 0:
        return s
    else:
        return s[-1] + rev_string_recursive(s[:-1]) 

In both cases, the goal was to take a single letter and append it to an accumulator. The only difference is, in the recursive example the function itself was the "loop". rev_string_recursive was called each time to with the whole string except the last letter, which was effectively identical the iterative task of moving the loop variable forward. In the iterative example, the loop was simply in a separate block of code.

If we trace the recursive function, we'll end up with something like this:
1. rev_string_recursive("") will return ""
2. rev_string_recursive("H") will return "H" + 1
3. rev_string_recursive("He") will return "e" + 2
4. rev_string_recursive("Hel") will return "l" + 3
and so on...

While this was just a practice, I didn't feel that it was necessarily a good practice. It feels as if we're reinventing the wheel - except we're doing it the hard way. There are a plethora of problems out there that require recursion to solve, many of which are contest worthy. It makes me wonder why we end up with exercises like this. Sure, those other problems may be hard, but even if we don't manage to solve all the problems we would still be able to gain a lot more practice from them.

Sorry, forgot to publish this!