python - 优化 Kadane 的 numpy 算法

Question

寻找最大子数组的标准方法是Kadene's algorithm .如果输入是一个large numpy array，有什么比原生python实现更快的吗？

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))

Answer 1

在 iPython notebook 中使用 Cython 进行的小测试(因为没有时间，似乎不适用于 %%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()

结果:

• 赛通:0.00420188903809 0.00658392906189 0.00474049091339
• 非 c:0.0485298633575 0.0644249916077 0.0522959709167

绝对是一个显着的增长，没有太多的努力:)