일정 시간에 행렬을 "나누기"

Question

Strassen의 알고리즘을 C++에서 행렬 곱셈을 구현하려고하는데 두 행렬을 각각 4 개의 부분으로 나누는 방법을 찾고 싶습니다. 여기에 내가 그렇게하고있는 현재의 방법입니다

for(int i = 0; i < n; i++){ 
    for(int j = 0; j < n; j++){ 
     A11[i][j] = a[i][j]; 
     A12[i][j] = a[i][j+n]; 
     A21[i][j] = a[i+n][j]; 
     A22[i][j] = a[i+n][j+n]; 
     B11[i][j] = b[i][j]; 
     B12[i][j] = b[i][j+n]; 
     B21[i][j] = b[i+n][j]; 
     B22[i][j] = b[i+n][j+n]; 
    } 
} 

이 방법 (N^2) 분명히 O이고, 그리고이 각 재귀 호출됩니다로는 런타임에 N^2 * 로그 (N)을 추가 요구.

일정한 시간에이를 수행하는 방법은 값을 복사하는 대신 4 개의 하위 행렬에 대한 포인터를 만드는 것이지만 포인터를 만드는 방법을 찾는 데 어려움을 겪고 있습니다. 어떤 도움을 주시면 감사하겠습니다.

Answer 1

매트릭스를 생각하지 마십시오. 매트릭스보기를 생각해보십시오.

매트릭스보기에는 T 버퍼의 포인터, 너비, 높이, 오프셋 및 열 (또는 행) 사이의 보폭이 있습니다.

배열보기 유형으로 시작할 수 있습니다.

template<class T> 
struct array_view { 
    T* b = 0; T* e = 0; 
    T* begin() const{ return b; } 
    T* end() const{ return e; } 

    array_view(T* s, T* f):b(s), e(f) {} 
    array_view(T* s, std::size_t l):array_view(s, s+l) {} 

    std::size_t size() const { return end()-begin(); } 
    T& operator[](std::size_t n) const { return *(begin()+n); } 
    array_view slice(std::size_t start, std::size_t length) const { 
    start = (std::min)(start, size()); 
    length = (std::min)(size()-start, length); 
    return {b+start, length}; 
    } 
}; 

이제 우리의 매트릭스보기 :

temlpate<class T> 
struct matrix_view { 
    std::size_t height, width; 
    std::size_t offset, stride; 
    array_view<T> buffer; 

    // TODO: Ctors 
    // one from a matrix that has offset and stirde set to 0. 
    // another that lets you create a sub-matrix 
    array_view<T> operator[](std::size_t n) const { 
    return buffer.slice(offset+stride*n, width); // or width, depending on if row or column major 
    } 
}; 

이제 코드를 matrix_view의하지 행렬에 대한 작업을 수행합니다.

Answer 2

사용할 작은 행렬의 상위 행렬에 위치를 보유하는 하위 행렬 클래스를 만들 수 있습니다. 대부분 행과 열에 대한 시작 인덱스를 저장해야하는 경우를 제외하고는 해당 행렬에 대해 이미 가지고있는 항목을 인덱싱 한 다음 오프셋을 오프셋합니다. 올바르게 끝나면 주/루트 행렬은 전체 행렬을 경계로하는 부분 행렬이됩니다.