競技プログラミングの問題(Python)_行列の積

Question

下記のサイトの競技プログラミングの問題を解きました。
競技プログラミングの問題
二つの行列の積を求める問題です。
もしお時間があれば、この問題のプログラムを作成していただきぜひ参考にさせていただきたいです。
下記が僕が作成したプログラムです。多くの改善点があると思うので、改善するべきところを指摘していただくだけでも構いません。

# coding: UTF-8
n,m,l = map(int,raw_input().split(" "))
a_matrix = [map(int,raw_input().split()) for i in range(n)]#行列a
b_matrix = [map(int,raw_input().split()) for i in range(m)]#行列b
c_matrix = [] #演算後の行列
for i in range(n):
    tmp_list = []#i行目の要素を１つずつこのリストにいれていく
    for j in range(l):
        sum = 0
        for k in range(m):
            sum += a_matrix[i][k] * b_matrix[k][j] #積の計算
        tmp_list.append(sum) #i行j列目の要素を追加
    c_matrix.extend([tmp_list])#i行目の要素がすべてそろと追加
for x in range(n):
    print " ".join(map(str,c_matrix[x]))

以上よろしくお願いします。

Answer 1

終わってしまった問題ではありますが、昼休み中に解答できてしまったので乗せちゃいます。

super_tomatoさんのコードを見て気になったこと

• sumは組み込み関数なので、上書きしてしまうのはだめです。

合計値を表現するなら別の変数名を利用しましょう。

• 速度を気にするなら、即時printの方が望ましいです。
• それ以外は細かいところになるので極力シンプルに組みなおしてみました。

n, m, l = map(int, input().split())
A = [[int(i) for i in input().split()] for _ in range(n)]
B = [[int(i) for i in input().split()] for _ in range(m)]

for i in range(n):
    for j in range(l):
        # 公式をそのまま利用し、C[i][j]の結果を取得し、そのまま出力
        # endにはi行の末尾 つまりl列目に来たら改行、それ以外なら空白を入れる。
        print(sum([A[i][k] * B[k][j] for k in range(m)]), end=" " if j < l - 1 else "\n")

前回同様シンプルに考えてみました

Comments

[super_tomato]

今回もありがとうございます！！ご指摘ありがとうございます。
>>sumは組み込み関数なので、上書きしてしまうのはだめです。
合計値を表現するなら別の変数名を利用しましょう。
というのは変数をsumにしてしまうと組み込み関数のsumが上書きされて組み込み関数のsumが使えなくなってしまうということでしょうか？

[maki]

> というのは変数をsumにしてしまうと組み込み関数のsumが上書きされて組み込み関数のsumが使えなくなってしまうということでしょうか？

そういうことです。組み込み関数としての動作をしなくなってしまいます。
一応、del sumとすることで戻ります。

[super_tomato]

なるほど。知りませんでした...。勉強になりました！ありがとうございます！

Answer 2

性懲りもせず、リスト内包表記で遊んでみました。

こういう時はzipが便利ですかね。

n,m,l = map(int,input().split())
A = [[int(i) for i in input().split()] for _ in range(n)]
B = [[int(i) for i in input().split()] for _ in range(m)]

res = [
    [sum([
        a*b for a,b in zip(A[i],list(zip(*B))[j])
    ])
    for j in range(l)]
for i in range(n)]

for r in res:
    print(*r)

Python 3.6.1

Comments

[super_tomato]

リスト内包表記だとすっきりしますね！ご回答ありがとうございました。

Answer 3

LouiS0616さんのと似ているけど、出来る限り変な書き方してみました。
このサイズでどうかはわかりませんが、書き出しは一気にやったほうが速いです（Pythonの一般論←AIZUのジャッジだとバッファしてくれるらしくあまり影響しないですね。そして整数から文字列へのキャストを消すと0.01s速くなりますね）。

n, m, l = map(int, input().split())
get_mat = lambda n: [list(map(int, input().split())) for _ in range(n)]

a = get_mat(n)
b = get_mat(m)
transpo = lambda a: [v for v in zip(*a)]
b = transpo(b)

dotv = lambda x,y: sum([s*t for s,t in zip(x,y)])
c = ((dotv(u,v) for u in b) for v in a)

