python - 优化 flood-fill alike 算法(渗透理论)

Question

这是我的 python 代码:

from numpy import *
from copy import *

def Grid(s, p):
    return random.binomial(1, p, (s,s))

def InitialSpill(G, i, j):
    G[i, j] = 2

def Fillable(G, i, j):
    if i > 0 and G[i - 1, j] == 2:
            return True
    if j > 0 and G[i, j - 1] == 2:
            return True
    if i < len(G) - 1 and G[i + 1, j] == 2:
            return True
    if j < len(G) - 1 and G[i, j + 1] == 2:
            return True
    return False

def Fill(G):
    F = copy(G)
    for i in range(len(G)):
        for j in range(len(G)):
            if F[i, j] == 2:
                G[i, j] = 3 # 3 denote a "dry" cell
            elif F[i, j] == 1 and Fillable(F, i, j):
                G[i, j] = 2 # 2 denote a "filled" cell

def EndReached(G): # Check if all filled cells are dry and if no cells are fillable
    for i in range(len(G)):
        for j in range(len(G)):
            if (G[i, j] == 1 and Fillable(G, i, j)) or G[i, j] == 2:
                    return False
    return True

def Prop(G): # yield the ratio between dry and total fillable cells
    (dry, unrch) = (0, 0)
    for e in G:
        for r in e:
            if r == 1:
                unrch += 1
            if r == 3:
                dry += 1
    if unrch == 0 and dry < 2:
        return 0
    return dry / (unrch + dry)

def Percolate(s, p, i, j): #Percolate a generated matrix of size n, probability p
    G = Grid(s, p)
    InitialSpill(G, i, j)
    while not EndReached(G):
        Fill(G)
    return Prop(G)

def PercList(s, i, j, n, l):
    list_p = linspace(0, 1, n)
    list_perc = []
    for p in list_p:
        sum = 0
        for i in range(l):
            sum += Percolate(s, p, i, j)
        list_perc += [sum/l]
    return (list_p, list_perc)

这个想法是用矩阵表示一个可渗流场，其中:

• 0 是一个完整的、不可填充的单元格
• 1 是一个空的、可填充的单元格
• 2 是一个填充的单元格(将变干 => 3)
• 3 是干电池(已充满，因此无法充满)

我想将干细胞/总可填充细胞的比率表示为 p(矩阵中细胞充满的概率)的函数。

但是，我的代码效率极低(需要很多时间才能完成，即使是小值)。

如何优化它？

Answer 1

此代码效率不高，因为当您使用 numpy 时，大部分计算都是按元素完成的(二维数组元素上的双循环等)，这在 Python 中很慢。

有两种可能的方法来加快速度，

1. 您对代码进行矢量化处理，使其对数组使用优化的 numpy 运算符。例如，不是使用返回 bool 值的函数 Fillable(G, i, j)，而是定义返回 bool 值 numpy 数组的函数 Fillable(G)一次所有的 i, j 索引(不使用循环)，

   def Fillable(G):
        res = np.zeros(G.shape, dtype='bool')
        # if i > 0 and G[i - 1, j] == 2:
        # find indices where this is true
        imask, jmask = np.where(G == 2)
        imask, jmask = imask.copy(), jmask.copy() # make them writable
        imask -= 1   # shift i indices
        imask, jmask = imask[imask>=0], jmask[jmask>=0]
        res[imask, jmask] = True
        # [..] do the other conditions in a similar way
        return res
   

   这样我们就可以从 Fill(G) 函数中移除双循环，例如，

   def Fill(G):
       G[G==2] = 3
       G[(G==1) & Fillable(G)] = 2
   

   几乎大部分代码都可以用类似的方式重写。

2. 另一种选择是使用 Cython .在这种情况下，代码结构可以保持不变，只需添加类型就可以显着加快速度。例如，Cython 的优化函数 Fill 将是，

   cpdef int Fill(int [:,::1] G):
       cdef int [:,::1] F = G.base.copy()
       cdef int i, j, N
       N = G.base.shape[0]
       for i in range(N):
           for j in range(N):
               if F[i, j] == 2:
                   G[i, j] = 3 
               elif F[i, j] == 1 and Fillable(F, i, j):
                   G[i, j] = 2 
       return 0
   

无论如何，你应该先profile your code , 查看哪些函数调用花费的时间最多。有可能只优化一个或两个关键函数就可以将速度提高一个数量级。