python 의 공식 repo 를 참고하여 collections 모듈의 Counter 의 사용법 및 구현 원리를 알아보고자 합니다.

Counter 내부 구현 원리

1. 객체 생성

Counter 는 dict 를 상속하는 클래스로써 hashable한 item들을 count하는 역할을 합니다.
따라서 dict가 가지는 속성도 가지고 있으며, 필요한 경우 오버라이딩하거나 확장한 것이 Counter 클래스라는 것을 알 수 있습니다. Counter 클래스의 입맛(?) 에 맞게 오버라이딩하거나 추가한 메소드들은 2번 목차에서 다루겠습니다.

class Counter(dict):
    	...

Counter 객체는 다양한 파라미터를 통해 생성될 수 있습니다.

c = Counter()  
# 비어있는 Counter
c = Counter('gallahad')   
# iterable로부터 Counter를 생성
c = Counter({'a': 4, 'b': 2}) 
# mapping으로부터 Counter 생성
c = Counter(a=4, b=2)  
# 위와 동일한 결과로, keyword args로 생성

이는 Counter class의 init 함수를 보면 다음과 같이 파라미터를 받을 수 있게 구현이 되어있기 때문입니다.

 def __init__(self, iterable=None, /, **kwds):
        super().__init__()
        self.update(iterable, **kwds)

2. Counter의 overriding

앞서 Counter 클래스가 dict를 상속하여 오버라이딩하거나 확장한 함수들을 가지고 있다고 했는데요,
주어진 각 객체들의 갯수를 세는 것이 Counter 클래스의 주된 역할이라는 것을 생각하면 각 함수들이 왜 이렇게 오버라이딩이 되었는지 자연스럽게 이해가 됩니다. 대표적인 몇가지 오버라이딩 사례를 보도록 하겠습니다.

update

위 __init__ 에서 나왔던 update 함수를 좀더 자세히 볼까요?
여기서의 update은 dict의 update과 유사하나 같은 key에 대해서 각 count값을 대체하는 것이 아니라 추가하는 것이 차이점입니다. 아무래도 replace보다는 기존의 count 값에 추가를 하는 것이 Counter 클래스의 역할상 더 직관적이기 때문입니다. ("이 단어가 최종적으로 몇번이나 나왔는가?" 가 궁금한 거니까요)

구현 로직을 보면 dictionary 형태로 주어진 파라미터는 기존의 count에 추가하고 있으며, 그 외에 list 형태로 주어진 경우 _count_elements 함수로 각 요소의 출현 횟수를 세고 있습니다.

 def update(self, iterable=None, /, **kwds):
	 if iterable is not None:
            if isinstance(iterable, _collections_abc.Mapping):
                if self:
                    self_get = self.get
                    for elem, count in iterable.items():
                        self[elem] = count + self_get(elem, 0)
                else:
                    # fast path when counter is empty
                    super().update(iterable)
            else:
                _count_elements(self, iterable)
        if kwds:
            self.update(kwds)

_count_elements 함수는 이 Counter 함수가 dict를 상속했다는 특징 상 get 함수를 가지고 있기 때문에 자기 자신이 mapping 이 되고, iterable로부터 요소들이 등장할 때마다 1씩 증가시키고 있음을 알 수 있습니다.

def _count_elements(mapping, iterable):
    mapping_get = mapping.get
    for elem in iterable:
        mapping[elem] = mapping_get(elem, 0) + 1

most_common

가장 많이 등장한 요소부터 n번째로 많이 등장한 요소까지 return하는 함수입니다.
n이 주어지지 않은 경우 단순히 item들을 등장 횟수 순으로 내림차순 정렬 후 return 하고 n 이 주어진 경우 heapq를 활용하고 있습니다. self.items() 를 heapq 에 넘기고 있기 때문에 각 key와 해당 key가 등장한 횟수인 value의 쌍들이 list로 반환될 것을 예상할 수 있습니다.

