[파이썬(Python)] 자료 구조와 알고리즘(2)

자료 구조와 알고리즘(2)

 

• 이 포스팅은 Python Cookbook의 내용을 요약하여 작성되었습니다.
• 지적, 질문은 언제나 환영합니다.

 

1.6 딕셔너리의 키를 여러 값에 매핑하기

---

 

• 하나의 키에 하나의 값이 매핑된 것을 딕셔너리라 부른다.
• 키에 여러 값을 매핑하려면, 그 여러 값을 리스트나 세트와 같은 컨테이너에 저장해 두어야 한다.

 

d = {
    'a': [1, 2, 3],
    'b': [4, 5]
}

e = {
    'a': {1, 2, 3},
    'b': {4, 5}
}

 

• 이러한 딕셔너리를 쉽게 만들기 위해서 collections 모듈의 defaultdict을 사용한다.
• defaultdict에는 첫 번째 값을 자동으로 초기화하는 기능이 있다.

 

from collections import defaultdict

d = defaultdict(list)
d['a'].append(1)
d['a'].append(2) # d['a'] outputs [1, 2]
d['b'].append(3)

...
d = defaultdict(set)
d['a'].add(1)
d['a'].add(2)
d['b'].add(3)

 

• 다만 defaultdict를 사용할 때는 딕셔너리에 존재하지 않는 값이라도 한 번이라도 접근했던 키의 엔트리를 자동으로 생성한다.
• 이런 동작성을 피하고 싶다면 일반 딕셔너리의 setdefault를 사용할 수 있다.

 

d = {} #일반 딕셔너리
d.setdefault('a', []).append(1)
d.setdefault('a', []).append(2) # d['a'] outputs [1, 2]
d.setdefault('b', []).append(3)

 

1.7 딕셔너리 순위 유지

---

 

• 딕셔너리 내부 아이템의 순서를 조절하려면 collections 모듈의 OrderDict을 사용한다.
• 이 모듈은 삽입 초기의 순서를 그대로 기억한다.

 

from collections import OrderDict

d = OrderDict()
d['foo'] = 1
d['bar'] = 2
d['spam'] = 3
d['grok'] = 4

# Outputs "foo 1", "bar 2", "spam 3", "grok 4"
for key in d:
    print(ket, d[key])

 

• OrderDict는 내부적으로 더블 링크드 리스트(doubly linked list)로 삽입 순서와 관련 있는 키를 기억한다. 따라서 일반적인 딕셔너리에 비해 크기가 두 배이다.
• 새로운 아이템을 삽입하면 리스트의 제일 끝에 위치시킨다. 기존 키에 재할당을 해도 순서는 바뀌지 않는다.

 

1.8 딕셔너리 계산

---

 

• 딕셔너리에 주식 이름과 가격이 들어 있다고 가정해 보자.

prices = {
    'ACME': 45.23,
    'AAPL': 612.78,
    'IBM': 205.55,
    'HPQ': 37.20,
    'FB': 10.75
}

 

• min, max 등을 딕셔너리에 사용하면 키에 대해서만 작업이 이루어진다.
• 딕셔너리 값에 대한 계산을 하기 위해 키와 값을 zip()으로 뒤집어 줄 수 있다.
• 값이 같은 경우에는 비교 결과를 결정하기 위해 키를 사용한다. 중복된 값이 있으면 가장 작거나 큰 키를 가진 엔트리를 반환한다.

 

min_price = min(zip(prices.values(), prices.keys()))
# min_price는 (10.75, 'FB')

max_price = max(zip(prices.values(), prices.keys()))
# max_price는 (612.78 'AAPL')

prices_sorted = sorted(zip(prices.values(), prices.keys()))
# 값의 순서도 매길 수 있다.
# prices)sorted = [ (10.75, 'FB'), (37.2, 'HPQ'),
#                    (45.23, 'ACME'), (205.55, 'IBM'),                
#                    (612.78, 'AAPL')]

 

1.9 두 딕셔너리의 유사점 찾기

---

 

• 두 딕셔너리에서 유사점(동일한 키, 동일한 값)을 찾기 위해 keys()와 items() 메소드에 집합 연산을 수행할 수 있다.

 

