자료구조 | chankoo

블룸 필터

2024-01-04

집합의 모든 값을 비트 배열에 저장한 자료형으로 특정 값이 집합에 속하는지 검사하는 용도로 쓰인다. m 비트 크기에 k 개의 서로 다른 해시함수를 사용해 구현한다. 해시 함수는 독립적이고 균일하게 분포해야한다. O(k) 시간에 새로운 값을 검사할 수 있다. k개 해시 모두 1인 경우 집합에 속하는 값이라 판단한다. 한정된 공간에서 집합이 커질 수록 긍정 오류(속하지 않으나 속한다고 판별)가 커지는 특성이 있지만, 부정 오류(속하는데 속하지 않는다 판별)는 발생하지 않아 1차적인 판별 알고리즘으로 많이 쓰인다.

Snowflake ID

2023-12-12 · 분산시스템

content 분산 시스템의 ID 생성 목적으로 트위터가 고안한 자료구조. 크기가 작고(8바이트) 특정 기술에 의존하지 않아 대용량 분산 시스템의 요구사항을 잘 만족시킨다. timestamp - 약 70년의 timestamp를 표현 가능. 생성 순으로 정렬 가능 instance - 장비의 고유 ID로 사용 seqence - 동일한 ms에 생성한 id에 순번을 매김. 즉, ms 마다 4097(2^12)개 id 생성 가능 refs Snowflake ID - Wikipedia 가상 면접 사례로 배우는 대규모 시스템 설계 기초 분산 처리 시스템에서 유일한 식별자를 만드는 방 …

로드 팩터

2023-12-01

content 해시 테이블에 저장한 데이터 개수 n을 버킷의 개수 k로 나눈 것(n/k) 로드 팩터가 높을수록 해시 테이블의 성능이 감소한다. 같은 버킷을 쓰는 데이터가 많아져 해시 테이블에서 탐색하는 시간이 늘어나기 때문이다. 따라서 언어별로 해시 테이블을 구현할때 로드 팩터의 임계치를 두고있으며, 임계치를 넘어설때 버킷의 수를 늘려 리해싱한다. (동적 배열의 메모리 재할당과 유사) refs links 해시 테이블 해시 충돌 Dynamic Array

LSM Tree

2023-11-21

Log Structured Merge Tree는 로그성 데이터 색인을 위해 고안된 자료구조로, 정렬된 키-값 데이터인 SS테이블(Sorted String Table) 형식으로 디스크에 데이터를 저장한다. refs 데이터 중심 애플리케이션 설계 색인(index)의 두 가지 형태 : LSM 트리 & B 트리 | by allocProc | Medium links B-Tree Hash 인덱스

B-Tree

2023-11-21 · mysql

BST(Binary Search Tree)를 일반화한 자료구조로 2개 이상의 자식 노드를 갖는 Balanced Tree이다. B Tree 류 자료구조는 DB 인덱스로 많이 쓰인다. (Balanced BST인)AVL Tree, RB Tree에 비해 자식 노드 개수가 많아 디스크 접근 수가 적음 블록 단위로 메모리에 적재하는 OS 특성도 효율적으로 활용 B Tree 인덱스의 성능은 키의 크기, 키의 카디널리티, 레코드 대비 인덱스 스캔의 범위 등 다양한 요소에 영향 받는다. 디스크 I/O로 데이터를 가져오는 단위인 블록의 크기는 고정(mysql은 16KB)인데, 키의 크 …

Python heapq

2022-11-18 · python

heap을 이용하는 q의 구현을 제공하는 모듈 heap = [] heapq.heappush(heap, item) heapq.heappop(heap) heappush 와 heappop 을 통해 힙 큐를 구현할 수 있다. 주의할 것은 heap 은 heap 자료구조가 아님. 선형 자료구조(ex. 리스트) 를 받아 힙의 구현을 도와주는 모듈임 최소 힙을 구현함 0을 제외한 인덱스로 읽지 말자 - heap[0] 을 제외한 값은 정렬된 형태가 아님 refs heapq — 힙 큐 알고리즘 — Python 3.12.0 문서 파이썬의 heapq 모듈로 힙 자료구조 사용하기 | …