def most_common(self, n=None):
        # Emulate Bag.sortedByCount from Smalltalk
        if n is None:
            return sorted(self.items(), key=_itemgetter(1), reverse=True)

        # Lazy import to speedup Python startup time
        import heapq
        return heapq.nlargest(n, self.items(), key=_itemgetter(1))

fromkeys

dict를 생성할 때는 fromkeys 메소드를 통해 편리하게 key들의 목록을 넘겨 딕셔너리를 생성하기도 하는데요, Counter의 경우엔 사용자가 직접 어떤 key에 대한 value를 수동으로 넣어주는 경우를 방지해야합니다. value는 무조건 key의 등장 횟수에 따라서만 결정되어야하기 때문입니다. 예를 들면 Counter.fromkeys('aaabbc', v=2) 와 같이 딕셔너리를 생성하면 a가 2번 등장했다는 이상한 데이터가 들어가게 되죠. 따라서 Counter 클래스는 fromkeys 함수를 호출시 아래와 같이 아예 NotImplementedError를 내뱉습니다.

@classmethod
    def fromkeys(cls, iterable, v=None):
        raise NotImplementedError(
            'Counter.fromkeys() is undefined.  Use Counter(iterable) instead.')

Counter 활용 예시

스트링 s가 알파벳 소문자('a'~'z')로 이루어져 있고, 가장 많이 쓰인 알파벳을 반환하는 solution 함수를 구현하시오.
단, 가장 많이 쓰인 알파벳이 2개 이상이면 알파벳 순서대로 스트링을 이루어 반환할 것.

def solution(s):
	# s= "aabbcdd"
    c = Counter(s.lower())
    # Counter가 문자열(iterable)로 초기화(__init__)되면서 내부적으로 update를 호출하여 각 letter와 등장횟수를 key,value로 가지고 있는 상태
    # Counter({'a': 2, 'b': 2, 'c': 1, 'd': 2})
    mc = c.most_common(1)[0][1]
    # [('a',2)] 에서 2를 추출 
    mc_words = [letter for letter, val in c.items() if val == mc]
    mc_words.sort()
    # 2와 동일한 값을 가지는 value의 key들을 모아서 알파벳 순으로 sort 
    return ''.join(mc_words)
    # abd

Counter의 most_common 함수는 n이 주어졌을 때 heapq.nlargest(n, self.items(), key=_itemgetter(1)) 를 통해 n개의 가장 큰 값을 가진 쌍들의 list을 반환했었죠. 따라서 most_common에서 반환된 값에서 등장 횟수만 뽑아 내기 위해 [0][1]과 같은 index 를 사용할 수 있습니다.

참고 🚩

만약 위 예제를 조금 변형해서 특정 알파벳의 순서를 앞당기고 싶다면 어떻게 할까요?
이 경우 단순히sort() 를 호출하는 것으로는 원하는 결과를 얻을 수 없겠죠. 이럴 때 저는 sort 의 기준을 별도로 만들기 위해 각 알파벳에 대한 별도의 우선순위를 value로 준 dict를 만들었습니다.
(더 좋은 의견이 있으시면 말씀해주세요! 😀)

코드는 다음과 같습니다. 'd'의 우선순위가 높을 때의 예제입니다.

def solution(s):
    # s= "aabbcdd"
    c = Counter(s.lower())
    mc_words = [letter for letter, val in c.items() if val == c.most_common(1)[0][1]]
    mc_words.sort()
    # 여기까지는 동일

    words = dict(zip(mc_words, range(len(mc_words))))
    # {'a': 0, 'b': 1, 'd': 2}
    
    for word in words.keys():
        if word == 'd':
            words['d'] = -1
    # {'a': 0, 'b': 1, 'd': -1}

    answer = ''.join(k for k, v in sorted(words.items(), key=itemgetter(1)))
    return answer
    # dab

이는 참고로 앞서 언급한 Counter의 most_common에서 첫번째 index에 있는 값을 기준으로 정렬하는 아래 부분을 보고 힌트를 얻었습니다.

if n is None:
      return sorted(self.items(), key=_itemgetter(1), reverse=True)