python3を使用してAOJ(Aizu Online Judge)のITP1に挑戦した際にひっかかったこと

python

Runtime Errorが発生する

  • 現象

ローカル環境ではそれらしく動いていたのに、判定にかけると最初のテストから失敗する。結果は「Wrong Answer」ですらなく、プログラムが全く動作していないように見える。

  • 原因

入力データの受け取り方が間違っている。たとえば、'AA'のような文字が入力されているのに int(input())で整数に変換しようとしている。

  • 対策

プログラムを見直す

ローカル環境では正常に動くのに、ジャッジではRuntime Errorが発生する

  • 現象

ローカル環境では正常に動くのに、評価するとRuntime Errorが発生する

  • 原因

AOJのpython実行環境(3.4.2)にない機能を使用しようとしている。

例: math.gcd(), math.inf, collections.deque.index() はpython3.5以降で使用可能。

  • 対策 プログラムを見直す

pycharmのデバッガが起動しない。

  • 現象

プログラムをデバッグしようとすると、「AttributeError: module 'queue' has no attribute 'Queue'」というエラーが発生する。

  • 原因

作成したプログラムのファイル名がpython標準モジュールの名前と重複している。 stackoverflow.com

  • 対策 自分の作成したプログラムの名前を変える。

リストのループが意図した通りに動かない

  • 現象 繰り返し処理する必要があるプログラムで、一度目は正常に動作するが、二度目以降は失敗する。

  • 原因

distance = map(lambda x, y:abs(x - y), data_x, data_y)

のようにmap()を使用すると、python3.xではdistanceはイテレータになる。 なので、一度読み尽してしまうとそれっきりになってしまう。

  • 対策

リスト化する

distance = list(map(lambda x, y:abs(x - y), data_x, data_y))

数列の処理が遅い

  • 現象

AOJのジャッジで、あと一歩のところで「Time Limit Exceeded」になった。少しでも処理を早くするためにリストをarrayに変更したら、かえって時間がかかるようになった。

  • 原因

不明。マージソートのプログラムで、以下のようにリストのままとarray化したもので処理速度を比較した場合、リストのままの方が速い。array化のオーバーヘッドのため?

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)


def merge(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = A[left:mid]
    R = A[mid:right]
    L.append(1000000001)
    R.append(1000000001)
    i = 0  # L[]用のインデックス
    j = 0  # R[]用のインデックス
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


from array import array
def merge_with_array(A, left, mid, right):
    global Comp_count
    n1 = mid - left
    n2 = right - mid
    L = array('I', A[left:mid])
    R = array('I', A[mid:right])
    L.append(1000000001)
    R.append(1000000001)
    i = 0  # L[]用のインデックス
    j = 0  # R[]用のインデックス
    for k in range(left, right):
        Comp_count += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1
  • 対策

array型の方が「効率が良い」と言われているのはメモリ効率のことで、速度効率のことではない?当面は、プロファイリングしながら両方とも試してみる。

ネスティングしたリストから値だけを取り出したい

  • 現象

再帰関数からリストで結果を返すようにしたら、[[[2], 1, [3]], 0, [[[6], 5, [7]], 4, [8]]] のように複雑にネスティングした結果になってしまった。これを [2 1 3 0 6 5 7 4 8] のようにスッキリしたリストに整形したい。

  • 原因

再帰呼び出しを行なう関数からリストでreturnしているのがそもそもの敗因。でもせっかく作ったのでできればそのまま利用したい。

  • 対策

この手の処理は、flatten, フラット化と呼ばれている。検索するといろいろと出てくるので、処理速度、可読性、汎用性などの点からから好みの方法で処理する。 stackoverflow.com