컴퓨터 과학 - 데이터 구조와 처리

 

 

 [개요]

• 3장에서는 DRAM, 플래시 메모리, 디스크 드라이브등의 메모리 장치를 읽고 쓰는 방식이 각 메모리 장치의 속도에 영향을 끼친다는 사실을 알아봤다.
• 5장에서는 데이터가 캐시 메모리에 있는지 여부에 따라 성능이 달라진다는 사실을 알아봤다.
• 이러한 시스템 메모리에 염두하고 데이터를 조직적으로 잘 정리하면 더 나은 성능을 얻을 수 있다. 이러한 성능 향상 방법으로 데이터 구조 (데이터를 조직화 하는 표준적인 방법)을 살펴본다.

[용어 정리]

• 참조 지역성
  - 필요한 데이터를 메모리에서 서로 근처로 유지하라, 금방 사용할 데이터는 더 가까운 곳에 저장하라라는 뜻이다.
• 기저 주소
  - 배열에서 0번째 원소의 주소, 바탕이 되는 주소
• 문자열 터미네이터
  - 문자열 끝을 표시하는 문자
• 편의 문법
  - 문법적으로 더 읽기 쉽고 이해하기 편하게 표현하는 것을 의미
• 아이노드
  - 디스크 블록에 대한 인덱스와 노드를 합친 단어

[내용]

1. 기본 데이터 타입
   1. 프로그래밍 언어는 다양한 데이터 타입을 제공하는데, 타입에는 크기 와 해석 이라는 두가지 측면이 존재한다. 크기 는 데이터의 크기를 의미 하고, 해석은 부호의 여부, 소수점인지, 문자인지등을 판단 하는 것을 의미한다.
   포인터의 등장
   1. 1964년 포인터 라는 개념이 해럴드 로슨에 의해 발명되었다. 포인터는 컴퓨터 아키텍처에 따라 결정되는 크기를 가지고 있으며, 메모리 주소값을 갖는 데이터 타입으로 해석 된다.
   2. 일부 언어는 잘못된 포인터의 사용으로 인한 오류를 막기 위해 참조라는 개념이 등장했다.
   3. 또한 새로 등장한 아키텍처로 코드를 포팅하면 프로그램이 깨지고, 종종 디버깅하기 어려운 방식으로 잘못되는 경우도 있다. 이를 해결하기 위해 두가지 접근 방식이 생겨났다.
   두가지 독립적인 접근 방식
   1. 이식성(호환성)
   2. 자바 같은 포인터를 없앤 언어 생성
2. 배열
   1. 프로그래밍 언어는 배열을 제공하는 데, 이 배열의 호수를 인덱스 라고 하고, 각각의 집을 원소라고 한다. 배열원소 타입은 모두 같아야 한다고 정해져 있다.
   2. 각 원소는 기저 주소로 부터 얼마나 떨어져 있는지를 행열로 지정할수 있다.
   3. 프로그램언어는 다차원 배열을 지원한다.
   다차원 배열의 단점
   1. 참조 지역성이 문제가 된다.
      - 다차원 배열에서 행 인덱스가 바뀌면 열 개수 만큼 떨어져 있는 메모리 위치에 있는 원소로 접근해야 한다. 행 인덱스가 바뀔때 더 많은 이동이 일어난다.
   배열의 단점
   1. 인덱스 검사가 필수적이다. 인덱스 검사를 하지 않는 언어의 경우 배열 영역을 벗어나는 위치의 데이터에 접근 할수 있어 보안상의 구멍이 발생할수 있다.
3. 비트맵
   1. 원하는 데이터를 표시하기에 기본 데이터가 너무 클때가 있다. 예를 들어 참과 거짓을 표현하기위해서는 1비트만 필요하다. 이때 필요한 것이 비트의 배열인 비트맵 이다.
      

      

   비트맵에 대해 수행 할수 있는 기본 연산
   1. 개요
      1) 정수의 나눗셈을 통해 바이트를 찾을 수 있다. 필요한 연산을 8로 나누는 것이다. 예를들어 비트 번호가 17이라면 17/8은 2이므로 2인덱스(세번째) 바이트에서 비트를 찾을 수 있다.
      |
      2) 다음으로 비트 위치에 대한 마스크를 만들어야 한다. 먼저 비트 번호와 0x07을 AND해서 하위 3비트(8가지 경우의 수)를 얻는다. 예를 들어 17이 비트 번호이면 000010001 AND 00000111 = 00000001을 얻는다. (3비트로 나눴을 경우 1이란 소리이다) 이 2진수를 왼쪽 시프트 하면 00000010이 되고 17번 비트의 위치가 된다(17은 3번째 바이트에서 두번째임)
   2. 비트 설정하기(1로 만들기)
      - 비트들 = 비트들 OR 마스크
   3. 비트 지우기(0으로 만들기)
      - 비트들 AND (NOT 마스크)
   4. 비트가 1인지 검사하기
      - (비트들 AND 마스크) != 0
   5. 비트가 0인지 검사하기
      - (비트들 AND 마스크) == 0
