Wie wird die Geschwindigkeit in Schleifen in Cython verbessert?

Question

Ich habe ein Projekt in Python gestartet, das meist aus Loops besteht. Vor ein paar Tagen habe ich über Cython gelesen, das Ihnen hilft, schneller Code durch statische Eingabe zu bekommen. entwickelte ich diese beiden Funktionen, um die Leistung zu überprüfen (ein in Python ist und die andere in cython):

import numpy as np 
from time import clock 

size = 11 
board = np.random.randint(2, size=(size, size)) 

def py_playout(board, N): 
    black_rave = [] 
    white_rave = [] 
    for i in range(N): 
     for x in range(board.shape[0]): 
      for y in range(board.shape[1]): 
       if board[(x,y)] == 0: 
        black_rave.append((x,y)) 
       else: 
        white_rave.append((x,y)) 
    return black_rave, white_rave 

cdef cy_playout(board, int N): 
    cdef list white_rave = [], black_rave = [] 
    cdef int M = board.shape[0], L = board.shape[1] 
    cdef int i=0, x=0, y=0 
    for i in range(N): 
     for x in range(M): 
      for y in range(L): 
       if board[(x,y)] == 0: 
        black_rave.append((x,y)) 
       else: 
        white_rave.append((x,y)) 
    return black_rave, white_rave 

ich den Code verwendet, nachdem die gleiche Performance zu testen:

t1 = clock() 
a = playout(board, 1000) 
t2 = clock() 
b = playout1(board, 1000) 
t3 = clock() 

py = t2 - t1 
cy = t3 - t2 
print('cy is %a times better than py'% str(py/cy)) 

ich jedoch habe keine spürbaren Verbesserungen gefunden. Ich habe noch nicht Typed-Memoryviews verwendet. Kann jemand eine nützliche Lösung vorschlagen, um die Geschwindigkeit zu verbessern oder mir helfen, den Code mit typed-memoryview neu zu schreiben?

Answer 1

Du hast Recht, einen Typ der board Parameter in der cython Funktion ohne Zugabe von der Beschleunigung nicht so viel ist:

%timeit py_playout(board, 1000) 
# 321 ms ± 19.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each) 
%timeit cy_playout(board, 1000) 
# 186 ms ± 541 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 

Aber es ist immer noch ein Faktor zwei schneller. Durch Hinzufügen eines Typs, z.

cdef cy_playout(int[:, :] board, int N): 
    # ... 

# or if you want explicit types: 
# cimport numpy as np 
# cdef cy_playout(np.int64_t[:, :] board, int N): # or np.int32_t 

Es ist viel schneller (fast 10 mal schneller):

%timeit cy_playout(board, 1000) 
# 38.7 ms ± 1.84 ms per loop (mean ± std. dev. of 7 runs, 10 loops each) 

habe ich auch timeit (okay die IPython Magie %timeit) genauere Timings zu erhalten.

---

Beachten Sie, dass Sie auch numba können große speedups ohne zusätzliche statische Typisierung zu erreichen:

import numba as nb 

nb_playout = nb.njit(py_playout) # Just decorated your python function 

%timeit nb_playout(board, 1000) 
# 37.5 ms ± 154 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 

Answer 2

implementiert ich eine Funktion, die noch schneller läuft. Ich erklärte einfach black_rave und white_rave als memoryviews und sich im Rückgabewert setzen:

cdef tuple cy_playout1(int[:, :] board, int N): 
    cell_size = int((size ** 2)/2) + 10 
    cdef int[:, :] black_rave = np.empty([cell_size, 2], dtype=np.int32) 
    cdef int[:, :] white_rave = np.empty([cell_size, 2], dtype=np.int32) 

    cdef int i, j, x, y, h 
    i, j = 0, 0 
    cdef int M,L 
    M = board.shape[0] 
    L = board.shape[1] 
    for h in range(N): 
     for x in range(M): 
      for y in range(L): 
       if board[x,y] == 0: 
        black_rave[i][0], black_rave[i][1] = x, y 
        i += 1 
       elif board[x,y] == 1: 
        white_rave[j][0], white_rave[j][1] = x, y 
        j += 1 
     i = 0 
     j = 0 

    return black_rave[:i], white_rave[:j] 

Das die Geschwindigkeit Testergebnisse:

%timeit py_playout(board, 1000) 
%timeit cy_playout(board, 1000) 
%timeit cy_playout1(board, 1000) 
# 1 loop, best of 3: 200 ms per loop 
# 100 loops, best of 3: 9.26 ms per loop 
# 100 loops, best of 3: 4.88 ms per loop