如何有效地改變矩陣的連續部分？

Question

給定M行的矩陣和N列，並將其分配爲M*N元素的字節數組（這些元素最初設置爲零），我將根據以下規則修改此矩陣：元素在某個元素的鄰域中發現必須設置爲給定的值。換句話說，給定一個矩陣，我應該設置矩陣的一個區域：爲此，我應該訪問數組中不連續的部分。

爲了執行上述操作，我已經獲得以下信息：

• 指針到位於在附近的中心處的元件（該指針時，必須在上述過程中改變操作）;這個元素的位置（行和列）也被提供;
• 大小附近（大號始終是一個奇數）的L*L。

實現此操作的代碼應儘可能快地在C++中執行：因此，我考慮使用上述指針訪問數組的不同部分。取而代之的是，鄰域的中心元件的位置（行和列）可能允許我檢查所指定的區域是否超過基體的尺寸（例如，該區域的中心可以被設置在矩陣的邊緣） ：在這種情況下，我應該只設置位於矩陣中的那部分區域。

int M = ... // number of matrix rows 
int N = ... // number of matrix columns 

char* centerPtr = ... // pointer to the center of the region 
int i = ... // position of the central element 
int j = ... // of the region to be modified 

char* tempPtr = centerPtr - (N+1)*L/2; 
for(int k=0; k < L; k++) 
{ 
    memset(tempPtr,value,N); 
    tempPtr += N; 
} 

我該如何改進代碼？ 如何處理一個區域可能超過矩陣的尺寸的事實？ 如何使代碼在執行時間方面更高效？

Answer 1

您的代碼可能是在區域不重疊矩陣外，一般情況下是最佳的。使用這種代碼可能導致的主要效率問題是使用外部循環而不是行。這破壞了緩存和分頁性能。你沒有這樣做。

使用指針與最現代的編譯很少或沒有速度優勢。優化器將從正常的數組索引中得到非常好的指針代碼。在某些情況下，我已經看到數組索引代碼的運行速度比手動調整指針代碼的速度快得多。所以如果索引算法更清晰，不要使用指針算法。

有8個邊界情況：華北，西北，西，...，東北。其中每個都需要一個自定義版本的循環來觸及正確的元素。我會展示西北地區的情況，讓你解決其餘的問題。

最快的方式來處理的案件是一個3級的「如果」樹：

if (j < L/2) { // northwest, west, or southwest 
    if (i < L/2) { 
    // northwest 
    char* tempPtr = centerPtr - (L/2 - i) * N - (L/2 - j); 
    for(int k = 0; k < L; k++) { 
     memset(tempPtr, value, L - j); 
     tempPtr += N; 
    } 
    } else if (i >= M - L/2) { 
    // southwest 
    } else { 
    // west 
    } 
} else if (j >= N - L/2) { // symmetrical cases for east. 
    if (i < L/2) { 
    // northeast 
    } else if (i >= M - L/2) { 
    // southeast 
    } else { 
    // east 
    } 
} else { 
    if (i < L/2) { 
    // north 
    } else if (i >= M - L/2) { 
    // south 
    } else { 
    // no overlap 
    } 
} 

這是乏味的像這樣做，但你必須每個地區不超過3間的比較。