Programming Methodology Instructor: Kyuseok Shim Project #4: external sort with template Due Date: 0:0 a.m. between 2007-12-2 & 2007-12-3 Introduction 이프로젝트는 C++ 의 template을이용한 sorting algorithm과정렬해야할데이터의크기가 main memory의크기를넘어갈때데이터를정렬하는 external sorting algorithm을구현하는것이다. Implementation 1. in memory sorting algorithm. memory안에들어갈수있는크기의데이터를정렬하는 heap-sort을구현한다. 데이터의 type은정해져있는것이아니라 template을사용하고, 정렬은오름차순으로한다. 2. main memory의크기보다큰사이즈의데이터를정렬하는 external sorting algorithm을구현한다. 입력파일과결과파일은 text형태이다 중간생성파일들은 text 형태가아닌 binary 형태로저장한다 page size는 1024 byte로고정한다 Input & Output input file은숫자들의집합이다. 첫줄의첫번째숫자는현재파일에들어있는데이터의개수를나타내고그다음은 S/I/L/F/D 중한문자이다 short, int, long, float, double. 다음줄은빈칸이나탭키로구별되는숫자들이나열된다. 100 I // 앞으로 integer 100개가나옴 722 329 62 1958 2 2950 6291 58 942... 2984 output file은정렬된숫자들의집합이다. 각줄마다숫자를하나씩출력한다. 2 66 245...
프로그램실행예시 >( 실행파일 ) ( 입력 ) ( 메모리사이즈-byte) ( 출력 ) 의형식으로실행한다 > external_sort.exe input.txt 102400 output.txt > 참고 1. external sort와 heap의 pseudo-code는게시된 pdf 파일을참고하도록한다. 2. heap 다음 skeleton code를참고한다. 기능만동일하다면아래코드와전혀다르게구현하더라도무방하다. 클래스이름, 함수이름, 함수인자종류등은임의로변경가능 template<class T> class HeapEntry { public : T value; // data int run; // 어느 run에서온 data인가를기록 ; template<class T> class Heap { private: HeapEntry<T> *heap; // heap으로사용할공간 Int maxsize; // allocate 받은 heap size Int cursize; // 현재 heap size, insert나 extract있을때 +/-... // 추가로필요한항목추가 public : Heap(); // Constructor, 필요하면인자추가 ~Heap(); // Destructor int insert(const HeapEntry<T>& h); // Heap에 data를삽입 HeapEntry<T>& extract(); // top node에있는값을반환, 삭제 void build_heap(); // heap을구성하는함수 void heapify(); // 주어진 data로 heap을만듬 HeapEntry<T>& looktop(); // heap의젤윗부분반환, 삭제X... // 추가로필요한항목추가 ;
3. binary 형태로읽고쓰기 C의함수를이용 # 메모리의내용을파일을쓰는함수 size_t fwrite(const void* ptr, size_t size, size_t count, FILE* stream ); ptr : Pointer to the array of elements to be written size : Size in bytes of each element to be written count : Number of elements, each one with a size of size bytes stream : Pointer to a FILE object that specifies an output stream example #include <iostream> #include <cstdio> using namespace std; int main() { FILE* pfile; int buffer[5] = {1,2,3,4,5; pfile = fopen("myfile.bin","wb"); if ( pfile == NULL ) { // 파일을열지못했으면오류출력 cerr<<"file error"<<endl; return 1; fwrite(buffer,sizeof(int),5,pfile); // buffer가가리키는주소부터 fclose(pfile); // sizeof(int)*5 byte를 return 0; // pfile에씀
# 파일의내용을메모리에읽어들이는함수 size_t fread (void *ptr, size_t size, size_t count, FILE* stream ); ptr : Pointer to a block of memory with a minimum size of (size*count) bytes size : Size in bytes of each element to be read count : Number of elements, each one with a size of size bytes stream : Pointer to a FILE object that specifies an input stream example #include <iostream> #include <cstdio> using namespace std; int main() { FILE* pfile; int buffer[5]; pfile = fopen("myfile.bin","rb"); if ( pfile == NULL ) { cerr<<"file error"<<endl; return 1; fread(buffer, sizeof(int), 5, pfile);// buffer가가리키는주소로부터 fclose(pfile); // sizeof(int)*5 byte 읽음 for ( int i = 0; i < 5; i++ ) cout<<"buffer["<<i<<"]="<<buffer[i]<<endl; return 0;
# 파일에서원하는위치로포인터를움직이는함수 int fseek ( FILE * stream, long int offset, int origin ); stream : Pointer to a FILE object that identifies the stream offset : Number of bytes to offset from origin origin : Position from where offset is added. It is specified by one of the following constants defined in <cstdio> SEEK_SET - Beginning of file SEEK_CUR - Current position of the file pointer SEEK_END - End of file example #include <iostream> #include <cstdio> using namespace std; int main () { FILE* pfile; int buf; pfile = fopen("myfile.bin","rb"); if ( pfile == NULL ) { cerr<<"file error"<<endl; return 1; fseek(pfile,-sizeof(int),seek_end); // 파일의끝에서 sizeof(int) 이동 fread(&buf,sizeof(int),1,pfile); // 현재위치에서 sizeof(int) byte cout<<"buf : "<<buf<<endl; // 를 buf에카피 ( 읽음 ) fseek(pfile,2*sizeof(int),seek_set); // 파일의시작부분에서 2*sizeof(int) fread(&buf,sizeof(int),1,pfile); //byte 이동해서 sizeof(int) byte cout<<"buf : "<<buf<<endl; // 읽어서출력 return 0;
제출사항 1. 제출방법및내용 1) 프로젝트구현파일제출 - 파일은 ee 홈페이지에과제제출을이용하여제출한다. - 소스파일과컴파일을할수있는파일과실행파일을압축하여제출한다. - 각제출파일이름은다음의형식을따른다. pro_4_ 학번.zip 예 ) pro_4_2007-12345.zip - 각소스파일상단에 E-mail 주소와작성자학번이름을적는다. 2) 보고서제출간단한설명과 discussion을하드카피로제출한다. 2. 제출일시파일제출마감일 : 2007년 12월 2 일과 3일사이새벽 0:00 - 구현파일제출시각은홈페이지과제제출시각에준한다보고서제출마감일 : 2007년 12월 3일오전 12:00( 정오 ) 302동 516-2호앞과제제출함 채점규칙몇가지다양한대용량데이터들에대해서정렬이정확히되는지, 중간생성파일이생성이되는지확인하여채점딜레이는하루에 10% 씩감점 Copy 발견시 F 처리