WPE - Week 02 - Solution

solution.py

import timeit
from typing import Dict, Generator, List

Range3 = Generator[int, None, None]


def myrange3(start: int, stop: int = None, step: int = 1) -> Range3:
    if stop is None:
        current, stop = 0, start
    else:
        current = start
    
    # range returns a ValueError if step = 0
    if step == 0:
        raise ValueError("myrange() step argument must not be 0")
    
    # We return nothing if step is such that nothing could be reached
    if (current < stop and step < 0) or (current > stop and step > 0):
        return

    while (step > 0 and current < stop) or (step < 0 and current > stop):
        yield current
        current += step

# = Solution from Reuven =
# def myrange3(first, second=None, step=1):
    # if second is None:
        # current = 0
        # end = first
    # else:
        # current = first
        # end = second

    # while current < end:
        # yield current
        # current += step


def myrange2(start: int, stop: int = None, step: int = 1) -> List[int]:
    return list(myrange3(start, stop, step))

def myrange2_list(start: int, stop: int = None, step: int = None) -> List[int]:
    if stop is None:
        start, stop = 0, start
    if step is None:
        step = 1

    list_range = list()  # type: List[int]
    while True:
        if start < stop:
            list_range.append(start)
            start += step
        else:
            break
    return list_range



def myrange2_rec(start: int, stop: int = None, step: int = None) -> List[int]:
    # NOTE: maximum recursion depth reached for 998 calls in my case
    if stop is None:
        start, stop = 0, start
    if step is None:
        step = 1

    if start < stop:
        return [start] + myrange2_rec(start + step, stop, step)
    else:
        return []


if __name__ == "__main__":
    for size_range, nb_times in [(100, int(1E5)), (1000, int(1E4)), (10000, 1000), (int(1E6), 10)]:

        timing = timeit.Timer(f"for _ in range({size_range}): pass").timeit(nb_times)
        print(f"Python3 range ({size_range}) * {nb_times} times: {timing:.4f}s")

        timing = dict()  # type: Dict[str, int]
        for fn in ["myrange3", "myrange2", "myrange2_list", "myrange2_rec"]:
            try:
                t = timeit.Timer(f"for _ in {fn}({size_range}): pass", f"from solution import {fn}")
                timing[fn] = t.timeit(nb_times)
                print(f"{fn:>15} ({size_range}) * {nb_times} times: {timing[fn]:.4f}s")
            except RecursionError:
                 print(f"{fn:>15} ({size_range}) * {nb_times} times: RECURSION ERROR")
        winner = min(timing, key=timing.get)
        print(f"==> WINNER = {winner} ({timing[winner]})")
        print("-" * 10)

Got the following timings:

Python3 range (100) * 100000 times: 0.1644s
       myrange3 (100) * 100000 times: 1.9795s
       myrange2 (100) * 100000 times: 1.4923s
  myrange2_list (100) * 100000 times: 1.8463s
   myrange2_rec (100) * 100000 times: 9.1241s
==> WINNER = myrange2 (1.4923410949413682)
----------
Python3 range (1000) * 10000 times: 0.2728s
       myrange3 (1000) * 10000 times: 1.3382s
       myrange2 (1000) * 10000 times: 1.3349s
  myrange2_list (1000) * 10000 times: 1.6462s
   myrange2_rec (1000) * 10000 times: RECURSION ERROR
==> WINNER = myrange2 (1.3349161829231448)
----------
Python3 range (10000) * 1000 times: 0.2199s
       myrange3 (10000) * 1000 times: 1.3992s
       myrange2 (10000) * 1000 times: 1.6076s
  myrange2_list (10000) * 1000 times: 1.7483s
   myrange2_rec (10000) * 1000 times: RECURSION ERROR
==> WINNER = myrange3 (1.3992412743590599)
----------
Python3 range (1000000) * 10 times: 0.2167s
       myrange3 (1000000) * 10 times: 1.3274s
       myrange2 (1000000) * 10 times: 3.0168s
  myrange2_list (1000000) * 10 times: 3.1425s
   myrange2_rec (1000000) * 10 times: RECURSION ERROR
==> WINNER = myrange3 (1.3274062991597546)
----------