東京大学大学院情報理工学系研究科 創造情報学専攻 2018年度 実技試験

東京大学大学院情報理工学系研究科 創造情報学専攻の2018年度 実技試験（プログラミング）の解答例（Python3）です。
https://www.i.u-tokyo.ac.jp/common/file/edu/course/ci/2017-8-program.pdf

※公開元ページはこちら
※記載の内容は筆者が個人的に解いたものであり、正答を保証するものではなく、また東京大学及び本試験内容の提供に関わる組織とは無関係です。

#(1)
問題文に記載のプログラムから、一番内側のループ1回の実行でa及びbから要素を読むため、2回あり、外側のループから、
2*{(nm)m} = 2nm^2

#(2)
本当の試験ではUSBメモリを渡されて、その中にmat1.txtがあるわけですが（おそらく非常に大きなファイル）、今回は以下のファイルをサンプルとして想定します。

• mat1.txt

0 1 2 3,4 5 6 7,8 9 10 11.xxx

• 2.py

import numpy as np
import re
def setArray(fn):
   mat = open(fn,'r')
   rn = 0 
   cn = 0 
   for row in mat:
       regex = re.compile('([0-9 \.]+)(\.|,)')
       ret = regex.findall(row.strip())
       rn = len(ret)
       n = 0 
       for i in ret:
           tmp = i[0].strip().split(' ')
           if cn == 0:
               cn = len(tmp)
               A = np.zeros((rn,cn)).astype(int)
           A[n] = tmp 
           n = n + 1 
       print("rn,cn:"+str(A.shape))
   return A
A = setArray("./mat1.txt")

rn,cn:(3, 4)

rnが行の数、cnが列の数になります。

#(3)
想定するmat2.txtとプログラム、実行結果は以下になります。

• mat2.txt

12 13 14,15 16 17,18 19 20,21 22 23.

• 3.py

import numpy as np
import re
def setArray(fn):
   mat = open(fn,'r')
   rn = 0 
   cn = 0 
   for row in mat:
       regex = re.compile('([0-9 \.]+)(\.|,)')
       ret = regex.findall(row.strip())
       rn = len(ret)
       n = 0 
       for i in ret:
           tmp = i[0].strip().split(' ')
           if cn == 0:
               cn = len(tmp)
               A = np.zeros((rn,cn)).astype(int)
           A[n] = tmp 
           n = n + 1 
       print("rn,cn:"+str(A.shape))
   return A
A = setArray("./mat1.txt")
B = setArray("./mat2.txt")
C = np.dot(A,B)
print(C)
print(sum(np.diag(C)))

rn,cn:(3, 4)
rn,cn:(4, 3)
[[114 120 126]
[378 400 422]
[642 680 718]]
1232

#(4)
(4)からは、メモリ、キャッシュメモリを使った読み込みに関する問題が続きます。
m,n,s（キャッシュ）からメモリから読む回数を数えるプログラムは以下になります。

def readCount(m,n,s):
    i = 0 
    ret = 0 
    c = {}
    for i in range(m):
        j = 0 
        for j in range(m):
            d = 0 
            k = 0 
            for k in range(n):
                index = "a:"+str(i)+":"+str(k)
                try:
                    c[index]
                except KeyError:
                    ret = ret + 1 
                    if len(c) >= s and len(c) > 0:
                        delKey = min(c, key=c.get)
                        del c[delKey]
                c[index] = k + j*n + i*m*n
                index = "b:"+str(k)+":"+str(j)
                try:
                    c[index]
                except KeyError:
                    ret = ret + 1 
                    if len(c) >= s and len(c) > 0:
                        delKey = min(c, key=c.get)
                        del c[delKey]
                c[index] = k + j*n + i*m*n
                k = k + 1 
            j = j + 1 
        i = i + 1 
    return str(ret)

#(5)
効率化のためにm,nの公約数pを使ったプログラムに変わります。
空欄はこのようになると思われます。
i < u + p
j < v + p
k < w + p

#(6)
(5)の実装をすればよいので以下のようになります。

def readCount(m,n,p,s):
    i = 0
    ret = 0
    c = {}
    u = 0

    indexValue = 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:
                            indexValue = indexValue + 1
                            index = "a:"+str(i)+":"+str(k)
                            try:
                                c[index]
                            except KeyError:
                                ret = ret + 1
                                if len(c) >= s and len(c) > 0:
                                    delKey = min(c, key=c.get)
                                    del c[delKey]
                            c[index] = indexValue
                            index = "b:"+str(k)+":"+str(j)
                            try:
                                c[index]
                            except KeyError:
                                ret = ret + 1
                                if len(c) >= s and len(c) > 0:
                                    delKey = min(c, key=c.get)
                                    del c[delKey]
                            c[index] = indexValue
                            k = k + 1
                        j = j + 1
                    i = i + 1
                w = w + p
            v = v + p
        u = u + p
    return str(ret)

問題は(7)までですが、筆者は解くのが難しかったのでできれば後日まとめられればと思っています（詳しい方いたらぜひ教えてください！）。