<jupyter_start><jupyter_text>The Joy of Fast Cars, Homework AssignmentIn this weeks (optional) homework, your task it to try and write a bit of code that is *faster* than my code. And there is going to be two basic ways to do it; you can get you hands dirty and try some low-level optimisation or you can ditch all that and favour a high-level approach.Unlike most of the homeworks, this more about being clever than it is about understanding Python.    The Challenge: BEAT MY TIME!!    The below code will create a list of all *ODD* square numbers starting at 1 and ending at x. Example:    If x is 100, the squares are:    [1, 4, 9, 16, 25, 36, 49, 64, 81, 100]        Of which, we only want the odd numbers:    [1, 9, 25, 49, 81]A few hints...* Remember that "a and b" can be slower than "b and a" (see logic lecture). Basically, **the order** in which you do things can make a difference.* Finding a needle in a haystack is probably slower than [BLANK] ? Please study the code below. Your jump is to either make it faster by tinkering with it. Or alternatively you may wish to use your own algorithm. Possible Solutions:<jupyter_code>import sys
sys.path.append("..\misc") # Adding to sys.path allows us to find "profile_code.py" 
from profile_code import profile

import math 

##################################
# BASE SOLUTION, GOTTA BEAT THIS!
def hamster_squares(x):
    lst = []                    
    for number in range(1, x+1):    
        square = math.sqrt(number)    
        if square.is_integer():
            if number % 2 != 0: 
                lst.append(number) 
    return lst

# Possible Solution #1, (low-level):
def my_squares(x):
    lst = []
    for number in range(1, x+1, 2): 
        # by using a step of 2, we don't even need to test for odd/even.
        square = math.sqrt(number)
        if square.is_integer():
            lst.append(number)
    return lst
    
# Possible Solution #2, (low-level):
def my_squares2(x):
    # Uses the logic described in #1, but uses a list comprehension and is therefore faster.
    return [i for i in range(1, x+1, 2) if math.sqrt(i).is_integer()]

# Possible Solution #3, (high-level)
def my_squares3(x):
    # Here we generate the list rather than search the haystack
    # sqrt(n) is the same as i*i = n. 
    # also note that i*i is odd if i is odd.
    # Combining these things means finding all odd squares <= x is the same as finding all odd i*i where i*i <= x
    lst = []
    for i in range(1, math.ceil(math.sqrt(x)), 2):
        lst.append(i*i)
    return lst

# Possible Solution #4, (High-level, with low-level tweaking)
def my_squares4(x):
    return [i*i for i in range(1, math.floor(math.sqrt(x)+1), 2)]


################## THE CONTROL PANEL ################################
#####################################################################
verbose = False # set to False if you dont want the time on line-by-line basis.
X = 50_000_000 
# Lower X if tests are taking too long on your machine. 
# Raise X if you want higher accuracy.
#####################################################################

# CORRECTNESS TEST...
k = 10000
correct = hamster_squares(k) == my_squares(k) == my_squares2(k) == my_squares3(k) == my_squares4(k)

# SPEED TESTS ... (just ignore this code)
if correct:
    print("CORRECTNESS TEST = PASSED")
    print("...Now testing speed. Please, note, this may take a while...\n", 
          "Also, I'd advise a margin or error of about +- 0.2 seconds\n")
    
    def string(i, func, detail): 
        i = i.split("\n")      
        s= "✿ Stats for {} function.\n{}".format(func, i[2])
        if detail:
            s = s + "\n" + "\n".join(i[3:-7]) + "\n"
        return s
        
    hs = profile(hamster_squares, X)
    print("-------- Solution Comparision, where input size is {}. -------- \n".format(X))
    print(string(hs, "Teacher's Squares", verbose))
    
    ss = profile(my_squares, X)
    print(string(ss, "Solution #1: 'Tinkering with Range'", verbose))
    
    ss2 = profile(my_squares2, X)
    print(string(ss2, "Solution #2: 'List comprehension of the above'", verbose))
    
    ss3 = profile(my_squares3, X)
    print(string(ss3, "Solution #3: 'Building, not searching'", verbose))
    
    ss4 = profile(my_squares4, X)
    print(string(ss4, "Solution #4: 'List Comprehension of the above'", verbose))<jupyter_output>CORRECTNESS TEST = PASSED
...Now testing speed. Please, note, this may take a while...
 Also, I'd advise a margin or error of about +- 0.2 seconds

-------- Solution Comparision, where input size is 50000000. -------- 

✿ Stats for Teacher's Squares function.
         100003541 function calls in 23.496 seconds
✿ Stats for Solution #1: 'Tinkering with Range' function.
         50003541 function calls in 11.734 seconds
✿ Stats for Solution #2: 'List comprehension of #1' function.
         50000006 function calls in 11.476 seconds
✿ Stats for Solution #3: 'Building, not searching' function.
         3543 function calls in 0.001 seconds
✿ Stats for Solution #4: 'List Comprehension of #3' function.
         8 function calls in 0.000 seconds
{'fraction_non_alphanumeric': 0.1493239271017049, 'fraction_numerical': 0.030766215951401138, 'mean_word_length': 3.0220646178092987, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '440848', 'license': 'MIT', 'n_tokens_mistral': 1717, 'n_tokens_neox': 1529, 'n_words': 650, 'path': 'A Beginners Guide to Python/Homework Solutions/21. The Joy of Fast Cars (HW).ipynb', 'repo_name': 'fluffy-hamster/A-Beginners-Guide-to-Python', 'size': '5103'}