데이터 구조와 처리

데이터 구조와 처리

기본 데이터 타입

• 프로그래밍 언어는 다양한 기본 데이터 타입 제공
  • 크기(size,비트수)와 해석(interpretation,부호여부, 부동소수점, 문자?,포인터?...)
• 포인터
  • 컴퓨터 아키텍처에 따라 결정되는 크기의 부호가 없는 정수
  • 정수값이 아니라 메모리 주소로 해석
  • 잘못된 포인터 사용으로 인한 오류를 막기 위해 참조 개념이 탄생됨
• 참조
  • 객체의 메모리 주소가 아닌 객체를 가르키는 변수를 저장

배열

• 아파트와 같은 구조
• 아파트 동 안에 각 집의 호수(인덱스)가 있고 호수에 집(원소)이 존재
• 각 원소는 0번째 원소의 주소(기저 주소)에서 얼마나 멀리 떨어져 있는지를 나타낸 오프셋으로 지정 가능
• 참조 지역성
  • 2*2 배열 가정
  • 0층 0호 => 1층 0호 => 0층 1호 => 1층 1호
  • 0층 0호 => 0층 1호 => 1층 0호 => 1층 1호
  • 두 방식중 2번째 방식이 주소상 이동이 적음
  • 즉 행열에서 열 인덱스가 바뀔때 보다 행 인덱스가 바뀔때 더 많은 리소스 사용

문자열

• 문자열의 길이를 알 수 없는 경우 큰 배열을 사용하는 경우가 많음
• C는 문자열 전용 데이터 타입이 없음
  • 문자 배열이기에 1바이트를 나타내는 데이터 이름이 char가 됨
  • 길이를 저장하지 않음
  • 문자배열 마지막에 바이트를 추가하고 문자열 끝을 나타내는 NUL을 넣어 표기

단일 연결 리스트

• 연결 리스트(Linked list)는 목록에 들어갈 원소 개수를 모르는 경우 배열보다 더 잘 작동
• 리스트는 값과 next를 가지고 있음
  • next는 리스트의 다음 원소 주소를 저장하는 포인터
  • 리스트에서 맨 앞은 헤드, 마지막은 테일 이라고 표현
• 원소를 추가시키는 방법은 넣고자 하는 위치 전의 next를 새롭게 추가되는 곳에 연결

이중 연결 리스트

• 단일 연결 리스트의 경우 삭제 알고리즘이 복잡(삭제하려는 원소의 바로 앞 원소를 찾아야함)
• 이중 연결 리스트는 이전 원소에 대한 포인터도 들어 있는 리스트
• 노드당 부가비용은 증가 (이전 원소 포인터 추가로 인해)
• 리스트 전체를 방문하지 않아도 원하는 위치에 노드를 추가하거나 삭제 가능

가비지 컬렉션

• 동적 메모리를 명시적으로 관리하면서 포인터를 잘못 사용시 두가지 문제(메모리 접근 문제) 발생
• 포인터는 단지 메모리 주소를 나타내는 숫자
• 포인터를 사용해 존재하지 않는 메모리에 접근하거나 프로세서의 메모리 경계에 맞지 않는 주소에 접근시 에외가 발생하며 프로그램이 중단
• malloc(메모리 할당) 나 free(해제) 없이 동적 메모리 할당을 지원할 때 사용하는 시스템
• 언어의 런타임 환경이 변수 사용을 추적해서 사용하지 않는 메모리를 자동으로 해제

단점

• 프로그래머가 가비지 컬렉션을 제어 불가
• 중요한 일을 하는 도중 가비지 컬렉션 시스템이 작동되어 문제 발생
• 불필요한 참조가 남는 경우가 자주 있기에 메모리를 더 많이 사용

데이터베이스

• 정해진 방식으로 조직화된 데이터 모음
• DBMS (데이터베이스 관리 시스템)를 이용하여 정보 저장 및 읽기
• B트리 데이터 구조를 활용한 시스템
  • 균형 트리
  • 한쪽의 노드가 많아질 경우 분할하여 관리하는 트리
  • A-Z를 A-M // N-Z 로 관리하다 A-M이 모두 할당된 경우 A-G // H-M으로 분할

인덱스

• 데이터를 여러 가지 방법으로 접근할때 사용시 편리

  • 이름과 성을 기준으로 데이터 접근
  • 이름과 좋아하는 과일 기준으로 데이터 접근...

• 데이터가 바뀔 때마다 모든 인덱스를 갱신해야함

• 데이터 변경보다는 데이터 검색이 더 자주 벌어지기 떄문에 지불할만한 리소스

객체 지향의 함정

• 객체에는 함수에 해당하는 메서드와 데이터에 해당하는 프로퍼티가 존재
• 어떤 객체에 필요한 모든 데이터와 함수는 구조 안에 모여있음
• 정숫값 등 크기가 작은 데이터를 저장하는 프로퍼티는 객체 구조체 안에 들어감
• 메모리 할당이 필요한 프로퍼티는 객체 구조체 안에 있는 포인터를 통해 참조됨
• 객체는 전역적으로 알려진 함수 대신 자신이 사용할 메서드에 대한 포인터를 가지고 있어야함
• 따라서 객체 내의 데이터가 데이터만 저장하는 데이터 구조 처럼 짜여져 있지 않아 성능에 문제 발생