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
print(2**10)
x = 2**10
print(x)
1024 1024
Lambda expressions can be used for creating anonymous functions (and named ones as well)
(lambda x: x+2)(3)
plus2 = lambda x : x + 2
plus2(3)
5
5
def make_pow(n):
def fixed_pow(x):
return x**n
return fixed_pow
square = make_pow(2)
cube = make_pow(3)
square(10)
cube(10)
100
1000
def make_pow(n):
return lambda x : x ** n
square = make_pow(2)
cube = make_pow(3)
square(10)
cube(10)
100
1000
lst = ["michal", "amirrub", "daniel", "amirgil"]
sorted(lst)
['amirgil', 'amirrub', '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
sorted(lst, key = lambda s : len(s))
sorted(lst, key = len)
sorted(lst, key = lambda s : s[::-1])
['michal', 'daniel', 'amirrub', 'amirgil']
['michal', 'daniel', 'amirrub', 'amirgil']
['amirrub', 'michal', 'daniel', 'amirgil']
another example: sort by the int value of the string elements
lst2 = ["232", "11", "3"]
sorted(lst2)
sorted(lst2, key=int)
['11', '232', '3']
['3', '11', '232']
def sum_naturals(n):
total = 0
for k in range(1,n+1):
total += k
return total
sum_naturals(10)
55
def sum_squres(n):
total = 0
for k in range(1,n+1):
total += k**2
return total
sum_squres(10)
385
Let's make it a general function that gets another function as a parameter:
def summation(n, term):
total = 0
for k in range(1,n+1):
total += term(k)
return total
The equivalent to sum_naturals and sum_squares:
term_naturals = lambda x : x
summation(10, term_naturals)
term_squares = lambda x : x**2
summation(10, term_squares)
55
385
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
term_pi = lambda k : 8 / ((4*k-1) * (4*k-3))
summation(10, term_pi)
summation(100, term_pi)
summation(10000000, term_pi)
3.091623806667838
3.1365926848388144
3.1415926035880983
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 print_consecutive_sublist(lst, func, *params):
func(lst, *params)
func = lambda lst, i, j : print(lst[i:j] if i < j else "bad range")
print_consecutive_sublist([i for i in range(100)], func, 50,55)
print_consecutive_sublist([i for i in range(100)], func, 55,50)
print_consecutive_sublist([i for i in range(100)], func, 50,55,56) # more than three arguments given to func
[50, 51, 52, 53, 54] bad range
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) <ipython-input-18-e1177d111490> in <module>() 5 print_consecutive_sublist([i for i in range(100)], func, 50,55) 6 print_consecutive_sublist([i for i in range(100)], func, 55,50) ----> 7 print_consecutive_sublist([i for i in range(100)], func, 50,55,56) # more than three arguments given to func <ipython-input-18-e1177d111490> in print_consecutive_sublist(lst, func, *params) 1 def print_consecutive_sublist(lst, func, *params): ----> 2 func(lst, *params) 3 4 func = lambda lst, i, j : print(lst[i:j] if i < j else "bad range") 5 print_consecutive_sublist([i for i in range(100)], func, 50,55) TypeError: <lambda>() takes 3 positional arguments but 4 were given
def print_sublist(lst, func, *params):
# print(*params)
# print(params)
func(lst, params)
func2 = lambda lst, tup : print([x for x in lst if x in tup])
print_sublist([i for i in range(100)], func2, 50,55, 43, 44, 90)
[43, 44, 50, 55, 90]