해시 충돌

2022-10-16 · java python

(해시) 충돌은 1) 서로 다른 값이 동일한 해시를 뱉거나(해시 충돌) 2) 서로 다른 해시가 동일한 인덱스를 뱉는 경우를 말한다. 해시 자료구조를 구성할때 모든 key가 충돌한다면, 탐색에 O(n)이 걸린다. 모든 데이터가 하나의 인덱스에 저장(Separate Chaning)되거나 다른 인덱스에 순차적으로 저장(Open Addressing)될 것이기 때문이다. 저장할 값의 배열이 크지 않다면, Open Addressing 이 캐시 효율적이다. 연속된 공간에 저장한 데이터는 함께 캐싱될 것이고(cache line), spatial locality 에 따라 hit …

해시

2022-10-15

content 임의 길이 데이터를 해시 함수를 통해 변환한 값으로, 1) 길이가 고정이고 2) 변환 전 값을 구하는 역함수가 없다. refs links

해시 테이블

2022-10-15

해시를 이용해서 key: value 쌍을 저장하고 O(1) 에 value를 찾는 자료구조이다. 해시 함수를 통해 immutable 한 key에서 해시를 얻는다 크기를 고정한(n) 배열을 생성하고 해시를 인덱스(0~n-1)로 변환하여(보통 modulo 연산. 해시 % n) 배열의 인덱스에 키 밸류를 저장한다 리스트, 그래프 형태로(Separate Channing)로 저장하거나 인접한 다른 인덱스에 삽입(Open Addressing)한다. (해시) 충돌이 발생하면 최악의 경우 탐색에 O(n)이 걸린다. refs links 해시 해시 충돌

Generator

2022-10-12 · python

제너레이터는 제어 흐름을 양보할 수 있는 Iterator이다. 루프를 순회하는 도중 의도적으로 순회를 멈추고, 자신을 호출한 루틴으로 제어 흐름을 양보할 수 있다. 때문에 semicoroutine 이라고도 불리는데, (제어 흐름을 넘겨줄 routine을 지정할 수 있는) coroutine 의 특수한 형태이기 때문이다. 이러한 제너레이터의 동작은 1) 메모리 효율 2) 동시성 의 관점에서 살펴볼만하다. 루프 내 요소의 평가가 필요할때 메모리에 요소를 올리는 lazy evaluation 이고, 원하는 시점에 제어흐름을 넘겨가며 동시성 프로그래밍을 가능케하는 pseudo …

Iterator

2022-10-11 · 디자인패턴 python javascript java

특정 집합 객체 요소에 순차적으로 접근 가능하도록 구현해놓은 객체. Iterator 패턴을 따라서 내부를 노출하지 않고 집합 객체의 구현에 종속되지 않아야한다. Iterator 를 제공하는 객체는 Iterator Protocol 을 따랐다고 표현하는데, 이는 언어마다 상이하다. 에를 들어 javascript 에선 Iteration Protocol 하위에 Iteration Protocol 과 Iterator Protocol이 존재한다. 구현은 프로그래밍 언어마다 다양할 수 있다. 보통 Iterable 객체와 묶여서 구현한다. python과 java 모두 Iterable …

Dynamic Array

2022-10-03 · python

python 의 list 는 dynamic array이다. 런타임에 element를 추가할때, 리스트에 할당된 메모리 공간이 모자라면 리스트 크기를 늘린다. 그런데 dynamic array도 엄연한 array 이기에 ’element 가 연속된 메모리 공간을 점유한다’는 제약을 따라야한다. 그래서 python(cpython)은 요소가 추가되어 리스트 크기가 변해야할 때, 전체 list를 복사하여 더 큰(2의 거듭제곱) 공간에 통째로 재할당 한다. 이는 시간 복잡도 계산에 영향을 준다. list 에 요소를 더하는 append 나 insert 연산의 …