AOJ ALDS1_2_Dについて(Python)

前提・実現したいこと

PythonでAOJのALDS1_2_D(シェルソート)の問題にて下のコードを提出したところ、Runtimeエラーと表示されました。また、実行結果を見たところ34件のテストケースの内32件目までは正常に実行されており、33件目でRuntimeエラーを起こしていました。
エラーは入力データの増加によるものなのかと考えましたがはっきりせず、対処法も思いつきません。どなたかご教授いただけないでしょうか。

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

Judge Input #33でのRuntime Error

該当のソースコード

python
1n, gap = int(input()), []
2data = list(map(int, [input() for i in range(n)]))
3cnt, g = 0, 0
4while g <= n//9:
5    g = 3 * g + 1
6    gap.append(g)
7m = len(gap)
8gap = gap[::-1]
9for i in gap:
10    for idx in range(i, n):
11        j = idx - i
12        while j >= 0 and data[j] > data[j+i]:
13            data[j+i], data[j] = data[j], data[j+i]
14            j -= i
15            cnt += 1
16print(m)
17print(" ".join(map(str, gap)))
18print(cnt)
19for i in range(n):
20    print(data[i])

試したこと

数回提出しましたが、同じケースでRuntime Errorとなってしまいます

補足情報（FW/ツールのバージョンなど）

当該問題のURLです
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_D

行動規範の内容に同意します

回答1件

ベストアンサー

RuntimeErrorなので時間が超過してエラーになっています。
もっとコードを高速化する必要があることを意味しています。

まずここですが、ループ内で2回代入します。

python
1j = idx - i
2while j >= 0 and data[j] > data[j+i]:
3    data[j+i], data[j] = data[j], data[j+i]
4    j -= i
5    cnt += 1

一方で概念コードではループ内で1回しか代入しません。

insertionSort(A, n, g)
    for i = g to n-1
    v = A[i]
    j = i - g
    while j >= 0 && A[j] > v
        A[j+g] = A[j]
        j = j - g
        cnt++
    A[j+g] = v

最後のcnt回だけ代入が多いです。

これで5秒短縮。

次に、入力サイズが果てしない場合、Pythonは読み込みでボトルネックが来ます。

python
1data = list(map(int, [input() for i in range(n)]))

よりも

python
1import sys
2data = [int(l) for l in sys.stdin.readlines()]

の方がずっと速いです。

これで4秒短縮。

そして最後に、
https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function
関数のほうが実行速度が速いです。

つまり、

python
1for g in gap[::-1]:
2    c = 0
3    for idx in range(g, n):
4        v = data[idx]
5        j = idx - g
6        while j >= 0 and data[j] > v:
7            data[j+g] = data[j]
8            j -= g
9            c += 1
10        data[j+g] = v
11    cnt += c

よりも

python
1def f(data, g, n):
2    c = 0
3    for idx in range(g, n):
4        v = data[idx]
5        j = idx - g
6        while j >= 0 and data[j] > v:
7            data[j+g] = data[j]
8            j -= g
9            c += 1
10        data[j+g] = v
11    return c
12
13for g in gap[::-1]:
14    cnt += f(data, g, n)