[PYTHON] Graduate School of Information Science and Technology, The University of Tokyo, Department of Creative Informatics, Summer 2018 Programming Exam
This is an example of the answer to the 2018 summer exam.
- The content of the description is personally solved by the author and does not guarantee the correct answer, and is not related to the University of Tokyo or the organization involved in providing the content of this examination.
Question theme
--Cash miss
Problem statement
- If the University of Tokyo points out, the problem statement will be deleted.
Distribution file
- Since it is not open to the public, the following is made by the author. mat1_sample.txt
0 1 2 3,4 5 6 7,8 9 10 11.
mat2_sample.txt
0 1 2,3 4 5,6 7 8,9 10 11.
(1) A: m^2n B: m^2n (2)
file_path = 'mat1_sample.txt'
def solve():
with open(file_path, 'r') as f:
text = f.read()
text = text.split('.')[0]
text_array = text.split(',')
mat = []
for text in text_array:
row = text.split(' ')
for index, strnum in enumerate(row):
row[index] = int(strnum)
mat.append(row)
row_num = len(mat)
col_num = len(mat[0])
print(row_num, col_num)
(3)
file_path1 = 'mat1_sample.txt'
file_path2 = 'mat2_sample.txt'
import numpy as np
def parse_file(file_path):
with open(file_path, 'r') as f:
text = f.read()
text = text.split('.')[0]
text_array = text.split(',')
mat = []
for text in text_array:
row = text.split(' ')
for index, strnum in enumerate(row):
row[index] = int(strnum)
mat.append(row)
return np.array(mat)
def solve(file_path1, file_path2):
mat1 = parse_file(file_path1)
mat2 = parse_file(file_path2)
mat = np.dot(mat1, mat2)
ans = 0
for i in range(0, len(mat)):
ans += mat[i, i]
return ans
(4)
class Ele(object):
def __init__(self, mat_name:str, row:int, col:int):
self.mat_name = mat_name
self.row = row
self.col = col
def __repr(self):
return 'mat_name: {0}, row_idx: {1}, col_idx: {2}'.fromat(self.mat_name, self.row, self.col)
def solve(m, n, s):
#Next cache idx to push
next_cache_idx = 0
#Specify what is in idx in cache
cache = np.empty(s, dtype=Ele)
#mem in memory_a[i, j] ai,Returns the index of the cache that contains j If it is not in the cache-1
mem_a = -1*np.ones((m, n), dtype=np.int)
mem_b = -1*np.ones((n, m), dtype=np.int)
a_num = 0
b_num = 0
for i in range(0, m):
for j in range(0, m):
for k in range(0, n):
# ai,k
if (mem_a[i, k] < 0): #Not in cache
a_num += 1
if (cache[next_cache_idx] != None): #The cache location to put is not empty
#Kick out
ele = cache[next_cache_idx]
#Update mem
if (ele.mat_name == 'A'):
mem_a[ele.row][ele.col] = -1
elif (ele.mat_name == 'B'):
mem_b[ele.row][ele.col] = -1
ele = Ele('A', i, k)
cache[next_cache_idx] = ele #Put in cache
mem_a[i, k] = 1 #In cache
next_cache_idx += 1
if (next_cache_idx >= s):
next_cache_idx = 0
# bk,j
if (mem_b[k, j] < 0): #Not in cache
b_num += 1
if (cache[next_cache_idx] != None): #The cache location to put is not empty
#Kick out
ele = cache[next_cache_idx]
#Update mem
if (ele.mat_name == 'A'):
mem_a[ele.row][ele.col] = -1
elif (ele.mat_name == 'B'):
mem_b[ele.row][ele.col] = -1
ele = Ele('B', k, j)
cache[next_cache_idx] = ele #Put in cache
next_cache_idx += 1
mem_b[k, j] = 1 #In cache
if (next_cache_idx >= s):
next_cache_idx = 0
return a_num, b_num
(5) In order u p v p w p (6)
def solve(m, n, p, s):
#Specify what is in idx in cache
cache = np.empty(s, dtype=Ele)
#mem in memory_a[i, j] ai,Returns the index of the cache that contains j If it is not in the cache-1
mem_a = -1*np.ones((m, n), dtype=np.int)
mem_b = -1*np.ones((n, m), dtype=np.int)
data = { 'a_num': 0, 'b_num': 0, 'next_cache_idx': 0 }
def check_cache():
if (cache[data['next_cache_idx']] != None): #The cache location to put is not empty
ele = cache[data['next_cache_idx']]
#Update mem
if (ele.mat_name == 'A'):
mem_a[ele.row][ele.col] = -1
elif (ele.mat_name == 'B'):
mem_b[ele.row][ele.col] = -1
def check_A(i, k):
if (mem_a[i, k] < 0): #Not in cache
data['a_num'] += 1
check_cache()
ele = Ele('A', i, k)
cache[data['next_cache_idx']] = ele #Put in cache
data['next_cache_idx'] += 1
mem_a[i, k] = 1
if (data['next_cache_idx'] >= s):
data['next_cache_idx'] = 0
def check_B(k, j):
if (mem_b[k, j] < 0): #Not in cache
data['b_num'] += 1
check_cache()
ele = Ele('B', k, j)
cache[data['next_cache_idx']] = ele #Put in cache
data['next_cache_idx'] += 1
mem_b[k, j] = 1
if (data['next_cache_idx'] >= s):
data['next_cache_idx'] = 0
u = 0
while (u < m):
v = 0
while (v < m):
w = 0
while (w < n):
i = u
while (i < u + p):
j = v
while (j < v + p):
k = w
while (k < w + p):
# ai,k
check_A(i,k)
# bk,j
check_B(k,j)
k += 1
j += 1
i += 1
w += p
v += p
u += p
return data
(7) I'm sorry, I couldn't solve it ... Please let me know if you understand
Impressions
-When I solved up to (6), I thought that this year was an easy one ... (Even though it is easy, there are only a few points to implement, and if only (4) can be done, it means that it will be reused. I don't think it's a low-level exam.) ――The number of cache misses was counted separately for A and B. The reason is that in the problem of matrix calculation cache misses like this time, there are many problems to ask that the number of cache misses is actually different between A and B. (Although it didn't really matter on this issue ...) -(4) However, I think there is an implementation method that searches the cache completely, and I feel that it is actually easier to implement it. However, I dared to implement a complicated implementation so that the cache can be expelled and updated with the computational complexity O (1). The reason is that I thought that the cache was for speed. If you actually drop the cache of this problem, it is probably a full-associative cache, so a full search makes more sense, but I wondered if it would take time. Instead, as you can see, my implementation takes up a lot of memory. --Additionally, in (7), it takes m ^ 2ns, that is, 200 * 200 * 150 * 600 = 3.6e10 for full search, and probably several minutes for python. ――It took about an hour and a half to finish up to (6), but I couldn't solve (7) even if I was worried about it ... I feel that the field is discrete mathematics, so please let me know if you are a professional!
Recommended Posts