chris3471 님의 블로그

B-tree- Designed to solve : simple index(검색할 수 있는 도구) 는 용량이 커서 Disk 비용이 많이 발생 (용량이 크면 메인 메모리에 load 불가능함으로) - 개선한 것 => B+ tree Statement of the Problem- binary searching (1) n값이 커질수록 O(log2 n)가 커짐 (실제로 사용하기 힘듦) (2) 항상 정렬되어 있어야 함 (항상 정렬하는 비용이 많이 발생) Indexing with Binary Search Trees장점 : (1) 데이터가 정렬되어 있지 않아도 됌 (2) 트리가 balanced state일 때 좋은 성능을 가짐 (3) insert cost = search cost (최악의 경우를 ..

Consequential 이란?- 2개의 파일- 어떠한 키에 대해서 sorted 되어있음- 교집합과 합집합을 찾기 위해 사용 ( 결과 파일은 그 키에 대해 정렬이 되어 있어야 함)- 교집합을 찾자!! 1. match를 찾아보자 ( 조건 : 효율적인 방법으로 찾아야 함, 중복된 key 값은 없음 )(1) 효율을 따지지 않는다면, 가장 간단한 방법은 List1 각 요소마다 List2의 모든 요소와 비교(2) 정렬이 되어 있으므로, List1의 첫 레코드와 List2의 첫 레코드를 비교 - 두 값이 동일하다면 결과 파일에 작성 - 그 다음 값들을 읽어옴 (CARTER, ANDERSON) - 두 키를 비교 했을 때, 같지 않으면 List2의 다음 요소를 읽어옴 (C > A이기 때문에) ..

Index란?- 어떻게 하면 빨리 찾을까? - 검색을 줄이기 위한 도구 ex) 학생 테이블을 주고 학생의 성적이 2.0이 안되는 학생을 다 찾아라 -> 민형이를 찾아라 관계 데이터 : 데이터와 데이터 간의 관계를 표현하는 데이터ex) 학생이 수강한 교과목 목록 Index안에는 Simple Index, B+ tree, hasing 등등 1. 간단한 인덱스 구조부터 살펴봄 - (key, reference fields) 쌍으로 이루어진 간단한 배열을 이용한 인덱스 - ex) 책의 인덱스, library card catalog 2. 고정 길이 or 가변 길이 레코드 파일에 인덱스를 어떻게 적용? 3. 이후 예시에서는 대규모 음반을 가정함 - 기본 키(primary key)는 label + ID 형식 (ex :..

Binary Search and Internal Sorting1. Sequential search - At most n comparisons -> O(n) - Too expensive -> keyed access를 다루기 위해 더 나은 방법을 찾아야함 2. Binary search - At most [log2 n] + 1 comparisons -> O(log n) - 단, 파일이 키 기준으로 정렬되어 있어야 함 3. Internal sort - RAM 안에 있는 디스크 파일을 읽어 정렬 (Disk 에서 RAM으로 데이터를 올린 후에 sort) ( 통째로 올려서 sort하는 방식) - 얼마나 적게 읽고 사용했는가? - 데이터가 많은 경우에는 유용하지 못하다 4. external sort..

삭제된 공간을 재활용 Data Compression (데이터 압축)1. 파일 사이즈가 작아짐 (1) 더 적은 공간을 사용해서 cost saving이 된다 (2) 접근 시간이 줄어들고 빠르게 전송 가능 (3) 순차적으로 빠르게 접근 가능 2. 단점은 별도의 인코딩, 디코딩 작업이 필요함 1. Using a Differnt Notation1. 압축 기법의 하나로, 더 간결한 표기를 찾아 비트 수를 줄이는 방식 (중복 제거(redundancy reduction)에 해당하는 압축 방식) ex) state : 2bytes -> 6bits 사용 50개의 데이터'L''A' -> 0'N''Y' -> 1...'C''Y' -> 49는 2^6 = 64개의 조합으로 모든 주를 표현 가능 2. Suppressing Re..

Record Keys1. Primary key - 키값이 존재한다면 유일한 레코드 값을 가져야 함 - 바뀔수가 없음 2. Secondary key - 레코드 값이 유일하지 않아도 됨 - ex) 이름, 도시 이름, 주소 등 3. Canonical form - 키의 형태를 통일된 형태로 변환을 하고나서 다룸ex) Ames, AMES, ames -> AMES로 변환 Sequential Search1. 순차 탐색 성능 평가 (1) read() 호출 수로 성능을 측정 - 파일에서 데이터를 읽는 read() 시스템 호출을 기준으로 성능을 평가 문제점 : 이 가정은 엄밀히 말하면 정확하지 않음 운영체제의 버퍼링(buffering) 덕분에 실제로는 성능이 더 나올 수 있음 (하지만 ..

Introduction1. Imperative languages는 폰 노이만 아키텍쳐의 추상 개념임   - Memory   - Processer 2. 변수들은 속성들로 특징화 되어있음  - type을 디자인 하기 위해서 scope, lifetime, type checking, initialization, and type compatibility를 고려 Names1. 고려사항 : 대소문자 구분, 예약어 or keywords 인지 아닌지 (예약어  ⊃  keywords) 예외) goto(Java)- 키워드 x- 예약어(reserved word) o goto(python)- 키워드 x- 예약어 x 2. 길이가 너무 짧으면, 함축적인 의미를 가질 수 없음 3. Special characters - PHP : 모..

사람 정보 저장 문제점- 사람 record 간에 구별이 되어있지 않음- record 안에서 field에 대한 구별이 되어있지 않음  File Organization- field : 논리적인 의미를 갖는 가장 작은 단위    - Fixed-length fields    - Variable-length fields         (1) Begin each field with a length indicator         (2) Separate the fields with delimiters         (3) Use  "keyword = value" expression to identify fields - record : field의 집합 (파일을 더 높은 수준의 조직체계로 볼 때 사용)    - Fix..

연역 추론- 일반적인 사실/이론 -> 구체적인 상황/예시- 특화 Specializationex) 모든 사람은 죽는다 + 소크라테스는 사람이다 -> 소크라테스는 죽는다 - 전문가 시스템 => 이론이 맞다면, 확실하게 옳은 결론을 내림귀납 추론- 구체적인 상황/예시 -> 일반적인 사실/이론- 일반화 Generalization - 머신 러닝 => 확실한 결론은 없고, 가능성에 기반한 결론을 내림   머신러닝이란 ?1. 지도 학습 (Supervised Algorithm) - 주어진 정답에 따라 학습하는 방법 2. 비지도 학습 (Unsupervised Algorithm) - 정답지 없이 데이터의 패턴 등을 학습하는 방법 - 클러스터링 (Clustering)  - 데이터 (Data)를 활용해 시스템을 개선해 나가는..

Symbolic AI 1. 탐색  (1) 맹목적 탐색  (2) 휴리스틱 탐색  (3) 게임 트리 탐색 2. 전문가 시스템   (1) 지식베이스  (2) 추론 엔진 3. 퍼지 이론 (일단 보류)4. 유전 알고리즘-------------------------------------------------------------------------------------------------------------진화 알고리즘 ( = 유전 알고리즘)1. 유전 알고리즘2. 유전 프로그래밍 ... 등을 포함 자연계에서의 진화 = 일종의 최적화 연산 (Optimization)- 적자생존 : 환경에 대한 적합도가 높은 개체가 살아남음- 자연선택(Selection) : 살아남은 개체의 특성이 후대에 유전- 돌연변이(Mutat..