Python3: listよりnumpy.ndarrayのほうが処理が遅くなることもあるのかどうか

Question

具体的なコードの質問というよりは抽象的な質問です。

・要約した質問
Pythonで「listよりnumpy.ndarrayのほうが処理が速い」というのは、必ずしもそうだとも言えないのか。

・質問とその背景
Pythonで数独パズルを解くプログラムを書きました。問題の盤面を9×9のリスト形式（下コードのような形）で与えると、それについて解いてくれるものです。

#問題の例
#0は空白マスを表す
sudoku_problem = [[0,0,5,3,0,0,0,0,0],
                  [8,0,0,0,0,0,0,2,0],
                  [0,7,0,0,1,0,5,0,0],
                  [4,0,0,0,0,5,3,0,0],
                  [0,1,0,0,7,0,0,0,6],
                  [0,0,3,2,0,0,0,8,0],
                  [0,6,0,5,0,0,0,0,9],
                  [0,0,4,0,0,0,0,3,0],
                  [0,0,0,0,0,9,7,0,0]]
#「世界一難しい数独」で調べると出てくる問題です。

上記の問題だと約1.5秒で解いてくれます。

ひとまずプログラムが完成したので、次はこれを高速化しようとしました。
完成したプログラムではpythonのリストオブジェクトを多用しているのですが、「pythonのリストの操作は処理が遅い、データ型の決まっているnumpy.ndarrayを使ったほうが高速」のような話を聞いていたので、プログラムの内問題の盤面とそれに関する処理をすべてnumpy.ndarrayの形式に書き換えました。

#問題の入力形式をnumpy.ndarrayに変えた
import numpy as np
sudoku_problem = np.array([[0,0,5,3,0,0,0,0,0],
                           [8,0,0,0,0,0,0,2,0],
                           [0,7,0,0,1,0,5,0,0],
                           [4,0,0,0,0,5,3,0,0],
                           [0,1,0,0,7,0,0,0,6],
                           [0,0,3,2,0,0,0,8,0],
                           [0,6,0,5,0,0,0,0,9],
                           [0,0,4,0,0,0,0,3,0],
                           [0,0,0,0,0,9,7,0,0]], dtype='int8')

しかし、そうしてできたプログラムを実行してみると、処理にかかる時間が元のプログラムより30倍ほど長くなってしまいました。
もともとのプログラムがfor文をガンガン回す感じもので、その構造については変更後もほぼかえていないので「あんまり早くならないかもな」ぐらいに思っていたのですが、
numpy.ndarrayの処理は普通のリストより早くなるものだと思っていたので大幅に遅くなったことが意外でした。

例えば行列計算なんかの処理をガンガンやる場合には、numpyを使うとデータ型は固定だしfor文をあまり書かなくて済むので高速になる、というのは多分あってると思うのですが、
そういう処理をやらない場合、numpyは単なるlist型の上位互換としては見ないほうがいいということでしょうか。

ぼんやりした質問で申し訳ないですがどなたか意見をくださると幸いです。

Answer 1

普通にpythonレイヤからnumpy配列の「要素」にアクセスするような処理をすると、オーバーヘッドの塊みたいなものですから遅いでしょうねえ。

import timeit
import numpy as np

n = 2
L = [[0 for _ in range(10**n)] for _ in range(10**n)]
A = np.array(L)

def func1(a):
    for i in range(10**n):
        for j in range(10**n):
            a[i][j]

def func2(a):
    for i in range(10**n):
        for j in range(10**n):
            a[i,j]

print(timeit.timeit(lambda :func1(L), number=100))
print(timeit.timeit(lambda :func1(A), number=100))
print(timeit.timeit(lambda :func2(A), number=100))
""" =>
0.0637162079801783
0.2254948549962137
0.14580219899653457
"""

実装についていえば、numpy配列は、C配列のwrapperみたいなものです。要素の取り出しはメモリ上のデータに対応する値を持つpythonオブジェクトを生成して返しますし、代入はその逆（pythonオブジェクトをデータに変換して書き込む）です。listはそんなまどころっこしいことはしていなくて、要素はただのpythonオブジェクトへのポインタです。