paiza 3次元データの計算量に関してわからないこと

Question

https://paiza.jp/works/mondai/sequence_search_problems_advanced/sequence_search_problems_advanced__matrix_step4

こちらの問題に関しての質問です
答えのコードをまずはらせていただきます。
python3で実装しました。

n, m, h, x = map(int, input().split())

lis = [[[int(x) for x in input().split()] for _ in range(n)] for _ in range(h)]

ans: int = 0

for i in range(h):
    for j in range(n):
        for s in range(m):
            if lis[i][j][s] == x:
                ans += 1
                
print(ans)

質問です。
for の中のhとnとmの順番を入れ替えて答えとして提出すると
ランタイムエラーとなってしまいます。どうしてなのでしょうか？

h * n * mの計算量は変わらず、最後まで実装されるため変数の順番をかえただけで
実行速度がかわってしまうことについて理解できませんでした。
よろしくお願いいたします

Comments

[TakaiY]

よくわかりませんが、「ランタイムエラー」って時間がかかっているからではなく、バグがあるから発生するのではないのでしょうか？
h, n, mを入れかえたもので、手元で動作しますか？ 特に、h, n, mの値の違うもの。

[meg_]

> for の中のhとnとmの順番を入れ替えて答えとして提出すると
具体的に何を何に変えましたか？

[tou.23.bc]

処理時間の画像を追加いたしました。
m,n,,hのじゅんでプログラムを書きました。

[tou.23.bc]

＞
h, n, mを入れかえたもので、手元で動作しますか？ 特に、h, n, mの値の違うもの。

コメントありがとうございます。これから手元でも実装してみます。

[TakaiY]

h,n,m を入れかえて、「ランタイムエラーになった」コードも提示いただけると原因がわかると思います。

[bsdfan]

ランタイムエラーが発生した分の時間が長くなっているだけではないでしょうか。
0.18秒とかは制限時間に引っかかるような長さではないかと。

Answer 1

例えば下記コードはIndexErrorとなります。

for i in range(n):
    for j in range(m):
        for s in range(h):
            if lis[i][j][s] == x:
                ans += 1

質問のコードを実行するとlisは[[[1, 1, 1], [1, 1, 1]], [[2, 2, 2], [2, 2, 2]], [[3, 3, 3], [3, 3, 3]]]となります。他の変数はn=2, m=3, h=3, x=2となります。
ですのでiが3以上、jが2以上、sが3以上になるときにエラーになります。
上記例ですとmが3なのでjが2になったときにエラーが発生します。

【追記】入力データを書き忘れていました。

2 3 3 2
1 1 1
1 1 1
2 2 2
2 2 2
3 3 3
3 3 3

Comments

[tou.23.bc]

理解することができました。ありがとうございます

Answer 2

ランタイムエラーは、時間がかかり過ぎたからでしょう。
現代のCPUではメモリは連続で触っていくと速いですが、ランダムに触ると遅いです。CPUキャッシュの効き具合とか。DRAMの読み込み単位とかの制約です。

sのループを回っている間はlis[i][j]部は固定でき、[s]は連続アクセスですが、sとiを入れ替えたとしたらiのループを回るたび[i],[j],[s]を参照してまわる必要があるうえ最終的なアドレスもバラバラになるのでテキメンに遅くなるでしょう

Comments

[TakaiY]

pythonの多次元リストの中のデータがメモリ上に整列しているとは思わないのですが、インデックスの変更順で速度が変ったりするのでしょうか？

[tou.23.bc]

回答いただきありがとうございます。
ないようが難しく理解することができませんでした。。