なぜネイティブのpythonリストのループはnumpyの配列のループより高速です

Question

の高性能Pythonにnumpyを導入し、自分のコンピュータ上でコードを再生する章を読んでいました。誤って私はforループでnumpyのバージョンを実行し、その結果がネイティブのpythonループに比べて驚くほど遅いことがわかりました。

コードの簡略化されたバージョンは、I 1と0の2次元アレイXと別の2次元アレイYを定義した場合、次の、その後繰り返し、概念的X + = Y.

import time 
import numpy as np 

grid_shape = (1024, 1024) 

def simple_loop_comparison(): 
    xmax, ymax = grid_shape 

    py_grid = [[0]*ymax for x in range(xmax)] 
    py_ones = [[1]*ymax for x in range(xmax)] 

    np_grid = np.zeros(grid_shape) 
    np_ones = np.ones(grid_shape) 

    def add_with_loop(grid, add_grid, xmax, ymax): 
     for x in range(xmax): 
      for y in range(ymax): 
       grid[x][y] += add_grid[x][y] 

    repeat = 20 
    start = time.time() 
    for i in range(repeat): 
     # native python: loop over 2D array 
     add_with_loop(py_grid, py_ones, xmax, ymax) 
    print('for loop with native list=', time.time()-start) 

    start = time.time() 
    for i in range(repeat): 
     # numpy: loop over 2D array 
     add_with_loop(np_grid, np_ones, xmax, ymax) 
    print('for loop with numpy array=', time.time()-start) 

    start = time.time() 
    for i in range(repeat): 
     # vectorized numpy operation 
     np_grid += np_ones 
    print('numpy vectorization=', time.time()-start) 

if __name__ == "__main__": 
    simple_loop_comparison() 

XにYを追加した通りでありますその結果がどのように見える

：

# when repeat=10 
for loop with native list= 2.545672655105591 
for loop with numpy array= 11.622980833053589 
numpy vectorization= 0.020279645919799805 

# when repeat=20 
for loop with native list= 5.195128440856934 
for loop with numpy array= 23.241904258728027 
numpy vectorization= 0.04613637924194336 

私は完全にnumpyのベクトル化操作は、他の2つを凌駕することを期待するが、私はネイティブのPythonのリストよりも大幅に遅いnumpyの配列の結果についてのforループを使用していることを見て驚きました。私の理解では、キャッシュは少なくともnumpyの配列で十分に満たされていなければならず、たとえforループであっても、ベクトル化なしでリストを上回るはずです。

numpyについて、またはCPU /キャッシュ/メモリが低レベルでどのように動作するのか分かりませんでしたか？どうもありがとうございました。

EDIT：変更タイトル

Answer 1

アンさらに簡単なケース - 配列対リストにリスト内包：

In [119]: x = list(range(1000000)) 
In [120]: timeit [i for i in x] 
47.4 ms ± 634 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 

In [121]: arr = np.array(x) 
In [122]: timeit [i for i in arr] 
131 ms ± 3.69 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

リストは、他のメモリ内のオブジェクトへのポインタを含むデータ・バッファを持っています。だから、反復またはリストのインデックスを作成するには、単にそのポインタを検索し、オブジェクトを取得する必要があります。

In [123]: type(x[1000]) 
Out[123]: int 

配列は、バイトとして、DataBufferのその要素を格納します。要素を取得するには、それらのバイトを（高速で）見つけ出し、numpyオブジェクトにラップする必要があります（dtypeによる）。そのようなオブジェクトは0d単一要素配列（同じ属性の多くを持つ）と似ています。

In [124]: type(arr[1000]) 
Out[124]: numpy.int32 

この索引付けは数値をフェッチするだけではなく、再作成します。

多くの場合、オブジェクトdtype配列は、拡張リストまたは劣化リストとして記述されます。リストのように、それはメモリ内の他の場所へのオブジェクトへのポインタを含んでいますが、それはappendでは成長できません。私たちはしばしば、数値配列の利点の多くを失うと言います。しかし、その反復速度は他の二つの間にある：

In [125]: arrO = np.array(x, dtype=object) 
In [127]: type(arrO[1000]) 
Out[127]: int 
In [128]: timeit [i for i in arrO] 
74.5 ms ± 1.42 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

をとにかく、私はあなたが反復しなければならない場合は、リストに固執することを、他のSOの回答で見てきました。リストから始めると、リストに固執するほうが速いことがよくあります。 numpy vectorの速度は速いが、配列の作成には時間がかかるため、時間を節約できます。

それは（コンパイルnumpyのコードで）最初からそのようなアレイを作成するために必要な時間と、このリストから配列を作成するのにかかる時間を比較：これは `numpy`ループない

In [129]: timeit np.array(x) 
109 ms ± 1.97 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 
In [130]: timeit np.arange(len(x)) 
1.77 ms ± 31.6 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each) 

Answer 2

彼らはデータポインタにnumpyのを求めに関与変換、それらのポインタ位置で値を取得して、反復するためにそれらを使用しているしているので。 Pythonのリストには、これらのステップの数が少なくなっています。ナンシー速度の向上は、ベクトル、行列の計算を繰り返したり内部的に実行したり、返り値と答えを返すことができたり、一連の回答を指すことができる場合にのみ注目されます。