a = {
    'x': 1,
    'y': 2,
    'z': 3
}

b = {
    'w': 10,
    'x': 11,
    'y': 2
}

# 동일한 키 찾기
a.keys() & b.keys() # {'x', 'y'}

# a에만 있고 b에는 없는 키 찾기
a.keys() - b.keys() # {'z'}

# (키, 값)이 동일한 것 찾기
a.items() & b.items() # {('y', 2)}

 

• 딕셔너리의 keys() 메소드는 키를 노출하는 키-뷰(key-view) 객체를 반환한다. 키 뷰에는 집합 연산 기능이 있다. 따라서 딕셔너리 키에 집합 연산을 수행하려면 집합으로 변환할 필요 없이 키-뷰 객체를 사용하면 된다.
• 딕셔너리의 items() 메소드는 (key, value) 페어 로 구성된 아이템-뷰(item-view) 객체를 반환한다. 이 객체는 집합 연산과 유사한 것을 지원한다.
• 이들과 유사한 values() 메소드는 집합 연산을 지원하지 않는다. 키와는 다르게 값-뷰은 유일하다는 보장이 없기 때문이다.

 

1.10 순서를 깨지 않고 시퀀스의 중복 없애기

---

 

• 중복을 없애려면 세트를 만드는 것이 가장 쉽지만, 이는 기존 데이터의 순서가 훼손된다.
• 시퀀스의 값이 해시(hash) 가능하다면 세트과 제너레이터(generator)를 사용해서 쉽게 해결 가능하다.

 

def dedupe(items):
    seen = set()
    for item in items:
        if item not in seen:
            yield item
            seen.add(item)

 

이 함수는 다음과 같이 사용할 수 있다.

 

>>> a = [1, 5, 2, 1, 9, 1, 5, 10]
>>> list(dedupe(a))
[1, 5, 2, 9, 10]

 

• 해시 불가능한 타입(ex. dict)의 중복을 없애려면 수정이 필요하다.
• key 인자는 중복 검사를 위해 함수가 시퀀스 아이템을 해시 가능한 타입으로 변환한다고 명시하는 데에 목적이 있다.

 

def dedupe(items, key=None):
    seen = set()
    for item in items:
        val = item if key is None else key(item)
        if val not in seen:
                yield item
                seen.add(val)

