'프로그래밍'에 대한 글목

WaitForSingleObject()

2011.04.11 11:02

WaitForSingleObject() - 보통 FindFirstChangeNotification, FindNext..., FindClose... 등과 쓰임
1. 용도

    Thread가 특정 signal이 발생할 때까지 정지해 있다가,
    signal을 받으면, 작업을 수행하고 다시 정지 상태로 돌아가게할 필요를
    자주 느끼게 된다.
    WaitForSingleObject()와 WaitForMultipleObjects()를 사용하여
    이런 need를 해결할 수 있다.
    이 함수들은 CreateEvent(), SetEvent(), ResetEvent()와 함께 사용한다.
    
2. WaitForSingleObject()

    이 함수는 하나의 Event object를 만들어 놓고,
    이 Event가 signal(SetEvent())될 때까지 기다린다.
    
    DWORD WaitForSingleObject(
      HANDLE hHandle,          // Event object handle
      DWORD dwMilliseconds // time-out interval. 단위는 millisecond
                                         // INFINITE 으로 설정할 경우, 무한정 기다린다.
    );
    
    return value:
        1) WAIT_FAILED: fail. GetLastError()로 원인을 알 수 있다. 이 경우는 logic을 빠져나간다.
        2) WAIT_ABANDONED: 이 경우는 Event object를 reset하고, 다시 WaitForSingleObject()를 호출한다.
        3) WAIT_OBJECT_0: 기다리던 Event가 signal된 경우.
        4) WAIT_TIMEOUT: time-out이 된 경우.
        
3. Sample code

    DWORD  ret;
    
    while( TRUE )  {
        ret = WaitForSingleObject( hHandle, INFINITE );
    
        if( ret == WAIT_FAILED )
            return 0;
        else if( ret == WAIT_ABANDONED ) {
            ResetEvent( hHandle );
            continue;
        }
        else if( WAIT_TIMEOUT )
            continue;
        else {
            ResetEvent( hHandle );
            // 원하는 작업을 처리한다.
        }
    }

신고

'프로그래밍' 카테고리의 다른 글

WaitForSingleObject()  (0) 2011.04.11
다차원 트리 - KD Tree  (0) 2009.10.23

다차원 트리 - KD Tree

2009.10.23 18:16

KD트리(다차원 검색트리, k-dimension tree)는 Binary Search Tree를 다차원 공간으로 확장한 것으로써,기본 구조와 알고리즘은 BST와 유사하지만 트리의 레벨 차원을 번갈아 가며 비교한다는 점이 다르다.

예를 들어 a(5,4), b(2,7), c(9,5), d(3,1)을 차례로 트리에 삽입한다고 하면,
처음엔 a는 루트에 저장하고, 
루트레벨에서 x좌표를 비교한다고 하면,
다음은 b의 x좌표를 a의 x좌표와 비교,작으므로 왼쪽에 삽입,
그 다음엔 c의 x좌표를 a의 x좌표와 비교, 크므로 오른쪽에 삽입,
다음 d노드는 x좌표가 a보다 작으므로 왼쪽으로 내려왔다가 레벨2에서 b와의 y좌표를 비교했을때 작으므로 왼쪽노드로 가게 된다. 결과는 이렇다.





검색은 해당 레벨에 맞는 키값을 가지고 차례로 검색하면 된다.

과제로 했던 KD 트리의 구축과 검색 알고리즘만 간단히...
0과 1000사이의 2차원 좌표인 GPS정보를 원하는 만큼 만들어 KD트리로 관리하고
쿼리로 던지는 구역내의 좌표를 검색하는 코드다.
갯수마다 차이가 얼마나 나는지 알아보려고 아웃풋으로 시간비교가 나오는데 무시...

"입력파일 예"(자동 생성됨)
GPS data file (G_File_2.txt)
100 // GPS 좌표 개수 (N) = {10, 100, 1,000, 10,000, 100,000}
100, 100 // 2차원 GPS 좌표 (x, y) = {0 ? x ? 1,000, 0 ? y ? 1,000}
……
150, 150 // 100번째 GPS 좌표

Query data file (Q_File_1.txt)
10 // Query 개수 (Q) = {10, 100, 1,000, 10,000, 100,000}
0, 0, 10, 10 // 영역질의 좌표 (x1, y1, x2, y2) = {0 ? x1, y1, x2, y2 ? 1,000, x1 ? x2, y1 ? y2}
……
100, 150, 200, 250 // 10번째 영역질의 좌표


