We have implemented a base conversion algorithm (from decimal to 2<=b<=36). We examined Python's memory model and analyzed the efficiency of constructing a list using + or += operators. Finally, we've seen an example for a binary search solution.
Before you click "Visualize Execution" button, you may want to use the following settings (can be adjusted via the drop boxes next to the textbox):
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
Converting from decimal to binary is done by integer division and modulo operations. Here is an implementation of the algorithm for conversion from decimal to a general base $b$.
def convert_base(n, b):
'''convert_base(int, int)->string
Returns the textual representation
of n(decimal) in base 2 <= b <= 10
'''
result = ""
while n != 0:
digit = n % b
n = n // b
result = str(digit) + result
return result
convert_base(10, 2)
convert_base(0, 5)
'1010'
''
convert_base above mishandles n = 0
def convert_base(n, b):
'''convert_base(int, int)->string
Returns the textual representation
of n(decimal) in base 2 <= b <= 10
'''
if n == 0:
return "0"
result = ""
while n != 0:
digit = n % b
n = n // b
result = str(digit) + result
return result
convert_base(0, 5)
convert_base(161, 16)
'0'
'101'
The improved version above fails for b > 10 (why ?) This issue is fixed in the final version below (improvement #2) (what happens when b = 1?)
def convert_base(n, b):
'''convert_base(int, int)->string
Returns the textual representation of n(decimal) in base 2 <= b <= 36
'''
assert 2 <= b <= 36
if n == 0:
return "0"
result = ""
alphabet = "0123456789abcdefghijklmnopqrstuvwxyz"
while n != 0:
digit = n % b
n = n // b
result = alphabet[digit] + result
return result
convert_base(161, 16)
convert_base(10, 2)
convert_base(10, 80)
'a1'
'1010'
--------------------------------------------------------------------------- AssertionError Traceback (most recent call last) <ipython-input-20-d75904b47e95> in <module> 1 convert_base(161, 16) 2 convert_base(10, 2) ----> 3 convert_base(10, 80) <ipython-input-19-a975136accdf> in convert_base(n, b) 4 ''' 5 ----> 6 assert 2<=b<=36 7 8 if n==0: AssertionError:
By understanding Python's memory model we
def change_num(num):
num = 999
x = 30
change_num(x)
print(x)
30
def add_to_list(lst):
lst.append(999)
mylst = [1, 2, 3]
print(mylst)
add_to_list(mylst)
print(mylst)
[1, 2, 3] [1, 2, 3, 999]
def change_lst(lst):
lst = []
mylst = [1, 2, 3]
print(mylst)
change_lst(mylst)
print(mylst)
[1, 2, 3] [1, 2, 3]
#1 basics #####################################################
a = 1000 #1
b = "hello" #2
a += len(b) #3
c = 2*b[:2] #4
if b != c: #5
c = b #6
del c #7
#2 lists #####################################################
a = 1000 #1
d = [a, 2] #2
d[1] = -1 #3
a = 1003 #4
for x in d: #5a
x = 7 #5b
#3 funcs #####################################################
a = 1000 #1
b = "hello" #2
def is_palindrome(a): #3a
b = a[::-1] #3b
return a == b #3c
is_pal = is_palindrome #4
x = is_pal(b) #5
#4 lists+funcs #####################################################
a = 1000 #1
d = [a, 2] #2
def f(a, d): #3a
a = 2000 #3b
d[0] = a #3c
d = [] #3d
return d #3e
x = f(a, d) #4
Extend(), append(), sort(), and sorted():
#5 – lists operators and methods #####################################################
lst = [3, 2, 1]
id(lst)
print(lst)
lst = lst+[0]
id(lst)
print(lst)
lst.append(4)
id(lst)
print(lst)
lst.insert(1,5)
id(lst)
print(lst)
lst.extend([6,7])
id(lst)
print(lst)
lst += [8]
id(lst)
print(lst)
79625288
[3, 2, 1]
79625672
[3, 2, 1, 0]
79625672
[3, 2, 1, 0, 4]
79625672
[3, 5, 2, 1, 0, 4]
79625672
[3, 5, 2, 1, 0, 4, 6, 7]
79625672
[3, 5, 2, 1, 0, 4, 6, 7, 8]
id(lst)
print(lst)
#sorted returns a sorted copy of the list, and does not change the original one
lst2 = sorted(lst)
id(lst)
print(lst)
#list.sort() sorts in place, and does not return anything
lst.sort()
id(lst)
print(lst)
79625672
[3, 5, 2, 1, 0, 4, 6, 7, 8]
79625672
[3, 5, 2, 1, 0, 4, 6, 7, 8]
79625672
[0, 1, 2, 3, 4, 5, 6, 7, 8]
We use + or += operators in order to construct the same list.
Using operator +: less efficient, since a new list is constructed every iteration the number of integers written to memory equals 1+2+ ... + n = (n+1)*n/2 (= asumptotically speaking, grows quadratically with n)
Using operator +=: more efficient, since the same list is extended again and again the number of integers written to memory equals n (= asumptotically speaking, grows linearly with n)
import time
n= 20000
lst = []
t0 = time.process_time()
for i in range(n):
lst = lst + [i]
t1 = time.process_time()
print("Extending a list n=", n, "times, using the + operator took", t1 - t0, "seconds")
lst = []
t0 = time.process_time()
for i in range(n):
lst += [i]
t1 = time.process_time()
print("Extending a list n=", n, "times, using the += operator (extend()) took", t1 - t0, "seconds")
Extending a list n= 20000 times, using the + operator took 1.8216400000000021 seconds Extending a list n= 20000 times, using the += operator (extend()) took 0.009539999999994109 seconds
We double the size of the input.
n = 40000
lst = []
t0 = time.process_time()
for i in range(n):
lst = lst + [i]
t1 = time.process_time()
print("Extending a list n=", n, "times, using the + operator took", t1 - t0, "seconds")
lst = []
t0 = time.process_time()
for i in range(n):
lst += [i]
t1 = time.process_time()
print("Extending a list n=", n, "times, using the += operator (extend()) took", t1 - t0, "seconds")
Extending a list n= 40000 times, using the + operator took 8.112637999999997 seconds Extending a list n= 40000 times, using the += operator (extend()) took 0.022804000000000713 seconds
In accordance with the theory, the running time of the inefficient code increases by a factor of approximately $2^2 = 4$ as n increases by 2, while the running time of the efficient code increases by a factor of approximately 2. Apparently n is large enough for the constants not to play a serious role, so that the measurements agree with the asymptotic analysis.
Question from an exam: Implement find_steady, a function that receives a list $L$ of sorted (ascending) unique integers, and returns a value $i \geq 0$ s.t. $L[i] == i$. If there is no such $i$, None is returned. If there is more than one such index, any one of them can be returned.
For example:
find_steady([3, 5, 9, 17]) => None
find_steady([-3, 0, 2, 10]) => 2
def find_steady(lst):
for i in range(len(lst)):
if lst[i] == i:
return i
return None
print(find_steady([3, 5, 9, 17]))
print(find_steady([-3, 0, 2, 10]))
None 2
def find_steady(lst):
n = len(lst)
left = 0
right = n-1
while left <= right:
middle = (right + left) // 2 # middle rounded down
if middle == lst[middle]: # item found
return middle
elif middle < lst[middle]: # item not in top half
right = middle - 1
else: # item not in bottom half
left = middle + 1
return None
print(find_steady([3, 5, 9, 17]))
print(find_steady([-3, 0, 2, 10]))
None 2
Question: In the worst case, how many operations would we need in each one of these solutions?
Question: What happens if the values in the list aren't necessarily unique?
# We would like the function to return 3
print(find_steady([-1, 0, 3, 3, 3]))
None