質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.48%

  • Python

    12188questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    10199questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • Python 2.7

    1468questions

    Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。

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

解決済

回答 5

投稿

  • 評価
  • クリップ 1
  • VIEW 1,522

super_tomato

score 26

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

# 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行目の要素を1つずつこのリストにいれていく
    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]))


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

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

+4

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

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")

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/25 12:55

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

    キャンセル

  • 2018/01/25 13:08 編集

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

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

    キャンセル

  • 2018/01/25 15:05

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

    キャンセル

checkベストアンサー

+3

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

こういう時は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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/25 10:59

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

    キャンセル

+2

相変らず競プロらしからぬコードですが、参考までに。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を使わずに書くのはなんだか新鮮です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/25 11:01

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

    キャンセル

+2

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/25 10:58

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

    キャンセル

+2

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>)


の速度の違いですね。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/26 20:50

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

    キャンセル

  • 2018/01/26 21:30

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

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

    キャンセル

  • 2018/01/26 21:52

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

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

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

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

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

    キャンセル

同じタグがついた質問を見る

  • Python

    12188questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    10199questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

  • Python 2.7

    1468questions

    Python 2.7は2.xシリーズでは最後のメジャーバージョンです。Python3.1にある機能の多くが含まれています。