2018年度夏の院試の解答例です
※記載の内容は筆者が個人的に解いたものであり、正答を保証するものではなく、また東京大学及び本試験内容の提供に関わる組織とは無関係です。
出題テーマ
- キャッシュミス
問題文
※ 東京大学側から指摘があった場合は問題文を削除いたします。
配布ファイル
※ 公開されていないので以下は筆者が適当に作ったものです
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)
この問題はご指摘を頂いき、コメントにLRU Cacheの実装を掲載したのでそちらを参考にしていただけると幸いです。
keyをうまく設定すればそのまま使用できると思います。
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):
# 次にpushするcacheのidx
next_cache_idx = 0
# cacheでidxに入っているものを指定
cache = np.empty(s, dtype=Ele)
# memmoryでmem_a[i, j] ai,jの入っているキャッシュのインデックスを返すキャッシュに入ってない場合-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): # キャッシュにない
a_num += 1
if (cache[next_cache_idx] != None): # 入れるキャッシュの場所が空でない
# 追い出す
ele = cache[next_cache_idx]
# 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 # cacheに入れる
mem_a[i, k] = 1 # cacheにある
next_cache_idx += 1
if (next_cache_idx >= s):
next_cache_idx = 0
# bk,j
if (mem_b[k, j] < 0): # キャッシュにない
b_num += 1
if (cache[next_cache_idx] != None): # 入れるキャッシュの場所が空でない
# 追い出す
ele = cache[next_cache_idx]
# 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 # cacheに入れる
next_cache_idx += 1
mem_b[k, j] = 1 # cacheにある
if (next_cache_idx >= s):
next_cache_idx = 0
return a_num, b_num
(5)
順番にu p v p w p
(6)
def solve(m, n, p, s):
# cacheでidxに入っているものを指定
cache = np.empty(s, dtype=Ele)
# memmoryでmem_a[i, j] ai,jの入っているキャッシュのインデックスを返すキャッシュに入ってない場合-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): # 入れるキャッシュの場所が空でない
ele = cache[data['next_cache_idx']]
# 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): # キャッシュにない
data['a_num'] += 1
check_cache()
ele = Ele('A', i, k)
cache[data['next_cache_idx']] = ele # 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): # キャッシュにない
data['b_num'] += 1
check_cache()
ele = Ele('B', k, j)
cache[data['next_cache_idx']] = ele # 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)
すみません、解けなかったです...
わかる方はぜひ教えてください
感想
- (6)まで解いた時はこの年は簡単な方だなと思ってました...（簡単と言っても実装すべきポイントが少ないだけで(4)さえできれば後は使い回しという意味です。決してレベルが低い試験ではないと思います。）
- キャッシュミスの回数ですがAとBで別々にカウントしました。理由としては今回のように行列計算のキャッシュミスをテーマにする問題では、よくAとBでは実はキャッシュミスの回数が違うんだよと尋く問題が多いからです。（この問題ではあまり関係はなかったけど...）
- (4)なのですがcacheを全探索する実装の方法もありだと思いますし、実際そちらの方が実装するのは楽な気がします。でも筆者はあえてcacheの追い出しと更新を計算量O(1)でできるように複雑な実装をしました。理由としてはやっぱりキャッシュというのは速さのためにあると思ったからです。この問題のキャッシュを現実に落としこむと多分フルアソシアティブ型のキャッシュなので全探索の方が筋は通っていますが、やっぱり時間がかかるのはどうかなーと思いました。その代わり見ていただけばわかるのですが筆者の実装ではメモリを多くとります。
- さらに補足すると(7)では全探索だとm^2nsつまり200200150*600=3.6e10の計算量がかかり、おそらくpythonだと数分かかってしまいます
- だいたい１時間半ちょっとで(6)までは終わったのですが(7)はだいぶ悩んでも解けませんでした...分野としては離散数学な気がしますのでプロの方は教えてください！