for v in c:
    print(*v)

---

https://qiita.com/Syo_pr/items/92b3cf7d7fc5dab4a3a7
行列積についての一般的なアルゴリズム。
普通はキャッシュ効率を高めることで高速化します。
Pythonでは意味ないです…（ホント？←たぶん転置してからのほうが速いですね）

http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1320-16.pdf
計算量を削減できるアルゴリズム。
実装は…

---

sum(s*t for s,t in zip(x,y))
より
sum([s*t for s,t in zip(x,y)])
のほうが速いのか…

1010000    0.141    0.000    0.141    0.000 p2-3.py:9(<genexpr>)`
10000    0.007    0.000    0.247    0.000 p2-3.py:9(<lambda>)

と

10000    0.016    0.000    0.115    0.000 p2-3.py:9(<lambda>)
10000    0.089    0.000    0.089    0.000 p2-3.py:9(<listcomp>)

の速度の違いですね。

Comments

[super_tomato]

なるほど。一気のほうが速いんですね！勉強になります。
ご回答ありがとうございました。

[mkgrei]

プロファイリングするわかるのですが、print文に時間を使っています。
これはOS側の問題なので一概にPythonが悪いわけではないのですが、実用上ネックになることが多く、書き出し時は溜めて一気に、というのが一般的です。

上記のサイトの採点の際ではprint文に時間はかかっていないようです。
書き出しの方法を変えると手元では時間は変わりましたが、サイト採点では同じでした。
ターミナル出力とファイル出力とでは時間が変化しています。
stdoutをリダイレクトしてバッファに溜めているのかもしれません。

[mkgrei]

ちなみに問題の「提出ボタン」の近くに「他人の解答ボタン」があって他の人の提出物を見れます。
言語別に選択できて、それぞれの実行時間も見れます。

どのようなコードを書いたら遅くなって、どのようなコードを書いたら速くなるのか。
どうしたらコードを短くできるのか、など勉強することができます。

難点はクリックしないとコードまで見れないことです。

このサイトなら他の人の回答を見て、違う書き方をしてくれる方々がいるので短い時間でいろいろなバリエーションが見れますね。

また一般的なことですが、同じことをしているコードでもPythonよりC/C++のほうが10倍以上速いです。
Pythonになれるためであればよいのですが、
競技プログラミングを極めるのであればC++も検討すべきです。

Answer 4

計算結果c(i,j)は溜めずにどんどん出してやればよいです。メモリも速度も改善されます。
出力時、cの各要素の区切り文字としてスペースまたは改行いずれを出力すべきかに注意してください。

Comments

[super_tomato]

確かにそうですね！ご回答ありがとうございました。

Answer 5

相変らず競プロらしからぬコードですが、参考までに。Wandbox

def scalar_product(vec1, vec2):
    """ベクトルのスカラー積を返すよ
    """
    return sum(e1*e2 for e1, e2 in zip(vec1, vec2))

def get_col_vec(mat_2dim, col_num):
    """二次元の行列について、指定列を返すよ
    """
    return [row[col_num] for row in mat_2dim]

def enumerate_col(mat):
    """二次元の行列について、enumerateの列版だよ
    """
    length = len(mat[0])
    for i in range(length):
        yield i, get_col_vec(mat, i)

def product_2dim(mat1, mat2):
    """行列の積を計算するよ
    """
    return [
        [
            scalar_product(row, col)
            for col_n, col in enumerate_col(mat2)
        ]
        for row_n, row in enumerate(mat1)
    ]

def print_mat(mat):
    """二次元の行列を表示するよ
    """
    for row in mat:
        print(*row)
        
def input_mat(row_n):
    """二次元の行列の入力を受け付けるよ
    """
    return [[int(e) for e in input().split()] for _ in range(row_n)]
        

s1, s2, _ = map(int, input().split())
mat1 = input_mat(s1)
mat2 = input_mat(s2)

mat3 = product_2dim(mat1, mat2)
print_mat(mat3)

numpyを使わずに書くのはなんだか新鮮です。

Comments

[super_tomato]

分かりやすいコードありがとうございます！