4. 문자열
   1. 여러 문자로 이루어진 시퀀스를 문자열이라고 한다.
   2. 배열과 마찬가지로 문자열을 연산할 때도 그 길이를 알아야 한다. 문자열 길이를 미리 알 수 없는 경우 큰 배열을 사용하는 경우가 많다. 하지만 배열의 크기는 문자열의 길이와 관련이 없기 때문에 문자열 길이를 추적할 방법이 필요하다.
   문자열 길이를 추적할 방법
   1. 문자열 안에 길이를 저장하는 방법
      1. 단점
         - 8비트는 255자로 제한되기 때문에 더 긴 문자열을 만들때 추가적인 부가 비용이 생기는 단점이 있다.
   2. 0을 문자열 터미네이터로 지정해서 사용하는 방법
      1. 문자는 1개만드려면 1바이트가 필요하다.
      2. C언어의 문자열은 길이를 저장하지 않고, 문자열 끝을 표시하는 문자 NUL을 사용하여, NUL문자 즉, 0을 문자열 터미네이터로 사요하고 문자열의 길이를 측정한다.
         

         

      3. 문자열 길이는 6이지만 7바이트를 사용한 것을 알수 있다.
      4. 장점
         - 저장이 쉽다.
         1. 문자열 끝까지 출력하라는 명령이 주어지면 추가적인 비용이 없다.
      5. 단점
         - 문자열 터미네이터를 발견할 때까지 문자열을 스캔하면서 문자수를 세야 한다.
5. 복합 데이터 타입
   1. 예를들어 원하는 대로 데이터 타입을 만들 수 있는 방법이 있는데, 이것이 구조체이다. 구조체 안에 있는 여러 데이터를 구조체의 멤버라고 한다.
   2. 예를 들어 일시를 표현하려 할때 월,일,시,분,초는 1바이트가 필요하고, 연도는 2바이트가 필요하다. 이때 일시를 표현하려 할때 구조체를 사용하면 간단하다.
   3. 편의 문법이라고도 한다.
   4. 구조체를 사용하면 일시를 표현하는 데이터 구조처럼 복잡한 데이터 타입을 마치 프로그래밍 언어가 기본적으로 제공하는 데이터 타입처럼 사용할수 있다.
   패딩
   1. 프로그래밍 언어는 멤버 순서가 바뀌면 문제가 될 수도 있기 때문에 메모리 정렬을 지켜줘야 한다.
   2. 프로그래밍 언어 도구는 패딩을 팔요한 만큼 추가해 이 문제를 해결한다.
      

      

   공용체
   1. 공용체는 구조체와 다르게 모든 멤버가 메모리 공간을 가지고 있는 게 아니라, 하나의 메모리 공간을 멤버가 공유해서 사용한다.
6. 단일 연결 리스트
   1. 배열은 데이터가 늘어났을때 새로 더 큰 배열을 만들고 기존 배열 내용을 새 배열로 복사해야 하기 때문에, 데이터 양이 정해져 있지 않는 경우 부적합하다.
   2. 연결리스트는 목록에 들어갈 원소의 개수를 모르는 경우 배열보다 더 잘 작동된다.
      

      

   3. next는 리스트의 다음 원소 주소를 저장하는 포인터다. 리스트의 맨 앞은 헤드라고 하고, 마지막은 테일이다. 보통 NULL 포인터로 리스트의 원소가 아님을 표현한다.
   4. 리스트는 배열과 다르게 데이터가 연속적으로 위치해 있지 않다. 장점으로는 원소를 쉽게 추가할 수 있다.
   5. 이중 간접 주소 지정을 사용하면 1개의 노드 포인터 만으로 연결리스트를 구성할수 있다.
