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

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

ただいまの
回答率

90.47%

  • Python

    12265questions

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

2次元配列アクセスの高速化

受付中

回答 1

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,051
退会済みユーザー

退会済みユーザー

前提・実現したいこと

pythonを使用して、アルゴリズムの勉強をしています。
Aizu Online Judgeの 0092 Square Searching という問題を2次元配列(リストのリスト)を使用して解くには解いたのですが、制限時間ギリギリなので高速化できないかと考えています。
pythonで2次元配列を使用する場合、どのように書くと速くなるでしょうか。

発生している問題・エラーメッセージ

プロファイラで確認したところ、ソース中の for y, for xループ中のdp[][]へのアクセス部分で実効時間の大部分を消費しているようです。

該当のソースコード

import sys

# オンラインジャッジシステムでの処理時間: 約3.5秒
def find_square0(data):
    max_size = 0
    dp = [] # dp用の2次元配列
    # '.'のマスを1に、'*'のマスを0に初期化
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
                max_size = 1
            else:
                temp.append(0)
        dp.append(temp)

    # 対象のマスから左上に向かって、何マスの正方形が確保できるかチェックする
    for y in range(1, len(dp)):
        for x in range(1, len(dp[0])):
            if dp[y][x] == 1:
                dp[y][x] = min(dp[y-1][x-1], dp[y-1][x], dp[y][x-1]) + 1
                if dp[y][x] > max_size:
                    max_size = dp[y][x]
    return max_size

def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square0(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

試したこと

リストのリストにアクセスしているから遅いのだろうと考え、以下のように変更してみましたが、少し(2割くらい)改善しただけでした。

# オンラインジャッジシステムでの処理時間: 約2.8秒
def find_square2(data):
    max_size = 0
    dp = [[0]*len(data[0]) for _ in range(len(data))] # dp用の2次元配列
    # '.'のマスを1に、'*'のマスを0に初期化
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y][x] = 1
                max_size = 1

    # 現在行(curr_row)と一つ上の行(prev_row)のみ必要なので、名前を付けてアクセスできるようにした
    prev_row = dp[0]
    for curr_row in dp[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
                if curr_row[x] > max_size:
                    max_size = curr_row[x]
        prev_row = curr_row
    return max_size

また、dpの宣言を以下のようにarrayのリストに変更してみましたが、速度は改善しませんでした。

dp = [array('I', [0]*len(data[0])) for _ in range(len(data))]

2017-08-28追記
okateimさんにコメントいただいた、配列(リスト)の1次元化を試してみました。
配列を一つだけ確保する方式だと、配列のサイズが大きくなった時の速度ペナルティが厳しいようです。

# サイズ固定、オンラインジャッジシステムでの処理時間: 約4.9秒
def find_square4(data):
    max_size = 0
    dp = [0 for _ in range(1024*1024)]
    # '.'のマスを1に
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*1024+x] = 1

    # 対象のマスから左上に向かって、何マスの正方形が確保できるかチェックする
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*1024+x] == 1:
                dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
                if dp[y*1024+x] > max_size:
                    max_size = dp[y*1024+x]
    return max_size
# サイズ可変、オンラインジャッジシステムでの処理時間: 約5.2秒
def find_square4_2(data):
    max_size = 0
    n = len(data)
    dp = [0 for _ in range(n**2)]
    # '.'のマスを1に
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*n+x] = 1

    # 対象のマスから左上に向かって、何マスの正方形が確保できるかチェックする
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*n+x] == 1:
                dp[y*n+x] = min(dp[(y-1)*n+x-1], dp[(y-1)*n+x], dp[y*n+x-1]) + 1
                if dp[y*n+x] > max_size:
                    max_size = dp[y*n+x]
    return max_size

補足情報(言語/FW/ツール等のバージョンなど)

オンラインのジャッジシステムを使用しているため、pythonのバージョンは3.4.2固定になります。また、NumPyなどの外部ライブラリを使用することはできません。

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

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 1

0

2次元配列が遅いのならば、1次元配列で実装してみてはいかがでしょう。

2次元配列 dp[0..N-1][0..N-1] : (i, j) 要素は dp[i][j] 
1次元配列 dp[0..N*N-1] : (i, j) 要素は dp[i*N+j]

これでも多少は高速化できるかと思います。

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

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

  • ただいまの回答率 90.47%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

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

  • Python

    12265questions

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