대용량 행렬 생성/조작을위한 효율적인 Cython

Question

매우 큰 데이터 행렬 (약 15,000 x 15,000; 유형 double)을 생성하고 조작하는 코드 섹션의 속도를 높이려고 노력했습니다. 지금은 매트릭스의 크기가 중요하지 않다고 생각합니다. 작은 10x10 매트릭스에서도 속도가 향상되지 않기 때문입니다. 사실 컴파일 된 Cython 코드는 작은 행렬에 대해서는 순수 파이썬보다 느린 반면, 큰 행렬에 대해서는 cython과 python 사이에서 거의 동일합니다). 필자가 일주일 동안 Python을 코딩하고 (새로 Matlab에서 변환 한) 겸손한 화학 엔지니어 일뿐입니다.

[ 16.66 16.85 16.93 16.98 17.08 17.03 17.09 16.76 16.67 16.72] 

출력으로서 매트릭스 (높이 L, 폭 L-1)을 제조 :

코드의 목적은 예를 들어, 입력으로 1D 배열 (길이 L)을 취한다

[[ 16.66 16.85 16.93 16.98 17.08 17.03 17.09 16.76 16.67] 
[ 16.85 16.93 16.98 17.08 17.03 17.09 16.76 16.67 16.72] 
[ 16.93 16.98 17.08 17.03 17.09 16.76 16.67 16.72 0. ] 
[ 16.98 17.08 17.03 17.09 16.76 16.67 16.72 0.  0. ] 
[ 17.08 17.03 17.09 16.76 16.67 16.72 0.  0.  0. ] 
[ 17.03 17.09 16.76 16.67 16.72 0.  0.  0.  0. ] 
[ 17.09 16.76 16.67 16.72 0.  0.  0.  0.  0. ] 
[ 16.76 16.67 16.72 0.  0.  0.  0.  0.  0. ] 
[ 16.67 16.72 0.  0.  0.  0.  0.  0.  0. ] 
[ 16.72 0.  0.  0.  0.  0.  0.  0.  0. ]] 

위의 예제와 아래 코드에서 분명히 밝히기를 바랍니다. 알고리즘은 매우 큰 행렬로 확장해야하는데, 현재는 오류없이 수행됩니다. 속도가 느립니다! 대단히 감사하겠습니다

from scipy.sparse import spdiags 
import numpy as np 
cimport numpy as np 
cimport cython 

DTYPE = np.float 
ctypedef np.float_t DTYPE_t 

@cython.boundscheck(False) 
@cython.wraparound(False) 
def sfmat(np.ndarray[DTYPE_t, ndim=1] data): 
    assert data.dtype == DTYPE 
    cdef int h = data.shape[0] 
    cdef np.ndarray[DTYPE_t, ndim=2] m = np.zeros([h, h-1], dtype=DTYPE) 
    cdef np.ndarray[DTYPE_t, ndim=2] s1 = np.zeros([h, h-1], dtype=DTYPE) 
    cdef np.ndarray[DTYPE_t, ndim=2] s2 = np.zeros([h, h-1], dtype=DTYPE) 
    cdef np.ndarray[DTYPE_t, ndim=2] s3 = np.zeros([h, h-1], dtype=DTYPE) 

    s1 = np.tile(data,[h-1,1]).T 
    s2 = np.tril(s1,0) 
    s3 = spdiags(s2,range(1-h,1), h, h-1).todense() 
    m = np.flipud(s3) 
    return m 

사이 썬의 된 구현에 어떤 도움을 : 나는 또한 읽을 더 명확 수 있습니다 더 자세한 코드를 시도

from scipy.sparse import spdiags 
import numpy as np 
cimport numpy as np 
cimport cython 

@cython.boundscheck(False) 
@cython.wraparound(False) 
def sfmat(np.ndarray[double, ndim=1] data): 
    cdef int h = data.shape[0] 
    cdef np.ndarray[double, ndim=2] m = np.zeros([h, h-1]) 
    m = np.flipud(spdiags(np.tril(np.tile(data,[h-1,1]).T,0),range(1-h,1), h, h-1).todense()) 
    return m 

: 여기

내 사이 썬 코드 . 이 알고리즘의 속도를 높이는 다른 방법이 있다면 도움이 될 것입니다. 도움 주셔서 감사합니다!

