[파이썬 알고리즘 인터뷰] 배열

 

github.com/onlybooks/algorithm-interview

 

자료구조는 크게 메모리 공간 기반 연속 방식과 포인터 기반 링크방식으로 나뉘고 배열은 여기서 연속방식의 가장 기본이 된다.

 

더블링: 미리 초깃값을 작게 잡아 배열을 생성한 뒤 데이터가 꽉 채워지면 늘려주고 복사

 

파이썬의 더블링은 cpython/Objectslistobject.c에 정의되어 있음.

new_allocated = (size_t)newsize + (newsize>>3)+newsize<9?3:6); 으로 기술되어있으며 0,4,8,16,25,35,46,58... 로 증가

 

이러한 재할당 비율은 그로스 팩터, 성장인자라고 하며 초반에는 2배씩늘려가나 전쳊거으로는 약 1.125배로 다른 언어에 비해 다소 조금씩 증가함(자바 1.5배, cpp,ruby:2배)

 

여기서 잠깐 파이썬의 데이터 타입 차이 알아보기

 

• list: 순서와 인덱스가 존재, mutable
• tuple: 순서만 존재, immutable
• dict: key,value로 구성, 중복 불가
• set:key로 구성, 중복 불가

그리고 지난번에 이미 알아봤듯이 weejw.tistory.com/459?category=934475 list,dic,set을 제외하면 모두 불변이다.