>>> a = [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y' : 4}]
>>> list(dedupe(a, key=lambda d: (d['x'], d['y'])))
[{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
>>> list(dedupe(a, key=lambda d: d['x']))
[{'x': 1, 'y': 2}, {'x': 2, 'y': 4}]

 

1.11 슬라이스 이름 붙이기

---

 

• 프로그램 코드에 슬라이스를 지시하는 하드코딩이 너무 많아 이해하기 어려울 경우에, 의미 없는 하드코딩에 이름을 붙여 이후에 이해하기 쉽게 만들 수 있다.
• 내장 함수인 slice()는 슬라이스를 받는 모든 곳에 사용할 수 있는 조각을 생성한다.

 

>>> items = [0, 1, 2, 3, 4, 5, 6]
>>> a = slice(2, 4)
>>> items[2:4]
[2, 3]
>>> items[a]
[2, 3]
>>> items[a] = [10, 11]
>>> items
[0, 1, 10, 11, 4, 5, 6]
>>> del items[a]
>>> items
[0, 1, 4, 5, 6]

 

• slice 인스턴스 s가 있다면 s.start와 s.stop, s.step 속성을 이용해서 더 많은 정보를 얻을 수 있다.

 

>>> a = slice(10, 50, 2)
>>> a.start
10
>>> a.stop
50
>>> a.step
2

 

• indices(size) 메소드를 이용하면 특정 크기의 시퀀스에 슬라이스를 매핑할 수 있다.
• 이렇게 하면 튜플(start, stop, step)을 반환하는데, 모든 값은 경계를 넘어서지 않도록 제약이 걸려 있다.

 

>>> s = 'HelloWorld'
>>> a.indices(len(s))
(5, 10, 2)
>>> for i in range(*a.indices(len(s))):
...        print(s[i])
...
W
r
d

 

1.12 시퀀스에 가장 많은 아이템 찾기

---

 

• collections.Counter 클래스를 사용하면 쉽게 해결할 수 있다.
• 가령, 단어가 들어 있는 리스트에서 가장 자주 나타나는 단어를 찾아보자.

 

words = ['look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes',
        'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around', 'the',
        'eyes', "don't", 'look', 'around', 'the', 'eyes', 'look', 'into',
        'my', 'eyes', "you're", 'under']

from collections import Counter
word_counts = Counter(words)
top_three = word_counts.most_common(3)
print(top_three)
# [('eyes', 8), ('the', 5), ('look', 4)] 출력

 

• Counter 객체에는 해시 가능한 모든 아이템을 입력할 수 있다.
• 내부적으로 Counter는 아이템이 나타난 횟수를 가리키는 딕셔너리이다.
• 카운트를 수동으로 증가시키고 싶다면 단순하게 더하기를 사용한다.
• Counter 인스턴스는 여러 가지 수식도 사용 가능하다.

 

>>> morewords = ['why', 'are', 'you', 'not', 'looking', 'in', 'my', 'eyes']
>>> for word in morewords:
...        word_counts[word] += 1
...     
>>> word_counts['eyes']
9
>>> word_counts.update(morewords) # 혹은 update() 메소드 사용 가능

 

1.13 일반 키로 딕셔너리 리스트 정렬

---

 

• 딕셔너리 리스트가 있고, 하나 혹은 그 이상의 딕셔너리 값으로 이를 정렬하고 싶을 때 operator 모듈의 itemgetter 함수를 사용하면 쉽게 정렬할 수 있다.

• itemgetter() 함수에는 키를 여러 개 전달할 수도 있다.

 

rows = [
    {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003},
    {'fname': 'David', 'lname': 'Beazley', 'uid': 1002},
    {'fname': 'John', 'lname': 'Cleese', 'uid': 1001},
    {'fname': 'Big', 'lname': 'Jones', 'uid': 1004}
]

from operator import itemgetter

rows_by_fname = sorted(rows, key=itemgetter('fname'))
rows_by_uid = sorted(rows, key=itemgetter('uid'))

print(rows_by_fname)
print(rows_by_uid)
# [
#    {'fname': 'Big', 'uid': 1004, 'lname': 'Jones'},
#    {'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'},
#    {'fname': 'David', 'uid': 1002, 'lname': 'Beazley'},
#    {'fname': 'John', 'uid': 1001, 'lname': 'Cleese'},
# ]

# [
#    {'fname': 'John', 'uid': 1001, 'lname': 'Cleese'},
#    {'fname': 'David', 'uid': 1002, 'lname': 'Beazley'},
#    {'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'},
#    {'fname': 'Big', 'uid': 1004, 'lname': 'Jones'},
# ]

# 키 여러 개 전달하기
rows_by_lfname = sorted(rows, key=itemgetters('lname', 'fname'))
print(rows_by_lfname)

# [
#    {'fname': 'David', 'uid': 1002, 'lname': 'Beazley'},
#    {'fname': 'John', 'uid': 1001, 'lname': 'Cleese'},
#    {'fname': 'Big', 'uid': 1004, 'lname': 'Jones'},
#    {'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'},
# ]

 

• 키워드 인자 key를 받는 내장 함수 sorted()에 rows를 전달했는데, 이 인자는 rows로부터 단일 아이템을 받는 호출 가능 객체를 입력받고 정렬의 기본이 되는 값을 반환한다.
• itemgetter() 함수는 그런 호출 가능 객체를 생성한다.
• operator.itemgetter() 함수는 rows 레코드에서 원하는 값을 추출하는 데 사용하는 인덱스를 인자로 받는다. 객체의 __getitem__() 메소드에 넣을 수 있는 모든 값이 가능하다.
• itemgetter에 여러 인덱스를 전달하면, 생성한 호출 가능 객체가 모든 요소를 가지고 있는 튜플을 반환한다. sorted()가 튜플의 정렬 순서에 따라 결과의 순서를 잡는다.
• itemgetter()의 기능을 lambda 표현식으로 대체할 수 있다. 실행 속도는 itemgetter가 조금 더 빠르다.
• 이 내용은 min()과 max()와 같은 함수에도 적용 가능하다.