Extra Homework 2 Solutions
Solutions: You can find the file with solutions for all questions here.
Multiprocessing in Python using Ray
If you face timeout errors, you might want to use the timeout flag while running the tests. Try --timeout 60 for a 60 seconds timeout.
Installing Ray
Before running the assignment you would need to installray. You can simply run pip install -U ray in your console. For further details, you can visit Ray Installation Guide.
Q1: Parallel Map
Implement parallel_map, which takes a list arr and a mapping function f. It should return a new list computed by applying f to each element of arr. A serial version of the map function, serial_map is given for your convenience in understanding the problem and also for evaluating your solution (along with the function func). You must not change serial_map or func. Notice that ray has been initialized for you with 4 processes and you do not need to call ray.init().
extra02.py runs in one of the 4 processes allocated for Ray. Hence, you can assume you have 3 more unused processes for your use.
def serial_map(arr, f):
"""A serial implementation of map. DO NOT CHANGE.
>>> serial_map(list(range(10)), lambda x: x*2)
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
>>> serial_map(list(range(10)), lambda x: x**2)
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
"""
return [f(x) for x in arr]
def func(x):
time.sleep(0.1)
return x
def parallel_map(arr, f):
"""A parallel implementation of map
>>> import time
>>> parallel_map(list(range(10)), lambda x: x*2)
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
>>> parallel_map(list(range(10)), lambda x: x**2)
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]
>>> arr = list(range(50))
>>> start = time.time()
>>> res_s = serial_map(arr, func)
>>> end = time.time()
>>> time_s = end - start
>>> start = time.time()
>>> res_p = parallel_map(arr, func)
>>> end = time.time()
>>> time_p = end - start
>>> (res_s == res_p) == True
True
>>> (time_s/time_p > 1.5) == True
True
"""
@ray.remote
def helper(arr):
return [f(x) for x in arr]
mid = len(arr)//2
fh = helper.remote(arr[0:mid])
lh = helper.remote(arr[mid:])
[fh, lh] = ray.get([fh, lh])
return fh+lhQ2: Parallel Merge Sort
Implement parallel_merge_sort, which takes a list arr and returns a new list with the elements sorted in ascending order. A serial version of the map function, sequential_merge_sort is given for your convenience in understanding the problem and also for evaluating your solution. You must not change sequential_merge_sort. Notice that ray has been initialized for you with 4 processes and you do not need to call ray.init().
extra02.py runs in one of the 4 processes allocated for Ray. Hence, you can assume you have 3 more unused processes for your use.
Hint: As we have a limited number of processes available, you might want to stop calling remote functions(which require new processes) after a certain depth of recursion.
def sequential_merge_sort(arr):
"""A parallel implementation of merge sort.
>>> arr = [1,5,3,2,4,9,8,7,6]
>>> sequential_merge_sort(arr)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
"""
arr2 = arr.copy()
if len(arr) > 1:
# Finding the mid of the array
mid = len(arr)//2
# Dividing the array elements
L = arr[:mid]
# into 2 halves
R = arr[mid:]
# Sorting the first half
L = sequential_merge_sort(L)
# Sorting the second half
R = sequential_merge_sort(R)
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr2[k] = L[i]
i += 1
else:
arr2[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr2[k] = L[i]
i += 1
k += 1
while j < len(R):
arr2[k] = R[j]
j += 1
k += 1
return arr2
def parallel_merge_sort(arr):
"""A parallel implementation of merge sort.
>>> import random
>>> import time
>>> nums = list(random.sample(range(0, 1000000), 1000000))
>>> start = time.time()
>>> s1 = sequential_merge_sort(nums)
>>> time_s = time.time() - start
>>> start = time.time()
>>> s2 = parallel_merge_sort(nums)
>>> time_p = time.time() - start
>>> (s1==s2) == True
True
>>> (time_s/time_p > 1.5) == True
True
"""
@ray.remote
def mergeSort(arr, level):
arr2 = arr.copy()
if len(arr) > 1:
# Finding the mid of the array
mid = len(arr)//2
# Dividing the array elements
L = arr[:mid]
# into 2 halves
R = arr[mid:]
# Sorting the first half
if level<1:
L = mergeSort.remote(L, level=level+1)
R = mergeSort.remote(R, level=level+1)
[L,R] = ray.get([L, R])
else:
L = mergeSort._function(L, level=level+1)
# Sorting the second half
R = mergeSort._function(R, level=level+1)
i = j = k = 0
# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] < R[j]:
arr2[k] = L[i]
i += 1
else:
arr2[k] = R[j]
j += 1
k += 1
# Checking if any element was left
while i < len(L):
arr2[k] = L[i]
i += 1
k += 1
while j < len(R):
arr2[k] = R[j]
j += 1
k += 1
return arr2
return ray.get(mergeSort.remote(arr, 0))Optional Questions
Section 2.4.9 describes a system for solving equations with multiple free parameters using constraint programming, a declarative style of programming that asserts constraints and then applies a general method of constraint satisfaction. The following questions ask you to extend that system. The code for the system appears at the end of this homework.
Q3: Triangle Area
Implement the function triangle_area, which defines a relation among
three connectors, the base b, height h, and area a of a triangle,
so that a = 0.5 * b * h:
def triangle_area(a, b, h):
"""Connect a, b, and h so that a is the area of a triangle with base b and
height h.
>>> a, b, h = [connector(n) for n in ('area', 'base', 'height')]
>>> triangle_area(a, b, h)
>>> a['set_val']('user', 75.0)
area = 75.0
>>> b['set_val']('user', 15.0)
base = 15.0
height = 10.0
"""
u, v = connector(), connector()
multiplier(b, v, u)
multiplier(u, h, a)
constant(v, 0.5)Q4: Squarer
The multiplier constraint from the readings is insufficient to model
equations that include squared quantities because constraint networks
must not include loops. Implement a new constraint squarer that
represents the squaring relation:
def squarer(a, b):
"""The constraint that a*a=b.
>>> x, y = connector('X'), connector('Y')
>>> s = squarer(x, y)
>>> x['set_val']('user', 10)
X = 10
Y = 100
>>> x['forget']('user')
X is forgotten
Y is forgotten
>>> y['set_val']('user', 16)
Y = 16
X = 4.0
"""
def new_value():
if a['has_val']():
b['set_val'](constraint, a['val'] ** 2)
elif b['has_val']():
a['set_val'](constraint, b['val'] ** 0.5)
def forget_value():
a['forget'](constraint)
b['forget'](constraint)
constraint = {'new_val': new_value, 'forget': forget_value}
a['connect'](constraint)
b['connect'](constraint)
return constraintUse Ok to test your code:
python3 ok -q squarerQ5: Pythagorean Theorem
Use your squarer constraint to build a constraint network for the
Pythagorean theorem: a squared plus b squared equals c squared:
def pythagorean(a, b, c):
"""Connect a, b, and c into a network for the Pythagorean theorem:
a*a + b*b = c*c
>>> a, b, c = [connector(name) for name in ('A', 'B', 'C')]
>>> pythagorean(a, b, c)
>>> a['set_val']('user', 5)
A = 5
>>> c['set_val']('user', 13)
C = 13
B = 12.0
"""
a_sq, b_sq, c_sq = [connector() for _ in range(3)]
squarer(a, a_sq)
squarer(b, b_sq)
squarer(c, c_sq)
adder(a_sq, b_sq, c_sq)Use Ok to test your code:
python3 ok -q pythagorean