We continued discussing complexity. Then we discussed higher-order functions and mentioned lambda expressions.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Given two functions $f(n)$ and $g(n)$,
$f(n) = O(g(n))$
If and only if there exist $c > 0 $ and $n_{0}\in \mathbb{R}$ such that
$\forall n>n_0$
$|f(n)| \leq c\cdot|g(n)|$
Let $n$ denote the input size. Let $f_1(n) = O(g_1(n))\;$ and $f_2(n)=O(g_2(n))$.
for i in range(f1(n))):
O(1)
for j in range(f_2(n)):
O(1)
We showed that $f_1(n) + f_2(n) = O(g_1(n) + g_2(n))$ and that $f_1(n) + f_2(n) = O(max(g_1(n), g_2(n)))$
Show that $f_1 + f_2 + ... + f_k = O(f_{max})$. That is, in a finite constant sum of functions, the dominate function defines the growth rate. A private case is that of a polynomial.
for i in range(f1(n)):
for j in range(f2(n)):
O(1)
Show that $f_1(n) \cdot f_2(n) = O(g_1(n) \cdot g_2(n))$.
for i in range(f1(n)):
for j in range(i):
O(1)
Use $\sum$ to bound the time complexity in this case
$\sum_{i=1}^{n}{i} = O(n^2)$ - the arithmetic series
$\sum_{i=1}^{n}{2^i} = O(2^n)$ - the geometric series
for i in range(1,n+1):
j=1
while j<=n:
j += 1 # O(n**2)
j += 7 # O(n**2), inner loop does n/7 iterations
# for each outer loop
j *= 2 # O(n*log(n))
j *= 7 # O(n*log(n)), change log bases is like
# multiplying by a constant
j **= 2 # O(n*log(log(n))), we need to take a log on both sides
# *twice* (also for this case, j should start from 2)
j += i # O(n*log(n)), the sum of 1/i from i=1 to n is O(log(n))
Anonymous vs. named values
x = 2**10
print(x)
print(2**10)
Lambda expressions can be used for creating anonymous functions (and named ones as well)
(lambda x: x+2)(6)
(lambda x: x+2)(10)
plus_2 = lambda x: x+2
plus_2(6)
plus_2(10)
8
12
8
12
def make_pow(n):
return lambda x: pow(x,n)
sqr = make_pow(2)
sqr(10)
cub = make_pow(3)
cub(10)
make_pow(2)(10)
100
1000
100
and now without lambda
def make_pow(n):
def fixed_exp_pow(x):
return pow(x,n)
return fixed_exp_pow
make_pow(2)(10)
100
lst = ["michal", "daniel", "amirr", "amirg"]
Lexicographical string sorting:
sorted(lst)
['amirg', 'amirr', 'daniel', 'michal']
"sorted" can recieve a function as an argument and use it to sort the input list. The function is given as the "key" argument to "sorted". Note that the "key" is used for ordering the elements without changing them.
examples: sort by length, sort by reverse lexicographical order
lst = ["michal", "daniel", "amirr", "amirg"]
sorted(lst, key= lambda x : len(x))
sorted(lst, key= len)
sorted(lst, key= lambda x : x[::-1])
['amirr', 'amirg', 'michal', 'daniel']
['amirr', 'amirg', 'michal', 'daniel']
['amirg', 'michal', 'daniel', 'amirr']
another example: sort by the int value of the string elements
lst = ["3", "22", "111"]
sorted(lst)
sorted(lst, key = int)
['111', '22', '3']
['3', '22', '111']
def sum_naturals(n):
total = 0
for k in range(1, n+1):
total += k
return total
sum_naturals(10)
55
def sum_sqrs(n):
total = 0
for k in range(1, n+1):
total += k*k
return total
sum_sqrs(10)
385
These two functions are quite similar. We could write a function that computes the summation of $n$ elements, for a given natural number $n$ and a function "term" that for every $i$ returns the $i$th element in the sum.
def summation(n, term):
total = 0
for k in range(1, n+1):
total += term(k)
return total
def cub(k):
return k*k*k
summation(10, cub)
3025
The following (infinite) sum slowly converges to pi:
$\frac{8}{1\cdot 3} + \frac{8}{5\cdot 7} + \frac{8}{9\cdot11} + \ldots$
We use "summation" to compute the sum of the first $n$ elements in this series
def pi_term(i):
return 8/((4*i-3)*(4*i-1))
def pi(n):
return summation(n, pi_term)
pi(10)
pi(100)
pi(10000)
3.091623806667838
3.1365926848388144
3.1415426535898203
The function below can recieve any number of of values as its input, all are packed into a tuple named "params", in this case.
The content of a tuple can be unpacked using * when passed as input to another method, as if you'd passed every value separately.
def mult(*params):
result = 1
print(*params)
print(params)
for elem in params:
result *= elem
return result
mult(2,10,55,3)
2 10 55 3 (2, 10, 55, 3)
3300
def print_consecutive_sublist(lst, func, *params):
return func(lst, *params)
func = lambda lst, i, j : print(lst[i:j] if i <j else "bad range")
l = [i for i in range (100)]
print_consecutive_sublist(l, func, 50, 55)
print_consecutive_sublist(l, func, 55, 45)
print_consecutive_sublist(l, func, 55)
[50, 51, 52, 53, 54] bad range
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-24-3ce2017b99a6> in <module>() 7 print_consecutive_sublist(l, func, 50, 55) 8 print_consecutive_sublist(l, func, 55, 45) ----> 9 print_consecutive_sublist(l, func, 55) <ipython-input-24-3ce2017b99a6> in print_consecutive_sublist(lst, func, *params) 1 def print_consecutive_sublist(lst, func, *params): ----> 2 return func(lst, *params) 3 4 5 func = lambda lst, i, j : print(lst[i:j] if i <j else "bad range") TypeError: <lambda>() missing 1 required positional argument: 'j'
def print_sublist(lst, func, *params):
return func(lst, params)
func = lambda lst, tup : print([x for x in lst if x in tup])
l = [i for i in range (100)]
print_sublist(l, func, 50, 55)
print_sublist(l, func, 50, 55, 20)
[50, 55] [20, 50, 55]