優化Kadane的numpy算法

查找最大子數組的標準方法是Kadene's algorithm。如果輸入是大塊狀數組，是否有比本機Python實現更快的速度？優化Kadane的numpy算法

import timeit 

setup = ''' 
import random 
import numpy as np 

def max_subarray(A): 
    max_so_far = max_ending_here = 0 
    for x in A: 
     max_ending_here = max(0, max_ending_here + x) 
     max_so_far  = max(max_so_far, max_ending_here) 
    return max_so_far 

B = np.random.randint(-100,100,size=100000) 
''' 

print min(timeit.Timer('max_subarray(B)',setup=setup).repeat(5, 100))

來源

2014-11-13 Hooked

你說的更好呢？更快？你可以明確地得到比純Python實現更快的速度。您可以使用Cython進行優化，將其寫入純C並通過'ctypes'或'Cython'包含它。 – cel

@cel是的，抱歉，如果我不清楚。更好=>更快。由於numpy數組已經是一種優化的數據類型（例如固定數據類型，連續數組等），我想知道是否有可以利用的（numpy）內置操作。因爲我不熟悉Cython路線，所以我沒有想過。 – Hooked

你只是希望它快速執行還是執行時間複雜度高？簡單地做一個'cumsum'和一個'sort'在numpy中將會非常快，無論:) – Wolph

在IPython的筆記本

小測試與用Cython（因爲沒有timeit，不會出現與%%cython環境:)

原始版本的工作：

import numpy as np 

B = np.random.randint(-100,100,size=100000) 

def max_subarray(A): 
    max_so_far = max_ending_here = 0 
    for x in A: 
     max_ending_here = max(0, max_ending_here + x) 
     max_so_far  = max(max_so_far, max_ending_here) 
    return max_so_far 

import time 

measurements = np.zeros(100, dtype='float') 
for i in range(measurements.size): 
    a = time.time() 
    max_subarray(B) 
    measurements[i] = time.time() - a 

print 'non-c:', measurements.min(), measurements.max(), measurements.mean()

用Cython版本：

%%cython 

import numpy as np 
cimport numpy as np 

B = np.random.randint(-100,100,size=100000) 

DTYPE = np.int 
ctypedef np.int_t DTYPE_t 

cdef DTYPE_t c_max_subarray(np.ndarray A): 
    # Type checking for safety 
    assert A.dtype == DTYPE 

    cdef DTYPE_t max_so_far = 0, max_ending_here = 0, x = 0 
    for x in A: 
     max_ending_here = max(0, max_ending_here + x) 
     max_so_far  = max(max_so_far, max_ending_here) 
    return max_so_far 

import time 

measurements = np.zeros(100, dtype='float') 
for i in range(measurements.size): 
    a = time.time() 
    c_max_subarray(B) 
    measurements[i] = time.time() - a 

print 'Cython:', measurements.min(), measurements.max(), measurements.mean()

結果：

用Cython：0.00420188903809 0.00658392906189 0.00474049091339
非C：0.0485298633575 0.0644249916077 0.0522959709167

絕對是一個顯着的增長沒有太多精力:)

來源

2014-11-14 09:15:47 Wolph

你應該真的靜態類型'x'在這裏。這是循環變量，發生在算術中。我很肯定你會獲得很多速度。 – cel

我得到：'Cython：0.0273659229279 0.0550830364227 0.0315420007706'和'FastCython：0.00628685951233 0.0138258934021 0.00742509126663'，當'x'保證是'int' – cel

@cel對於那些不熟悉Cython的人，你說什麼具體到靜態鍵入x作爲int？在Cython中使用 – Hooked

優化Kadane的numpy算法

回答

相關問題