优化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算法

回答

相关问题