스터디 6주차

객체지향의 함정
정렬
해시효율성과 성능

1. 객체지향의 함정

객체지향프로그래밍은 c++ 를 통해 본격적으로 널리 사용되기 시작했습니다.
객체에는 함수에 해당하는 매서드와 데이터에 해당하는 프로퍼티가 들어있습니다.

객체에 필요한 데이터와 함수는 한 데이터 구조 안에 모여 있습니다.
c는 타입캐스팅과 함수를 가리키는 포인터를 지원합니다.

property1은 처럼 크기가 작은 데이터를 저장하는 프로퍼티는 객체 구조체에 할당됨.
property2 같이 메모리 할당이 더 필요한 프로퍼티는 포인터를 통해 참조됨

메서드를 별도의 데이터 구조에 나눠 담아 구조체가 커지는 것을 막는다.

객체는 전역적으로 알려진 함수 대신에 자신이 사용할 메서드에 대한 포인터를 가지고 다녀야 한다.
객체 내의 데이터가 데이터만 저장하는 데이터 구조 처럼 꽉짜여 있지 않다.
성능이 결정적으로 중요할 때는 전통적인 배열을 활용하는 것을 추천한다.

2. 정렬

데이터를 정렬 해서 저장하면 메모리 접근 횟수를 줄임으로써 검색을 빨리 끝낼 수 있다.

정렬대상이 포인터 크기보다 크다면 데이터를 직접 정렬하는 대신 데이터를 가리키는 포인터를 재배열 하는 방식으로 정렬해서 데이터 가체가 여기저기로 움직이지 않게 해야한다.

정렬은 숫자의 대소 구분으로 산술적인 비교를 통해 결정을 내릴 수 있다.
이건. 포트란 프로그래밍 언어에서 비롯되었다.

• 포트란 프로그래밍

IF(식) 분기1, 분기2, 분기3

IF문을 계산한 후
결과가 0 보다 작으면 분기1를 실행
0과 같으면 분기2를 실행
0보다 크면 분기3를 실행

• qsort 라이브러리
  유닉스 버전 Ⅲ부터 퀵정렬 알고리즘을 구현한 qsort라는 라이브러리 함수가 도입되었다.
  이 qsort함수는 데이터를 정렬하는 방법은 알고 있지만 데이터를 비교하는 방법은 모르기때문에, c언어의 함수 포인터를 활용하여 비교를 한다.
  
  

• Strcmp
  Strcmp는 qsort를 염두해두고 작성되었다.
  두 문자열의 전번째 부터 차례로 방문하면서 한 문자에서 다른 문자를 빼는 방식으로 구현된다.
  뺄셈 결과가 0이면 다음 문자, 0이 아니면 뺄셈결과를 반환하고,
  이 과정을 반복하다가 문자열 끝에 도달하면 0을 반환한다.

문자열 정렬
아스키로 표현한 문자열 정렬은 알고리즘이 잘 작동한다.
다른 언어(자연어)를 지원하게 되면서 아스키 문자만 수치적인 비교순서를 제공하거나 언어에 따른 정렬 규칙이 달라지는 부작용이 생겼다.

3.해시

앞선 방식들보다 성능이 더 좋은 접근 방법이다.
해시 함수는 계산하기 쉽고 각 키를 벽에서 유일한 위치에 뿌려준다면, 검색을 아주 빠르게 할 수 있다.
해시함수의 결과값을 사용해 키에 대응하는 데이터를 메로리에 저장할 수 있다.
해시함수는 메모리 크키보다 작은 범위의 값을 만들어야 한다.
데이터 값이 크거나 너무 많이 사용할 경우, 데이터가 여기저기 흩뿌려저 있어 메모리 접근성이 떨어질 수 있다.

• 해시 테이블
  해시함수의 결과를 배열 인덱스로 활용하는 방법이 이다.
  각 원소를 버킷이라고 한다.
  

좋은 해시 함주란?
계산하기 쉬워야한다.
키를 골고루 뿌려줘야 한다.

해시테이블 인덱스 최댓값보다 커지는 함수 해결법
함수 합계를 해시 테이블 크기로 나눈 나머지를 사용하면 쉽게 이 분제를 해결 할 수 있다.

만약 해사ㅣ태이블 크기 11라면 문잣값을 모두 더한 값이 골고루 분포하기 위해서는 해시 테이블 크기를 소수로 만들면 좋다.

해 테블을 이용하여 노래 제목을 저장한 것인데 "Alligator" 와"scarlet" 이 충돌된 상태이다.

이경우 해시 채인으로 해결할 수 있다.

• 해시 채인 관리
  충돌이 났을 경우 삽입을 빠르게 하기 위해 체인 앞에 원소를 추가 할수 있다.
  삽입에 시간이 더 걸리지만, 검색시 채인을 다 뒤질 필요가 없어진다.
  체인길이를 추적하다가 체인이 길어지면 해시테이블을 확장할수 있는데, 이럴 경우에는 테이블 확장으로 얻을 이익이 더 크므로 연장하는 것이 좋다.

• 해시 충돌 처리 방법
  해시테이블에 빈 슬롯을 찾는 알고리즘을 사용하여 해시 체인을 없앨 수 있다.

• 완전 해지
  각 키를 유일한 버킷에 연결해준다.
  모든키를 알고 있지 않다면 완전한 해시 함수를 만들기는 거의 불가능하다.
  

4.효율성과 성능

덜 효율적인 알고리즘을 돌려도 더 많은 프로세서를 사용하면 좋은 성능을 얻을 수 있다.

• 샤딩(수평 파티셔닝)
  성능와 효율이 분리된 상황을 응용하는 데이터 베이스.
  데이터 베이스를 각각의 기계에서 실행되는 여러 샤드로 나누는 방식을 말한다.
  
  인터페이스를 통해 요청이 들어온 데이터 베이스 연산을 모든 샤드에 전달한다.
  컨트롤러가 결과를 하나로 모은다.
  이 작업은 동시에 병렬적으로 작업을 수행 하여 성능이 향상된다.

• 맵리듀스(Map Reduce)
  샤딩의 변종으로 근본적으로 컨트롤러가 중간 결과를 모으는 방법을 코드로 작성 할 수 있게 해준다.

다중 프로그램을 사용하는 방식을 다른 분야에서도 응용할 수 있다.
대표적으로 전자프론디어 재단에서 만들었던 DES(Data Encryption Standard) 암호 해독 프로그램이 있다.