7. 동적 메모리 할당(힙 영역)
   1. 프로그램 런타임 라이브러리가 설정해주는 힙영역이 있다. MMU(메모리 관리장치)가 있는 시스템에서는 런타임 라이브러리가 프로그램에게 필요한 메모리 용량을 판단해 요청한다.
   2. 힙은 연결리스트로 구성된 동적 메모리 영역이며, 동적 메모리는 힙에서 얻어온다.
   3. C에서는 malloc 과 free 함수가 있다.
   malloc구현
   1. malloc은 단일 연결리스트 데이터 구조를 사용해 구현된다.
   2. 힙은 여러 블록으로 나뉘고 각 블록에는 크기와 다음 블록에 대한 포인터가 포함된다.
      

      

   3. 처음에는 전체 힙이 한 블록으로 존재한다. 프로그램이 메모리를 요청하면 malloc은 충분한 크기의 블록을 찾아서 요청받은 공간에 대한 포인터를 반환하고, 프로그램에게 할당한 메모리를 반영해 크기와 링크를 조정한다.
   4. 프로그램이 free로 메모리를 해제하면 메모리가 다시 연결리스트에 추가된다.
   5. malloc은 종종 블록리스트를 스캔하면서 두 블록을 합쳐서 더 큰 블록을 만든다.
   6. 시간이 지남에 따라 메모리 공간은 파편화(분리되어 파편처럼)되는데, 메모리르 모두 사용하지 않았음에도 너무 작은 가용 블록만 남아 malloc으로 요청 받은 메모리공간을 만들어 줄수없게 된다. MMU가 있는 시스템의 경우 더 큰 메모리를 필요로 할때 브레이크를 조정할수 있다.
   7. 단점
      - 경험이 적은 프로그래머는 할당하지 않은 메모리를 해제하거나 해제된 메모리를 계속 사용하는 실수를 종종 저지르곤 한다. 할당받은 메모리 경계의 밖에 데이터를 쓰면 size와 next필드를 오염시킬수도 있다.
8. 더 효율적인 메모리 할당
   1. 노드에 문자열을 가리키는 포인터가 포함된 연결리스트가 있을때, 노드에 사용할 메모리와 문자열에 사용할 메모리가 필요하기 때문에, malloc 의 부가 비용이 커질 수 있다. 16바이트 노드를 처리하기 위해 16바이트의 부가비용이 필요하고 , 4바이트 문자열을 처리하기 위한 16바이트(포인터) 부가 비용이 필요하다.
   2. 노드와 문자열을 합하면서 32바이트로 발생한 부가비용을 16바이트로 줄일 수 있다.
   3. 메모리 경계를 지키기 위해 패딩은 필요하다.
9. 가비지 컬렉션
   1. 자바나 자바스크립트 같은 언어는 포인터가 없지만 직접 malloc이나 free를 하지 않으면서도 동적 메모리 할당을 지원하는데, 이를 가비지컬렉션이라고 한다.
   2. 자바 같은 언어는 포인터 대신 참조를 사용한다. 포인터를 추상화해서 거의 비슷한 기능을 제공하지만 실제 메모리 주소를 노출하지 않는다.
   가바지 컬렉션
   1. 특징
      - 데이터 요소를 만들어 내면서 요소가 사용할 메모리도 할당하는 new 연산자를 제공한다.(c++은 가비지 컬렉션을 사용하지않지만 new연산자가 있다.)
      1. 언어의 런타임 환경이 변수 사용을 추적해서 더 이상 사용하지 않는 메모리를 자동으로 해제해준다.
      2. 각 메모리를 변수가 참조하는 횟수를 추적하여 더 이상 메모리를 참조하는 변수가 없을때 메모리를 해제하는 방법도 있다.
   2. 단점
      - 프로그래머가 가비지컬렉션 시스템을 제어할 수 없다.
      1. 프로그램이 아주 중요한 일을 하는데, 가비지 컬렉션이 작동되서 문제가 발생할수 있다.
      2. 불필요한 참조가 남는 경우가 자주있어 메모리 낭비가 발생한다.
10. 이중 연결 리스트
    1. 단일 연결 리스트는 delete함수에서 삭제하려는 원소의 바로 앞 원소를 찾아야만했다. 이로 인해 긴 리스트를 순회해야 하기 때문에 이주 느리다.
    2. 이중 연결 리스트는 이전 원소에 대한 포인터도 들어 있는 리스트다. 노드당 부가비용은 2배가 되지만 삽입, 삭제시 리스트 전체를 방문하지 않아도 된다.
