카디 네의 알고리즘 최적화하기

Question

최대 부분 배열을 찾는 표준 방법은 Kadene's algorithm입니다. 입력이 큰 숫자 배열 인 경우 원시 파이썬 구현보다 빠릅니다.

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 노트북의 사이 썬과

리틀 시험 (그 중 어떤 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 

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

결과 :

,451,515,

• 사이 썬 : 0.00420188903809 0.00658392906189 0.00474049091339
• 아닌 C : 0.0485298633575 0.0644249916077 0.0522959709167

확실히 너무 많은 노력 :)