<리스트, 딕셔너리>
1. 리스트
- 입력순서 유지, 동적 배열로 구현됨
표 5-2 리스트의 주요 연산 시간 복잡도
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| len(a) | O(1) | 전체 요소의 개수를 리턴한다 |
| a[i] | O(1) | 인덱스 i의 요소를 가져온다 |
| a[i:j] | O(k) | i부터 j까지 슬라이스의 길이만큼 k개의 요소를 가져온다. 이 경우, 객체 k개에 대한 조회가 필요하므로 O(k) 이다. |
| elem in a | O(n) | elem 요소가 존재하는지 확인한다. 처음부터 순서 탐색이므로 n만큼 시간이 소요된다. |
| a.count(elem) | O(n) | elem 요소의 개수를 리턴한다 |
| a.index(elem) | O(n) | elem 요소의 인덱스를 리턴한다. |
| a.append(elem) | O(1) | 리스트 마지막에 elem 요소를 추가한다. |
| a.pop() | O(1) | 리스트 마지막 요소를 추출한다. 스택의 연산이다. |
| a.pop(0) | O(n) | 리스트 첫 번째 요소를 추출한다. 큐의 연산이다. 이 경우 복사가 필요하므로 O(n)이다. 큐이 연산을 주로 사용한다면 리스트보다는 O(1)에 다능한 데크를(deque)를 권장. |
| del a[i] | O(n) | i에 따라 다르다. 최악의 경우 O(n) 이다. |
| a. sort() | O(nlogn) | 정렬한다. Timsort를 사용하면 최선의 경우 O(n)에도 실행될 수 있다. |
| min(a), max(a) | O(n) | 최솟값, 최댓값을 계산하기 위해서는 전체를 선형탐색 해야한다. |
| a.reverse() | O(n) | 뒤집는다. 리스트는 입력 순서가 유지되므로 전체를 뒤집게 되면 입력 순서가 반대로 된다. |
| 제목 없음 |
- 리스트의 경우 탐색 시 값의 존재 유무를 확인하려면 이진 검색이 효율적이지만, 매번 정렬이 필요하고 대부분의 리스트는 정렬된 상태가 아니므로 리스트의 경우 모든 elem을 순차적으로 조회하는 형태로 구현되어 있다. 이 경우 최악의 경우 항상 O(n)이 소요된다.
리스트의 활용 방법
- insert() : 특정 위치의 인덱스를 지정해 요소를 추가
- a.insert(3,5) : 3번째 인덱스에 5를 삽입
- 동적 배열에 삽입할 수 있는 자료형을 동일한 타입으로 제한하는 다른 언어에 비해 파이썬은 자유롭게 삽입이 가능하다(숫자,문자,볼 등)
- Slicing 기능이 있어 특정 범위 내의 값을 매우 편리하게 조작 가능하다.
- IndexError : 인덱스가 리스트의 길이를 넘어설 때 발생
- 예외처리
try:
print(a[9])
except indexError:
print("존재하지 않는 인덱스")
- del 키워드 : 인덱스의 위치에 있는 요소 삭제
- del a[1]
- remove() 함수 : 값에 해당하는 요소 삭제
- a.remove(3)
- pop() 함수 : 스택의 pop 연산처럼 추출로 처리됨. 삭제될 값을 리턴하고 삭제가 진행된다.
- a.pop(3)
리스트의 특징
- 리스트는 연속된 공간에 요소를 배치하는 배열의 장점 + 다양한 타입을 연결해 배치하는 연결 리스트의 장점을 모두 취함
- Cpython에서 리스트를 정의한 헤더
typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t_allocated;
}PyListObject;
- 요소에 대한 포인터 목록(ob_item)을 갖고있는 구조체
- 리스트는 객체로 되어있는 모든 자료형을 포인터로 연결한다.
- 객체에 대한 포인터 목록을 관리하는 형태로 구현되어 있다.
- 자료형의 크기는 각각 다르기 때문에 리스트는 연속된 메모리 공간에 할당하는 것이 불가능.
- 각각의 객체에 대한 참조로 구현할 수 밖에 없다.
- 포인터의 위치를 찾아 타입 코드를 확인하는 등의 추가 작업이 필요하므로 속도면에서 불리하다.
2. 딕셔너리
- 키/값 구조로 이루어짐
- Python 3.7 이상부터 순서가 유지된다.
- 내부적으로 해시 테이블(Hash Table)로 구현되어 있다.
- 문자를 포함해 다양한 타입을 키로 사용 가능.
- 해싱 : 객체를 키로 사용하는 것.
- 해시 테이블을 이용해 자료를 저장한다.
- 다양한 타입을 지원하면서도 입력과 조회 모두 O(1)에 가능함
- 분할 상환 분석(Amortized Analysis)에 따른 시간 복잡도는 O(1)
표 5-4 딕셔너리의 주요 연산 시간 복잡도
| 연산 | 시간 복잡도 | 설명 |
|---|---|---|
| len(a) | O(1) | 요소의 개수를 리턴한다. |
| a[key] | O(1) | 키를 조회하여 값을 리턴한다. |
| a[key]=value | O(1) | 키/ 값을 삽입한다 |
| key in a | O(1) | 딕셔너리에 키가 존재하는지 확인한다. |
- 위와 같이 딕셔너리는 대부분의 연산이 O(1)에 처리 가능한 매우 우수한 자료형이다.
- 대부분의 언어에서 해시 테이블을 이용한 자료형은 입력 순서가 유지되지 않는다.
- Python 3.6 이하 버전에서는 입력 순서가 유지되지 않아 collections.OrderedDict() 라는 별도의 자료형을 제공함.
- Python 3.7 부터 내부적으로 인덱스를 이용해 입력 순서를 유지하도록 개선됨.
딕셔너리의 활용 방법
- KerError : 존재하지 않는 키를 조회하는 경우 발생 + 키를 삭제할 때 발생 가능.
- Try 구문 예외처리
try:
print(a['key4']
except KeyError:
print("존재하지 않는 키")
- 예외처리를 하지 않고 키가 존재하는지 미리 확인 후 작업 진행도 가능하다
if 'kry4' in a:
print('존재하는 키')
else:
print('존재하지 않는 키')
- items() 매소드 : 키와 값을 각각 꺼내올 수 있다.
for k,v in a.items():
print(k,v)
>>> key1 valu1
>>> key2 value2
>>> key3 value3
- del a['key1'] : 딕셔너리의 키 삭제
딕셔너리 모듈
딕셔너리와 관련된 특수한 형태의 컨테이너 자료형
defaultdic,Counter,OrderedDict
defaultdict 객체
- 디폴트값을 기준으로 해당 키에 대한 딕셔너리 아이템을 생성해준다.
- KeyError는 발생하지 않음
- collections.defaultdict 클래스를 갖는다.
a=collection.defaultdic(int)
a['A']=5
a['B']=4
a
>>a
defaultdict(<class 'int'>,{'A':5,'B':4)
a['C']+=1 # 존재하지 않는 키
>>>a
defaultdict(<class 'int'>,{'A':5,'B':4,'C':1})
- 디폴트인 0을 기준으로 자동으로 생성한 후 여기에 1을 더해 최종적으로 1이 만들어진다.
Counter 객체
- Counter 객체는 아이템에 대한 개수를 계산해 딕셔너리로 리턴한다.
- 키에는 아이템의 값을, 값에는 해당 아이템의 개수가 들어간다.
- 딕셔너리를 래핑(Wrapping)한 collections.Counter 클래스를 갖는다.
a=[1,2,3,4,5,5,5,6,6]
b=collections.Counter(a)
b
>>>Counter({5:3,6:2,4:1,3:1,2:1,1:1})
type(b)
>>><class 'collections.Counter'>
- 개수를 자동으로 계삼하여 매우 편리하다.
- most_common() 을 사용하여 가장 빈도수가 높은 요소 추출 가능
b.most_common(2) # 빈도수가 가장 높은 2개의 요소 추출
>>>[(5,3),(6,2)]
OrderedDict 객체
- 3.6 이하에서는 순서가 유지되지 않으므로 OderedDict 객체를 사용
collections.OrderedDict({'banana':3,'apple':4,'per':1,'orenge':2})- 위와 같이 입력값을 부여할 경우 입력 그대로 순서가 유지된다.
Uploaded by Notion2Tistory v1.1.