ITqom

2016년 5월 6일 금요일

리눅스의 파일처리 - read()

이전에 리눅스에서는 모든장치(H/W, 외부장치 포함)는 파일로써 관리되며, 장치에 접근하기 위해서는 파일디스크립터(FD)를 사용한다고 언급했었다.

이제 파일에 접근하여 수행하는 작업들 중에서 read()에 대해서 살펴보자.

read()는 말 그대로 '파일을 읽어오는 형태 구나'라고 생각하면된다.

read()의 역할은 open한 파일을 읽어온다, 즉 파일의 내용을 불러온다.
(파일디스크립터을 통해 파일에 접근한 뒤 파일의 내용을 저장할 수 있는 기능)

ex) read 함수 사용법
: read(파일 디스크립터, 파일의 내용을 저장할 공간, 불러올 파일의 내용크기);

ex) read함수를 사용해 cat명령어 수행하기.

리눅스의 파일처리 - open()

리눅스에서는 디렉터리뿐만 아니라 하드웨어적인 모든 장치들을 파일로 취급한다.

( 일반 파일뿐만아니라, 외부장치도 파일로 취급함. )

그래서 어떤 특정한 장치(H/W)에 접근하기 위해서 파일디스크립터(FD)를 사용하면된다.

파일디스크립터(FD)는 특정한 파일에 접근하기위해 추상화시켜놓은 장치이다.

간다히 말해서 '장치에 접근하기위한 핸들러 같은 역할을 하는구나' 생각하면된다.

이러한 핸들러, 파일디스크립터를 사용하는 방법은 먼저 파일을 연 상태에서 데이터의 추가, 삭제 등 원하는 작업을 하며, 필요한 역할을 끝냈으면 연 파일을 닫아주는 작업또한 필요하다. 이러한 작업을 다음과같은 함수를 이용하면된다.

1. Open()

핸들러 역할을하는 파일디스크립터의 의미를 부여할 수 있는 open()이다.

ex) open("파일명", 옵션);

: 파일명 : 원하는 파일을 입력

: 옵션 : 파일을 읽기, 수정, 생성 등 어떠한 작업을 할것인지 옵션부여

필요한 작업에서 다양한 옵션을 선택하는데, 그 중에서 대표적으로 사용하는 4가지 옵션

- O_RDONLY : 읽기전용으로 파일열기

- O_RDWR : 읽기/쓰기 전용으로 파일열기

- O_CREAT : 파일의 생성

- O_APPND : 파일에 추가

리눅스의 파이프명령( | )으로 이옵션들을 함께 사용할수있다.

ex) 파일을 읽기/쓰기 전용으로 열기, 파일이 존재하지않으면 생성.

fd = open("test.txt", O_RDWR | O_CREAT)

// fd는 핸들러 역할을 하며, test.txt의 파일 크기가 저장됨.

그리고 필요한 작업을 마쳤다면, 파일을 연상태이니 close()함수를 통해서 닫으면된다.

ex) close(fd);

ex) Open함수 사용

2016년 5월 1일 일요일

고급정렬 알고리즘(1) - 병합정렬

선택, 버블, 삽입정렬의 수행시간은 평균적으로 Theta(n의 제곱)의 시간이 걸렸다.

이보다 수행시간을 더 줄일 수 있는 방법은 있을까? 물론, 존재한다.

이번장에서는 병합 정렬(Merge Sort)에 대해서 알아보도록 하겠다.

병합정렬이란 N개의 원소들중에서 가운데를 기준으로 반반씩 나눈 뒤에

앞의 원소들은 전반부, 뒤의 원소들은 후반부로 가정을하며, 이 전반부, 후반부가 각각 N개, N/2개, N/4개 ... 2개, 1개가 남을때까지 나누어주는 분리과정, 그리고 분리과정을 통해 나온 원소의 수를 1개씩, 2개씩.. n/2개씩 n개씩 비교하면서 정렬시키는 병합과정이 필요하다.

(분리과정, 병합과정 2개의 알고리즘이 필요하다)

조금 더 자세히 알아보면...

Ex) 병합정렬 과정

A = { 5, 4, 9, 2, 7, 1, 6, 3 }

1회 분리( 5, 4, 9, 2, 7, 1, 6, 3 )