11. 계층적인 데이터 구조
    1. 리스트의 길이가 n이라면 O(n)의 시간 복잡도가 생긴다. 이를 해결하기 위해 노드를 계층적으로 조직할 수 있다.
    2. 가장 간단한 게층적 데이터 구조는 2진트리이다. 이 데이터 구조는 내부에 숫자가 5개가 들어 있을때 최악의 경우 3번만 비교하면 원하는 숫자를 찾을 수 있다.
    3. 원소를 순차 수열로 증가하게 나열했다면 균형이 잡히지 않는 트리가 그려진다. 이를 해결하기 위한 가중치를 적용한 트리 알고리즘을 사용한다.
    4. log(n)의 시간으로 부가 비용을 절약할 수 있다.
12. 대용량 저장장치
    1. 디스크의 기본 단위는 블록이고,연속적인 블록을 클러스터라고 한다. 클러스터는 한 트랙 안에 연속적인 섹터로 이루어지므로, 데이터를 한 클러스터에만 저장할 수 있으면 좋겠으나 한 클러스터에 들어가기에 너무 큰데이터들도 있기에 불가능하다. 어떤 데이터를 저장하기에 충분한 크기가 되도록 블록을 여럿 확보해서 데이터를 이런 블록에 나눠 담아야 한다.
    2. 데이터를 디스크에 저장할때는 영구적인 존재인 파일이름이 필요하다.
    파일이름과 파일의 데이터를 디스크에 저장하는 방법
    1. 유닉스에서 등장함
    2. 블록중 일부를 아이노드로 따로 지정한다. 아이노드에는 파일에 대한 여러가지 정보가 들어간다.(파일 이름, 파일 소유자, 파일크기...) 아이노드에는 보통 직접블록 포인터가 12개 들어 있다.최대 4096 * 12 바이트까지 보관할수있다. 파일이 더 커지면 간접블록을 사용한다. 이보다 더 큰 파일을 저장해야 하면 2중 간접, 3중 간접블록을 통해 지원한다.
    3. 아이노드 정보중에는 블록에 데이터가 있는지 디렉토리정보가 있는지 표시하는 것도 있다. 디렉토리는 아이노드를 연결해준다. 디렉토리는 다른 디렉토리를 참조 할 수있다는 뜻이고, 트리 구조의 계층적 파일 시스템을 생성한다.
    4. 하지만 트리 구조가 아니다. 여러 아이노드가 같은 블록을 참조할수 있다. 각 참조를 링크라고 부른다. 같은 파일이 여러 디렉토리에 나타날수 있다.
    5. 디렉토리에 대해 링크할 수 있으면 편리한데, 이를 심볼릭 링크라고 한다. 하지만 심볼릭 링크를 허용하면 파일에 무한 루프가 발생하는데, 이를 감지하기 위해 사용중인 블록에 대한 정보를 저장할수있는 복잡한 구조가 생겨났다.
    6. 가용공간을 추적하는 방법으로 비트맵 방식이 있다. 1이 사용중인 블록이고 0이 사용가능한 블록을 가리킨다면 가용블록을 찾기 위해 비트가 1이 아닌 블록을 쉽게 찾을수 있다. 하지만 디스크에 데이터를 기록하던 도중 전원이 나갈 시 패널 스위치를 조작해 아이노드 번호를 입력 함으로써 파일 시스템을 수리해야 했다. 이를 해결하기 위해 fsck프로그램이 개발되고, 더 나아가 저너링 파일시스템이 등장했다.
13. 데이터 베이스
    1. 2진 트리는 커다란 데이터를 저장할때 잘 작동하지 않는다. 대신해 데이터 베이스를 사용한다.
    2. 데이터 베이스는 정해진 방식으로 조직화된 데이터 모음이다.
    3. DBMS(데이터베이스관리 시스템) 은 데이터베이스에 정보를 저장하고 읽어올수 있게 해주는 프로그램이다.
    4. 데이터 베이스는 B트리라는 데이터 구조를 활용한 시스템이다.
    B트리
    1. 균형트리지만 2진 트리가 아니다.
    2. 덜 효율적으로 공간을 사용하지만 효율이 더 높다.
       

       

    3. 공간만 차지하고 사용하지 않는 자식 링크가 있으면 각 노드가 범위를 조정하면서 쉽게 트리의 균형을 다시 잡을 수 있다.
14. 인덱스
    1. 인덱스가 여럿이면 다양한 방법으로 원하는 데이터를 효율적으로 검색할 수 있다.
       

       

