Re: [問題] for迴圈 處理矩陣問題
※ 引述《tomnelson (ㄚ隆)》之銘言：
: 看到各位在這篇推文中貢獻自己的想法, 雖然應該解決了原po的問題,
: 尤其是 "B[i][j] = A[i/3*3+2][j/3*3+2];" 的推文, 一行就解決了,
: 不過還是覺得有改進方式, 雖然在腦中已經大概有想法, 但是最近雜務頗多,
: 今天終於花了大概15分鐘把想法實作出來了, 以下提供給原po"另一種"參考!
: (僅提供副程式部份)
: void MatrixTest(int M[9][9], int T[9][9])
: {
: int i, j, x, y, s;
: for (i = 0; i < 9; i += 3)
: {
: x = i + 2;
: for (j = 0; j < 9; j += 3)
: {
: y = j + 2;
: s = M[x][y];
: T[i][j] = T[i][j + 1] = T[i][j + 2] = s;
: T[i + 1][j] = T[i + 1][j + 1] = T[i + 1][j + 2] = s;
: T[i + 2][j] = T[i + 2][j + 1] = T[i + 2][j + 2] = s;
: }
: }
: }
: 以上這種作法雖然沒有一行那麼漂亮, 但是我會這麼做是有原因的!
: 因為這種解法不會用到乘法與除法, 僅用到加法而已, 而且只要再稍微整理一下,
: 可以輕鬆改成給 N x N 矩陣用的函式, 另外,
: 如果有人注意到我上面三行 " .... = s;" 的排列方式,
: 應該會有人看出端倪, 沒錯, 這裡可以再最佳化, 可以使用memcpy來處理,
: 這樣對 N x N 矩陣, N值本身大於一定值時, 效率就會大幅顯現出來!
: 以上, 個人拙見, 僅供參考! 歡迎指教! :)
以下為最新版, 加入效能比較, 以及加入我說的memcpy方式, 文末有附測試結果!
抱歉沒有提供 "HRTimer_Win32.c" & "HRTimer_Win32.h" 兩檔案, 該兩檔案組成的
模組是在利用Win32 "QueryPerformanceFrequency" & "QueryPerformanceCounter"
來做高精度計時功能.
#include <stdio.h>
#include <string.h>
#include "HRTimer_Win32.h"
#define TOTAL_TEST_LOOPS 10000
/*
| 1 2 3 4 5 6 7 8 9 | | 5 5 5 8 8 8 2 2 2 |
| 2 3 4 5 6 7 8 9 1 | | 5 5 5 8 8 8 2 2 2 |
| 3 4 5 6 7 8 9 1 2 | | 5 5 5 8 8 8 2 2 2 |
| 4 5 6 7 8 9 1 2 3 | | 8 8 8 2 2 2 5 5 5 |
A = | 5 6 7 8 9 1 2 3 4 | B = | 8 8 8 2 2 2 5 5 5 |
| 6 7 8 9 1 2 3 4 5 | | 8 8 8 2 2 2 5 5 5 |
| 7 8 9 1 2 3 4 5 6 | | 2 2 2 5 5 5 8 8 8 |
| 8 9 1 2 3 4 5 6 7 | | 2 2 2 5 5 5 8 8 8 |
| 9 1 2 3 4 5 6 7 8 | | 2 2 2 5 5 5 8 8 8 |
*/
typedef void (*MatrixTestMethodFuncType)(int M[9][9], int T[9][9]);
void Matrix_Loop_Test(int iTestMethod, int iLoop, int M[9][9], int T[9][9]);
void Matrix_Test_Method1(int M[9][9], int T[9][9]);
void Matrix_Test_Method2(int M[9][9], int T[9][9]);
void Matrix_Test_Method3(int M[9][9], int T[9][9]);
MatrixTestMethodFuncType MatrixTestMethodFunctionArray[3] =
{Matrix_Test_Method1, Matrix_Test_Method2, Matrix_Test_Method3};
int A[9][9] =
{
{1, 2, 3, 4, 5, 6, 7, 8, 9},
{2, 3, 4, 5, 6, 7, 8, 9, 1},
{3, 4, 5, 6, 7, 8, 9, 1, 2},
{4, 5, 6, 7, 8, 9, 1, 2, 3},
{5, 6, 7, 8, 9, 1, 2, 3, 4},
{6, 7, 8, 9, 1, 2, 3, 4, 5},
{7, 8, 9, 1, 2, 3, 4, 5, 6},
{8, 9, 1, 2, 3, 4, 5, 6, 7},
{9, 1, 2, 3, 4, 5, 6, 7, 8}
};
int B[9][9];
int main(int argc, char *argv[])
{
int i, iRtn;
unsigned int uiTimeElapsedUSec = 0, uiTimeElapsedMSec = 0;
HRTimerType *Timer = NULL;
Timer = HRTimer_CreateObject();
if (Timer)
{
for (i = 1; i <= 3; i++)
{
iRtn = HRTimer_Start(Timer);
Matrix_Loop_Test(i, TOTAL_TEST_LOOPS, A, B);
iRtn = HRTimer_Stop(Timer);
iRtn = HRTimer_GetTimeElapsedUSec(Timer, &uiTimeElapsedUSec);
iRtn = HRTimer_GetTimeElapsedMSec(Timer, &uiTimeElapsedMSec);
printf("Test [%d] result: %u microseconds, %u milliseconds.\n", i,
uiTimeElapsedUSec, uiTimeElapsedMSec);
}
Timer = HRTimer_DeleteObject(Timer);
}
return 0;
}
void Matrix_Loop_Test(int iTestMethod, int iLoop, int M[9][9], int T[9][9])
{
int i;
if (iTestMethod < 1 || iTestMethod > 3) return;
if (iLoop <= 0) return;
printf("[Matrix Loop Test %d][Loops: %d]\n", iTestMethod, iLoop);
for (i = iLoop; i--;) (MatrixTestMethodFunctionArray[iTestMethod - 1])(M, T);
}
/*
Non-optimized type: B[i][j] = A[i/3*3+2][j/3*3+2];
*/
void Matrix_Test_Method1(int M[9][9], int T[9][9])
{
int i, j;
for (i = 9; i--;)
for (j = 9; j--;)
T[i][j] = M[i/3*3+2][j/3*3+2];
}
/*
Optimized type 1: Use normal method for array elements copy (1-by-1)
*/
void Matrix_Test_Method2(int M[9][9], int T[9][9])
{
int i, j, x, y, s;
for (i = 6; i >= 0; i -= 3)
{
x = i + 2;
for (j = 6; j >= 0; j -= 3)
{
y = j + 2;
s = M[x][y];
T[i][j] = T[i][j + 1] = T[i][j + 2] = s;
T[i + 1][j] = T[i + 1][j + 1] = T[i + 1][j + 2] = s;
T[i + 2][j] = T[i + 2][j + 1] = T[i + 2][j + 2] = s;
}
}
}
/*
Optimized type 2: Use memcpy for array elements copy (3-by-3)
*/
void Matrix_Test_Method3(int M[9][9], int T[9][9])
{
int i, j, x, y, s[3], csize;
csize = sizeof(s);
for (i = 6; i >= 0; i -= 3)
{
x = i + 2;
for (j = 6; j >= 0; j -= 3)
{
y = j + 2;
s[0] = s[1] = s[2] = M[x][y];
memcpy(&T[i][j], &s, csize);
memcpy(&T[i + 1][j], &s, csize);
memcpy(&T[i + 2][j], &s, csize);
}
}
}
測試結果:
[Matrix Loop Test 1][Loops: 10000]
Test [1] result: 14824 microseconds, 14 milliseconds.
[Matrix Loop Test 2][Loops: 10000]
Test [2] result: 4095 microseconds, 4 milliseconds.
[Matrix Loop Test 3][Loops: 10000]
Test [3] result: 5770 microseconds, 5 milliseconds.
結論:
使用我修改的方式(Test [2])會比原先方式快將近三倍以上,
而使用memcpy方式(Test [3])雖然在此慢於我原先修改的方式,
但仍然快原先方式兩倍接近三倍,
在這邊先前已經說過, 當N x N矩陣中, N值大於某數時, 這些測試值會有更明顯的差距,
我相信memcpy方式(Test [3])仍會與我先前修改的版本(Test [2])有極小差距,
甚至可能超越.
編譯&測試環境:
OS: Windows 2000
DEV: mingw + GCC 4.4.1 (沒有加入任何最佳化參數 -O1/-O2/-O3...等等)
CPU: Athlon XP Barton 2600+
MEM: 1GB DDR400
Happy coding :)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.245.109
→
04/28 23:49, , 1F
04/28 23:49, 1F
推
04/28 23:58, , 2F
04/28 23:58, 2F
推
04/29 04:39, , 3F
04/29 04:39, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 5 篇)：