在同一時間內「分割」一個矩陣

我想在C++中實現Strassen的矩陣乘法算法，並且我想要找到一種方法將兩個矩陣分成四個部分，每個部分在不同的時間。這是當前的方式，我這樣做：在同一時間內「分割」一個矩陣

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]; 
    } 
}

這種做法顯然是爲O（n^2），並增加了N^2 *的log（n）的運行時間，因爲它是所謂的每個遞歸呼叫。

似乎在常量時間這樣做的方式是創建指向四個子矩陣的指針，而不是複製值，但我很難找出如何創建這些指針。任何幫助，將不勝感激。

來源

2016-11-29 chrisz

你的源矩陣的大小是2 * n嗎？ – Pavel

不要想到矩陣，想到矩陣的意見。

矩陣視圖具有指向緩衝區的指針，其寬度，高度，偏移量和列（或行）之間的跨度爲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 S，不是矩陣的工作。

來源

2016-11-29 16:52:25 Yakk

正是我在找的，謝謝！ – chrisz

您可以創建一個子矩陣類來保存要使用的較小矩陣的父矩陣中的位置。大多數情況下，您已經擁有了矩陣，除了需要存儲行和列的起始索引，然後通過偏移索引來抵消索引。如果正確完成，主/根矩陣將是以完整矩陣作爲邊界的子矩陣。

來源

2016-11-29 16:44:33 1201ProgramAlarm

在同一時間內「分割」一個矩陣

回答

相關問題