KDTree.h
struct NODE
{
	int m_iX;
	int m_iY;
	struct NODE* m_pLeft;		//LEFT CHILD
	struct NODE* m_pRight;		//RIGHT CHILD
	struct NODE* m_pParent;	//PAREENT
};
typedef struct NODE NODE;
KDTree.c

#include "KDTree.h" #include <stdlib.h> #include <stdio.h> #include <math.h> #include <time.h> #include <windows.h> #define XLEVEL 0 #define YLEVEL 1 void SetNode(int x, int y, NODE* pNode); NODE* Insert(int x, int y, NODE* pRoot); void RegionSearch(int x1, int y1, int x2, int y2, NODE* pRoot, int iLevel); void CreatGPS(FILE* pFile, char* pcGpsFName, int iNum); void CreatQuery(FILE* pFile, char* pcQueryFName, int iQnum); int g_iCount; int main(void) { /***************************************/ // 한번에 모든 프로시져를 수행하지 않으므로 // 측정을 원하는 Data값으로 각각 변수 값과 파일Name을 변경해주어야 함. // Default : 100, 100 long iNum = 100; //사용자 수 long iQnum = 100; //질의 수 char* pcGpsFName = "G_File_2.txt"; char* pcBuildFName = "BuildTime_2.txt"; char* pcQueryFName = "Q_File_2.txt"; char* pcSearchFName = "SearchTime_2_2.txt"; /***************************************/ int i = 0; int x, y; int x1, y1, x2, y2; FILE* pFile1 = NULL; FILE* pFile2 = NULL; FILE* pFile3 = NULL; FILE* pFile4 = NULL; LARGE_INTEGER StartTime; LARGE_INTEGER TicksPerSecond; LARGE_INTEGER CurrentTime; double dSeconds; NODE* pRoot = NULL; //트리의 루트노드 CreatGPS(pFile1, pcGpsFName, iNum); //GPS좌표 파일생성 CreatQuery(pFile2, pcQueryFName, iQnum); //질의영역좌표 파일생성 fopen_s(&pFile1, pcGpsFName, "rt"); fopen_s(&pFile3, pcBuildFName, "wt"); if(pFile1 == NULL || pFile3 == NULL) { printf("File Open Error!\n"); return 1; } QueryPerformanceFrequency(&TicksPerSecond); QueryPerformanceCounter(&StartTime); fscanf_s(pFile1, "%d", &iNum); for(i = 0; i < iNum ; i++) { fscanf_s(pFile1, "%d %d", &x, &y); pRoot = Insert(x, y, pRoot); QueryPerformanceCounter(&CurrentTime); dSeconds = (double)(CurrentTime.QuadPart - StartTime.QuadPart) / (double)TicksPerSecond.QuadPart; fprintf_s(pFile3, "%lf\n", dSeconds); } fclose(pFile1); fclose(pFile3); fopen_s(&pFile2, pcQueryFName, "rt"); fopen_s(&pFile4, pcSearchFName , "wt"); if(pFile2 == NULL || pFile4 == NULL) { printf("File Open Error!\n"); return 1; } QueryPerformanceCounter(&StartTime); fscanf_s(pFile2, "%d", &iQnum); for(i = 0; i < iQnum ; i++) { fscanf_s(pFile2, "%d %d %d %d", &x1, &y1, &x2, &y2); RegionSearch(x1, y1, x2, y2, pRoot, 0); g_iCount = 0; QueryPerformanceCounter(&CurrentTime); dSeconds = (double)(CurrentTime.QuadPart - StartTime.QuadPart) / (double)TicksPerSecond.QuadPart; fprintf_s(pFile4, "%lf\n", dSeconds); } fclose(pFile2); fclose(pFile4); return 0; } void SetNode(int x, int y, NODE* pNode) { pNode->m_iX = x; pNode->m_iY = y; pNode->m_pLeft = NULL; pNode->m_pRight = NULL; } //트리 구축 함수 NODE* Insert(int x, int y, NODE* pRoot) { int iLevel = XLEVEL; NODE* pHead = pRoot; NODE* pParent = NULL; NODE* pTemp = NULL; pTemp = (NODE*)malloc(sizeof(NODE)); //GPS좌표의 노드 생성 SetNode(x, y, pTemp); if(pRoot == NULL) { pRoot = pTemp; pTemp = NULL; return pRoot; } while(1) { pParent = pHead; // 삽입하려는 부모 노드를 저장 if(iLevel == XLEVEL) // X축 기준이면 { if(x <= pHead->m_iX ) pHead = pHead->m_pLeft; else pHead = pHead->m_pRight; } else // Y축 기준이면 { if(y <= pHead->m_iY) pHead = pHead->m_pLeft; else pHead = pHead->m_pRight; } if(pHead == NULL) //자식이 없으면 탈출 break; iLevel = (iLevel+1)%2; } if(iLevel == XLEVEL) // X축 기준에서 { if(pTemp->m_iX <= pParent->m_iX) //New 노드의 x좌표가 부모의 x좌표보다 작으면 왼쪽Child에 생성 pParent->m_pLeft = pTemp; else pParent->m_pRight = pTemp; //New 노드의 x좌표가 부모의 x좌표보다 크면 오른쪽Child에 생성 } else // Y축 기준에서 { if(pTemp->m_iY <= pParent->m_iY) pParent->m_pLeft = pTemp; else pParent->m_pRight = pTemp; } pTemp = NULL; pHead = NULL; pParent = NULL; return pRoot; // Root노드 포인터 반환 } //탐색 함수 void RegionSearch(int x1, int y1, int x2, int y2, NODE* pRoot, int iLevel) { if(pRoot == NULL) return; //영역내의 노드가 있으면 좌표 출력 if( (pRoot->m_iX >= x1 && pRoot->m_iX <= x2) && (pRoot->m_iY >= y1 && pRoot->m_iY <= y2) ) { printf("( %d , %d )\n", pRoot->m_iX, pRoot->m_iY); g_iCount++; } if(iLevel == XLEVEL) //X축 기준이면 { //내부영역에 해당하면, 더 많은 노드를 찾기 위해 다음 레벨로 이동, 그렇지 않으면 return해서 그 레벨의 검색은 끝남 if(pRoot->m_iX >= x1) RegionSearch(x1, y1, x2, y2, pRoot->m_pLeft, (iLevel+1)%2); if(pRoot->m_iX <= x2) RegionSearch(x1, y1, x2, y2, pRoot->m_pRight, (iLevel+1)%2); } else { if(pRoot->m_iY >= y1) RegionSearch(x1, y1, x2, y2, pRoot->m_pLeft, (iLevel+1)%2); if(pRoot->m_iY <= y2) RegionSearch(x1, y1, x2, y2, pRoot->m_pRight, (iLevel+1)%2); } return; } //GPS 좌표 생성 함수 void CreatGPS(FILE* pFile, char* pcGpsFName, int iNum) { int i = 0; int x = 0; int y = 0; fopen_s(&pFile, pcGpsFName, "wt"); if(pFile == NULL) { printf("File Open Error!\n"); exit(0); } fprintf(pFile, "%d\n", iNum); for(i = 0; i < iNum; i++) //랜덤좌표 생성 { srand(i*100); x = rand()%1000; y = rand()%1000; fprintf(pFile, "%d %d\n", x, y); } fclose(pFile); } //질의영역 좌표 생성 함수 void CreatQuery(FILE* pFile, char* pcQueryFName, int iQnum) { int i = 0; int x1 = 0; int y1 = 0; int x2 = 0; int y2 = 0; int iTempX = 0; int iTempY = 0; fopen_s(&pFile, pcQueryFName, "wt"); if(pFile == NULL) { printf("File Open Error!\n"); exit(0); } fprintf_s(pFile, "%d\n", iQnum); //랜덤 좌표 생성, 작은 좌표가 x1, y1에 가게 함 for(i = 0; i < iQnum; i++) { srand(i*200); x1 = rand()%1000; iTempX = rand()%1000; if(x1 <= iTempX) { x2 = iTempX; } else { x2 = x1; x1 = iTempX; } y1 = rand()%1000; iTempY = rand()%1000; if(y1 <= iTempY) { y2 = iTempY; } else { y2 = y1; y1 = iTempY; } fprintf_s(pFile, "%d %d %d %d\n", x1, y1, x2, y2 ); } fclose(pFile); }

KD트리의 장점은 기본 키 필드가 없거나 범위 검색이 많은 응용분야에 적합하지만 
밸런스 트리가 아니므로 데이터의 입력 순서나 분포에 따라 트리의 높이가 높아질 수 있으며 검색 성능이 떨어짐(검색 필드 값이 균등하게 분포되어 있지 않을 경우)


저작자 표시 비영리
신고

'프로그래밍' 카테고리의 다른 글

WaitForSingleObject()  (0) 2011.04.11
다차원 트리 - KD Tree  (0) 2009.10.23

K-D, kd source code, kd tree, kd트리, 다차원 검색트리

티스토리 툴바