teratail header banner
teratail header banner
質問するログイン新規登録

質問編集履歴

1

配列を1次元化した測定結果を追加

2017/08/28 01:56

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -11,6 +11,7 @@
11
11
  ```python
12
12
  import sys
13
13
 
14
+ # オンラインジャッジシステムでの処理時間: 約3.5秒
14
15
  def find_square0(data):
15
16
  max_size = 0
16
17
  dp = [] # dp用の2次元配列
@@ -51,6 +52,7 @@
51
52
  ###試したこと
52
53
  リストのリストにアクセスしているから遅いのだろうと考え、以下のように変更してみましたが、少し(2割くらい)改善しただけでした。
53
54
  ```python
55
+ # オンラインジャッジシステムでの処理時間: 約2.8秒
54
56
  def find_square2(data):
55
57
  max_size = 0
56
58
  dp = [[0]*len(data[0]) for _ in range(len(data))] # dp用の2次元配列
@@ -78,6 +80,53 @@
78
80
  dp = [array('I', [0]*len(data[0])) for _ in range(len(data))]
79
81
  ```
80
82
 
83
+ **2017-08-28追記**
84
+ okateimさんにコメントいただいた、配列(リスト)の1次元化を試してみました。
85
+ 配列を一つだけ確保する方式だと、配列のサイズが大きくなった時の速度ペナルティが厳しいようです。
86
+ ```python
87
+ # サイズ固定、オンラインジャッジシステムでの処理時間: 約4.9秒
88
+ def find_square4(data):
89
+ max_size = 0
90
+ dp = [0 for _ in range(1024*1024)]
91
+ # '.'のマスを1に
92
+ for y, row in enumerate(data):
93
+ for x, c in enumerate(row):
94
+ if c == '.':
95
+ dp[y*1024+x] = 1
81
96
 
97
+ # 対象のマスから左上に向かって、何マスの正方形が確保できるかチェックする
98
+ for y in range(1, len(data)):
99
+ for x in range(1, len(data)):
100
+ if dp[y*1024+x] == 1:
101
+ dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
102
+ if dp[y*1024+x] > max_size:
103
+ max_size = dp[y*1024+x]
104
+ return max_size
105
+ ```
106
+
107
+ ```python
108
+ # サイズ可変、オンラインジャッジシステムでの処理時間: 約5.2秒
109
+ def find_square4_2(data):
110
+ max_size = 0
111
+ n = len(data)
112
+ dp = [0 for _ in range(n**2)]
113
+ # '.'のマスを1に
114
+ for y, row in enumerate(data):
115
+ for x, c in enumerate(row):
116
+ if c == '.':
117
+ dp[y*n+x] = 1
118
+
119
+ # 対象のマスから左上に向かって、何マスの正方形が確保できるかチェックする
120
+ for y in range(1, len(data)):
121
+ for x in range(1, len(data)):
122
+ if dp[y*n+x] == 1:
123
+ dp[y*n+x] = min(dp[(y-1)*n+x-1], dp[(y-1)*n+x], dp[y*n+x-1]) + 1
124
+ if dp[y*n+x] > max_size:
125
+ max_size = dp[y*n+x]
126
+ return max_size
127
+ ```
128
+
129
+
130
+
82
131
  ###補足情報(言語/FW/ツール等のバージョンなど)
83
132
  オンラインのジャッジシステムを使用しているため、pythonのバージョンは3.4.2固定になります。また、NumPyなどの外部ライブラリを使用することはできません。