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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Python 2.7

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

Python 3.x

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

Python

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

Q&A

解決済

5回答

4369閲覧

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

super_tomato

総合スコア34

Python 2.7

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

Python 3.x

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

Python

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

0グッド

1クリップ

投稿2018/01/24 14:08

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

python

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

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答5

0

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

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

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

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

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

python

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

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

投稿2018/01/25 03:36

maki

総合スコア72

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

super_tomato

2018/01/25 03:55

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

2018/01/25 04:09 編集

> というのは変数をsumにしてしまうと組み込み関数のsumが上書きされて組み込み関数のsumが使えなくなってしまうということでしょうか? そういうことです。組み込み関数としての動作をしなくなってしまいます。 一応、del sumとすることで戻ります。
super_tomato

2018/01/25 06:05

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

0

ベストアンサー

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

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

python

1n,m,l = map(int,input().split()) 2A = [[int(i) for i in input().split()] for _ in range(n)] 3B = [[int(i) for i in input().split()] for _ in range(m)] 4 5res = [ 6 [sum([ 7 a*b for a,b in zip(A[i],list(zip(*B))[j]) 8 ]) 9 for j in range(l)] 10for i in range(n)] 11 12for r in res: 13 print(*r)

Python 3.6.1

投稿2018/01/24 14:53

編集2018/01/24 15:15
namnium1125

総合スコア2043

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

super_tomato

2018/01/25 01:59

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

0

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

python

1n, m, l = map(int, input().split()) 2get_mat = lambda n: [list(map(int, input().split())) for _ in range(n)] 3 4a = get_mat(n) 5b = get_mat(m) 6transpo = lambda a: [v for v in zip(*a)] 7b = transpo(b) 8 9dotv = lambda x,y: sum([s*t for s,t in zip(x,y)]) 10c = ((dotv(u,v) for u in b) for v in a) 11 12for v in c: 13 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/25 13:26

編集2018/01/25 16:19
mkgrei

総合スコア8560

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

super_tomato

2018/01/26 11:50

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

2018/01/26 12:30

プロファイリングするわかるのですが、print文に時間を使っています。 これはOS側の問題なので一概にPythonが悪いわけではないのですが、実用上ネックになることが多く、書き出し時は溜めて一気に、というのが一般的です。 上記のサイトの採点の際ではprint文に時間はかかっていないようです。 書き出しの方法を変えると手元では時間は変わりましたが、サイト採点では同じでした。 ターミナル出力とファイル出力とでは時間が変化しています。 stdoutをリダイレクトしてバッファに溜めているのかもしれません。
mkgrei

2018/01/26 12:52

ちなみに問題の「提出ボタン」の近くに「他人の解答ボタン」があって他の人の提出物を見れます。 言語別に選択できて、それぞれの実行時間も見れます。 どのようなコードを書いたら遅くなって、どのようなコードを書いたら速くなるのか。 どうしたらコードを短くできるのか、など勉強することができます。 難点はクリックしないとコードまで見れないことです。 このサイトなら他の人の回答を見て、違う書き方をしてくれる方々がいるので短い時間でいろいろなバリエーションが見れますね。 また一般的なことですが、同じことをしているコードでもPythonよりC/C++のほうが10倍以上速いです。 Pythonになれるためであればよいのですが、 競技プログラミングを極めるのであればC++も検討すべきです。
guest

0

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

投稿2018/01/24 14:58

can110

総合スコア38234

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

super_tomato

2018/01/25 01:58

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

0

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

Python

1def scalar_product(vec1, vec2): 2 """ベクトルのスカラー積を返すよ 3 """ 4 return sum(e1*e2 for e1, e2 in zip(vec1, vec2)) 5 6def get_col_vec(mat_2dim, col_num): 7 """二次元の行列について、指定列を返すよ 8 """ 9 return [row[col_num] for row in mat_2dim] 10 11def enumerate_col(mat): 12 """二次元の行列について、enumerateの列版だよ 13 """ 14 length = len(mat[0]) 15 for i in range(length): 16 yield i, get_col_vec(mat, i) 17 18def product_2dim(mat1, mat2): 19 """行列の積を計算するよ 20 """ 21 return [ 22 [ 23 scalar_product(row, col) 24 for col_n, col in enumerate_col(mat2) 25 ] 26 for row_n, row in enumerate(mat1) 27 ] 28 29def print_mat(mat): 30 """二次元の行列を表示するよ 31 """ 32 for row in mat: 33 print(*row) 34 35def input_mat(row_n): 36 """二次元の行列の入力を受け付けるよ 37 """ 38 return [[int(e) for e in input().split()] for _ in range(row_n)] 39 40 41s1, s2, _ = map(int, input().split()) 42mat1 = input_mat(s1) 43mat2 = input_mat(s2) 44 45mat3 = product_2dim(mat1, mat2) 46print_mat(mat3)

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

投稿2018/01/24 14:42

LouiS0616

総合スコア35658

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

super_tomato

2018/01/25 02:01

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問