15. 데이터 이동
    1. 프로그램은 한 지점에서 다른 지점으로 데이터를 이동시키기 위해 많은 시간을 소비한다. 따라서 효율적으로 하는게 중요하다.
    2. length이 짝수라면 루프 언롤링기법을 사용하면 코드를 효율적으로 만들수 있다.
       

       

    3. 다른 방법으로 더프의 장치로 구현한 알고리즘이 있다. 비트맵 방식을 이용해 0으로 초기화 한다.
16. 벡터를 사용한 I/O
    1. 시스템 성능에 있어 복사를 피해야 성능을 높일 수 있다. 예를 들어 mp3 형식의 오디오 데이터를 오디오 장치에 보내려 할때 mp3파일은 여러개의 프레임으로 구성되며, 각 프레임은 헤더 와 데이터로 구성된다. 이때 데이터를 복사해서 프레임을 만드는것이 아닌, 시스템에게 프레임의 각 부분을 가리키는 포인터 집합을 전달하고 다시 데이터를 사용할때 합쳐주는 방식을 사용한다.
    분산/수집
    1. 크기와 데이터에 대한 포인터로 이루어진 벡터를 운영체제에 넘긴다.
    2. 수집
       - 벡터를 활용해 데이터를 쓰는 행위
    3. 분산
       - 벡터를 사용해 데이터를 읽는 행위
    4. 분산/수집은 인터넷의 근간이 된 버클리 네트워크 코드의 주류가 되었다.
17. 객체 지향의 함정
    1. 객체 지향 프로그래밍은 주의 깊게 사용하지 않으면 선능 문제가 발생할수도 있다.
    2. 객체에는 함수인 메서드와 데이터인 프로퍼티가 존재하는데, 메모리 할당이 더 필요한 프로퍼티는 객체 구조체안에 있는 포인터를 통해 참조하게되며 데이터 구조가 생긴다. 이때 객체는 전역적인 함수대신 메소드 포인터를 들고다녀야 하는데, 객체 내의 데이터가 데이터만 저장하는 데이터 구조처럼 꽉 짜여 있지않어 성능적으로 떨어질 수 있다.
18. 정렬
    1. 정렬을 할때 정렬 대상이 포인터 크기보다 크다면 데이터를 직접 정렬하는 대신 데이터를 가리키는 포인터를 재배열하는 방식으로 정렬해서 데이터 자체가 여기저기 움직이지 않게 해야 한다.
    포트란 산술 IF문
    1. if문으로 식을 계산 후, 결과가 0보다 작으면 분기 1, 0과 같은면 분기 2, 0 보다 크면 분기 3을 실행한다.
    2. 유닉스 버전3 부터 퀵정렬알고리즘을 구현한 qsort 라는 라이브러리 함수가 도입됐다. qsort로 리스트를 정렬하려면 포트란 IF문처럼 둘을 비교해서 사용한다.
19. 해시
    1. 검색 메서드는 모든 데이터 구조를 순회하면서 비교를 여러번 수행해야 했지만, 해싱은 바로 접근 가능하다. 메모리에 데이터를 저장하고 읽는 연산을 다룬다. 해시 함수의 결과값을 사용해 키에 대응하는 데이터를 메모리에 저장할수 있다.
    2. 저장 장치에 데이터를 저장하는 방법 중에는 해시 함수의 결과를 배열 인덱스로 활용하는 방법인 해시 테이블이 있다.
    3. 해시의 경우 같은 주소값에 데이터를 저장하려 할때 해시 충돌이 발생한다. 이때 이 문제를 해결하기 위해 해시 체인을 사용한다. 해시 체인은 단일 연결리스트 형태로 삽입 정렬로 해시 체인에 원소를 넣어 만들수 있다.
20. 효율성과 성능
    1. 덜 효율적인 알고리즘을 돌려도 더 많은 프로세서를 사용하면 효율적인 알고리즘을 더 적은 프로세서로 실행할때보다 더 나은 성능을 얻을 수도 있다.
    데이터 베이스 샤딩
    1. 데이터 베이스를 각각 다른 기계에서 실행되는 여러 샤드로 나누는 방식을 말한다.
    2. 이 기법을 사용하면 작업을 여러 작업자로 나눠 수행할 수 있기 때문에 성능이 향상된다.

1. 참고 문헌
   1. 한 권으로 읽는 캄퓨터 구조와 프로그래밍