: 전반부 ▶ 5, 4, 9, 2 & 후반부 ▶ 7, 1, 6, 3

2회 분리( 5, 4, 9, 2 )

: 전반부 ▶ 5, 4 & 후반부 ▶ 9, 2

3회 분리( 5, 4 )

: 전반부 ▶ 5 & 후반부 ▶ 4 - 분리완료

4회 분리( 9, 2 )

: 전반부 ▶ 9 & 후반부 ▶ 2 - 분리완료

5회 분리( 7, 1, 6, 3 )

: 전반부 ▶ 7, 1 & 후반부 ▶ 6, 3

6회 분리( 7, 1 )

: 전반부 ▶ 7 & 후반부 ▶ 1 - 분리완료

7회 분리( 6, 3 )

: 전반부 ▶ 6 & 후반부 ▶ 3 - 분리완료

여기까지 분리가 완료된다면(전반부, 후반부가 하나의 원소가 남을경우) 병합을 실행

병합은 전반부의 원소들과 후반부의 원소들의 앞부분을 병합하며 정렬시켜 나아감

1회 병합 (전반부 : 5 / 후반부 : 4)

▶ 4 ( 5 / 4 )

▶ 4, 5 ( 5 / ) - 병합완료

2회 병합 (전반부 : 9 / 후반부 : 2)

▶ 2 ( 2 / 9 )

▶ 2, 9 ( / 9 ) - 병합완료

3회 병합 (전반부 : 4, 5 / 후반부 : 2, 9)
▶ 2 ( 4, 5 / 2, 9 )

▶ 2, 4 ( 4, 5 / 9 )
▶ 2, 4, 5 ( 5 / 9 )
▶ 2, 4, 5, 9 ( / 9 ) - 병합완료

4회 병합 (전반부 : 7 / 후반부 : 1)

▶ 1 ( 7 / 1 )

▶ 1, 7 ( 7 / ) - 병합완료

5회 병합 (전반부 : 6 / 후반부 : 3)

▶ 3, ( 6 / 3 )

▶ 3, 6 ( 6 / ) - 병합완료

6회 병합 (전반부 : 1, 7 / 후반부 : 3, 6)

▶ 1 ( 1, 7 / 3, 6 )

▶ 1, 3,    (    7 / 3, 6 )
▶ 1, 3, 6 (    7 / 6 )
▶ 1, 3, 6, 7 (    7 / )   - 병합완료

7회 병합 (전반부 : 2, 4, 5, 9 / 후반부 : 1, 3, 6, 7)

▶ 1       ( 2, 4, 5, 9 / 1, 3, 6, 7 )
▶ 1, 2     ( 2, 4, 5, 9 /   3, 6, 7 )
▶ 1, 2, 3    (   4, 5, 9 /   3, 6, 7 )
▶ 1, 2, 3, 4     (   4, 5, 9 /     6, 7 )
▶ 1, 2, 3, 4, 5    (      5, 9 /     6, 7 )
▶ 1, 2, 3, 4, 5, 6,    (         9 /     6, 7 )
▶ 1, 2, 3, 4, 5, 6, 7        (        9 /       7 )
▶ 1, 2, 3, 4, 5, 6, 7, 9     (        9 /        ) - 병합완료

그렇다면 수행시간을 얼마나 단축시킬 수 있겠는가?

우선 기초적인 정렬(선택, 버블, 삽입)을 사용했을경우, 100개의 원소가있다면 1부터 N까지 숫자들을 비교 후 큰 수를 뒤로 보내거나(선택, 버블) 앞에서부터 하나씩 비교하며 정렬시켜 나아갈 것이다(삽입). 이렇게 된다면 상당히 긴 수행시간이 소요될 것이다.

그렇다면 병합정렬을 사용하게 된다면?

100개의 원소가있다면, 100개 → 50개 → 25개 → 12개 → 6개 → 3개 → 1개의 원소가 남을때까지 나누고, 1개 → 3개 → 6개 → 12개 → 25개 → 50개 → 100개가 될때까지 나눈 숫자들을 다시 병합하며 정렬이 되는것이다.

평균적으로 Theta(nlogn)의 시간이 소요된다.

알고리즘을 보면..

▶실행결과