나는 이것에 익숙하지 않기 때문에 여기에 더 많은 세부 사항이 있습니다. 64 비트 Windows 7 Pro를 실행하고 있고 Windows SDK C/C++ 컴파일러를 사용하여 cython 코드를 successfuly로 컴파일하고 있습니다. (나는 성공적으로 github here에 대한 지침을 따랐다.) 간단한 "hello world"cython 예제는 잘 컴파일되고 64 비트 모드에서 잘 실행되며 위의 코드는 오류없이 컴파일되고 실행됩니다. 전체 15,000 x 15,000 행렬을 조작하려면 64 비트 아키텍처가 필요합니다. 그렇지 않으면 적어도 32 비트 용으로 컴파일 한 후 코드를 실행하면 메모리 오류가 발생했기 때문에 그렇게 믿습니다. 이 질문에 대해서는 행렬을 작은 덩어리로 분해 할 수 없다고 가정하십시오. 이 질문에 답하는 데 필요한 다른 정보가 있으면 알려주십시오. 내가 루프를 피하는 가장 좋은 방법이 될 것이라고 생각

건배, scientistR

UPDATE는, 그러나, spdiags

의 주요 병목이다. 따라서 새 알고리즘이 더 잘 작동합니다 (내 컴퓨터에서 4 배 향상).

import numpy as np 
cimport numpy as np 
cimport cython 

@cython.boundscheck(False) 
@cython.wraparound(False) 
def sfmat(np.ndarray[double, ndim=1] data): 
    cdef int i 
    cdef np.ndarray[double, ndim=2] m = np.zeros([data.shape[0], data.shape[0]-1]) 
    for i in range(data.shape[0]-1): 
     m[:,i] = np.roll(data,-i); 
    return m 

그러나 Cython은 순수 Python에 비해 향상된 기능을 제공하지 않습니다. 도와주세요. 주석가들이 지적했듯이 알고리즘을 최적화하는 것 외에도이를 개선 할 방법이 없을 수도 있지만 희망적입니다. 감사! 또한, 더 빠른 알고리즘, cython 또는 파이썬이 있습니까?

Answer 1

다소 오래된 질문 일 수 있지만 답변을 남기지 않은 채 :)으로 남겨 두어야합니다. 나는 간단하게 for-loops (실제로 Cython에서 빠름)를 사용하여 Cython 코드를 약 8 배 빠르게 할 수 있었고 배열 크기는 7000이었습니다.np.roll을 사용한 구현은 원하는 배열 (!)을 생성하지 않지만 그 함수를 사용하여 타이밍을 비교하는 방법에 유의하십시오.

def sfmat(data): 
    n = len(data) 
    out = np.empty((n, n-1)) 
    out[0, :] = data[:n-1] 
    for i in xrange(1, n): 
     out[i, :n-i] = data[i:] 
     out[i, n-i:] = 0 
    return out 

:

편집 형식화 된 Memoryviews를 사용하는 코드와 np.empty 대신 np.zeros

def sfmat(double[:] data): 
    cdef int n = data.shape[0] 
    cdef np.ndarray[double, ndim=2] out = np.empty((n, n-1)) 
    cdef double [:, :] out_v = out # "typed memoryview" 

    cdef int i, j 
    for i in range(n-1): 
     out_v[0, i] = data[i] 

    for i in range(1, n): 
     for j in range(n-i): 
      out_v[i, j] = data[i+j] 
     for j in range(n-i, n-1): 
      out_v[i, j] = 0. 
    return out 

불행하게도, 사이 썬의 노력은 단지 ~ 1.2 배 빠른 일반 파이썬 세션에서 다음 코드를 실행보다

그러나 주석에서 이미 논의한 것처럼,이 방법으로 원래의 아주 작은 행렬을 날려 버리는 것이 실제, 전반적인 문제를 해결하는 가장 효율적인 방법은 아닐 것입니다 어쨌든 문제. 처음에 할 일이 for-loops를 사용하지 않으려한다면 Cython에서 그렇게 할 필요가 없습니다!

Answer 2

나는 순진하다고 생각하지는 않지만, C, C++ 및 Python이 "행 주요 언어"라는 것을 알고 있습니다. 맞습니까? Matlab (및 Fortran)은 "열 - 전공"입니다. 나는 당신이 이미 i과 j을 뒤집어 썼다 고 확신하지만, 아무도 그 시도를 생각하지 않을 경우를 대비해 언급하고 싶었습니다.