05. Group Anagram 결과 값 반환형

05. Group Anagram 결과 값 반환형

[rekyungmin]

hschong

키가 없을 경우라고 하셨는데, 없는 경우가 아니라 각각의 키가 최초 발생 시 key와 매핑되지 않아 empty list를 리턴합니다. 즉 key가 최초 발생시 리턴된 empty list와 key를 매핑 한다는 내용입니다.

먼저, 키가 없는 경우 발생한다는 것은 틀리지 않은 말입니다. 파이썬의 help를 이용해 확인하실 수 있습니다. defaultdict는 __getitem__에서 존재하지 않는 키를 발견했을 때 default_factory의 callable 객체를 호출하여 새로운 객체를 만들어내기 때문입니다.

>>> from collections import defaultdict
>>> help(defaultdict)
class defaultdict(builtins.dict)
 |  defaultdict(default_factory[, ...]) --> dict with default factory
 |
 |  The default factory is called without arguments to produce
 |  a new value when a key is not present, in __getitem__ only.
 |  A defaultdict compares equal to a dict with the same items.
 |  All remaining arguments are treated the same as if they were
 |  passed to the dict constructor, including keyword arguments.
 ...
 |  __missing__(...)
 |      __missing__(key) # Called by __getitem__ for missing key; pseudo-code:
 |      if self.default_factory is None: raise KeyError((key,))
 |      self[key] = value = self.default_factory()
 |      return value

이슈 작성자 분이 참조하신 문서의 "최초 발생" 말은 특정 예시를 설명하면서 나오는 말입니다. 틀린 말은 아니지만, 다음과 같은 예시에서는 혼동의 여지가 있을 것 같습니다.

>>> from collections import defaultdict
>>> a = defaultdict(list)
>>> a["first"].append("hello")
>>> del a["first"]
>>> a["first"]

"first" 는 최초 발생 이후 제거되었지만, 5번 라인에서는 default_factory 에 의해 list 객체를 생성합니다. 물론 제거하고 다시 키에 접근하면 최초 발생이라고 말할 수도 있습니다만, 읽는 사람에 따라 다르게 이해할 소지가 있다고 생각합니다.

[rekyungmin]

각설하고, 다시 본론으로 들어가보겠습니다.

결론부터 말하면 values() 메서드가 반환하는 객체의 타입은 typing.List가 아닙니다.

파이썬 알고리즘 인터뷰 책에서 파이썬의 표준 타입 계층도를 설명한 적이 있습니다. list는 가변 시퀀스 타입이라고 하였는데요, 그렇다면 list 는 무엇으로 가변 시퀀스 타입이라고 판단할 수 있을까요?

파이썬은 덕 타이핑입니다. 따라서 구현된 메서드와 속성을 통해 타입을 판단할 수 있습니다. 그렇다면 이슈 작성자분이 올린 values() 가 반환하는 객체가 List 타입인지 아닌지는 파이썬의 덕 타이핑을 이용해보면 되겠습니다. 파이썬에서는 abstract base class를 제공하여 덕 타이핑을 보완하고 있는데, 이것을 이용하여 간단하게 타입을 따져볼 수 있습니다.

만약 이슈 작성자분 말대로 values() 메서드가 list 타입을 반환한다면, MutableSequence 라고 부를 수 있는 메서드 또는 속성을 포함하고 있어야 합니다. 공식 문서의 Collections Abstract Base Classes를 통해서 MutableSequence가 가져야하는 메서드를 확인할 수 있습니다. MutableSequence는 __getitem__, __setitem__, __delitem__ 등과 같은 매직 메서드들을 가져야만 합니다. 하지만 이전 답변에서 뷰 객체에서는 인덱스 접근이 안 되었다는 것을 언급한 바가 있습니다. __getitem__ 매직메서드가 없다는 것인데, 코드로 확인해보겠습니다.

>>> from collections import defaultdict
>>> a = defaultdict(list).values()
>>> dir(a)
['__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__']

>>> b = list()
>>> dir(b)
['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

보다시피 defaultdict(list).values() 가 반환하는 객체는 MutableSequence가 가져야할 메서드를 포함하고 있지 않습니다. 따라서 MutableSequence라고 부를 수 없고, 그렇기 때문에 List 도 될 수 없습니다.

감사합니다.

[likejazz]

이런 열띤 토론 매우 유익하네요 ^^
괜찮으시다면 다른 분들도 좀 더 보실 수 있게 당분간 오픈 상태로 두도록 하겠습니다.

이 문제는 리턴 타입이 List[List[str]]이고, 가급적 이 타입을 맞춰야 겠죠.
물론 파이썬의 특성상 맞추지 않아도 오류가 나진 않습니다만 정확한 풀이라고는 할 수 없겠죠.

맨 처음에 제가 책에서 풀었던 방식은,
anagrams.values() 이고 이 경우 리턴 타입은 다음과 같습니다.

>>> anagrams.values()
dict_values([['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']])
>>> type(anagrams.values())
dict_values

원래 변수 anagrams는 딕셔너리인데, 여기서 값만 추출하고자 했고 이 경우 바로 List[List[str]]로 추출 될거라 예상했습니다. 당시에는 타입 확인 조차 하지 않았고, 실제로 리트코드에서도 문제 없이 풀이가 됩니다. 그러나 확인해보면 실제로는 List가 아니라 dict_values이기 때문에, 인덱스 조회도 되지 않는 등 List의 특징을 갖고 있지 않습니다. 말씀하신대로 __getitem__을 포함한 매직 메서드를 갖고 있지 않고 List가 아닙니다. (리트코드는 어떻게 결과를 검증했는지 모르겠네요)

이제 @rekyungmin 님이 제안해주신 대로 list()로 랩핑하게 되면 이 값이 List로 타입 변환됩니다.

>>> list(anagrams.values())
[['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
>>> type(list(anagrams.values()))
list

그리고 List내부의 값들도 List[str]로 변환되어 있음을 확인할 수 있습니다.

>>> type(list(anagrams.values())[0])
list
>>> type(list(anagrams.values())[0][0])
str

list() 함수는 deepcopy()처럼 내부의 값들도 모두 찾아서 변환해주는 것을 확인할 수 있습니다. 실제로 내부의 값들은 정상적인 List이고 당연히 List의 특징을 모두 갖고 있습니다. 보다 정확한 동작은 공식 문서나 코드를 꼼꼼히 살펴봐야 겠지만 이 문제의 경우 list(anagrams.values())로 하면 문제에서 요구한 리턴 타입을 정확히 맞출 수 있는 것은 분명해 보입니다.

아마 처음 의견 주신 분이 혼동하셨을거 같고, 저도 실험하기 전에는 잘 몰랐던 부분이라 많은 도움이 되었네요.
또한 앞서 두 분이 의견 주실때 공식 문서를 참조해서 의견을 피력하는 것도 매우 설득력 있는 좋은 주장 방식 같습니다.

앞으로도 좋은 내용 많이 올려주세요.
감사합니다.

[rekyungmin]

안녕하세요. 제가 올린 이슈에 관심을 가져주셔서 감사합니다.

저에게도 알림 메일이 와서, 책 저자분을 대신해 먼저 답변해보겠습니다.

먼저, 본문에서 참조하신 도큐먼트 내용부터 확인해보겠습니다.

defaultdict Examples
"When each key is encountered for the first time, it is not already in the mapping; so an entry is automatically created using the default_factory function which returns an empty list."

위 내용은 defaultdict(list) 에서 키가 없을 경우, default_factory 에 의해 빈 리스트가 반환된다는 것입니다. 다음과 같은 상황인 것이지요.

>>> a = defaultdict(list)
>>> isinstance(a["b"], list)
True

하지만, 제 이슈는 values() 메서드의 반환 타입의 문제를 논한 것입니다.

>>> a = defaultdict(list)
>>> isinstance(a.values(), list)
False

dict 의 values(), keys(), items() 메서드는 list가 아닌 view 객체를 반환합니다. 따라서 인덱스로 접근할 수 없고, list 객체와 비교 연산을 수행할 수 없으며, 원본 딕셔너리 내용이 변경될 경우 view 도 변경된 내용을 반영하는 등 몇 가지 특징들을 확인할 수 있게 되는 것입니다. 이것은 저의 개인적인 의견이 아니라 Python의 공식 도큐먼트에서 언급되는 내용입니다.

The objects returned by dict.keys(), dict.values() and dict.items() are view objects. They provide a dynamic view on the dictionary’s entries, which means that when the dictionary changes, the view reflects these changes.

여기를 참고하시면 도움이 되실 거라 생각합니다.

감사합니다.

안녕하세요.

영문해석의 차이가 서로 다른 의견을 가지게 된 것 같습니다.
"When each key is encountered for the first time, it is not already in the mapping; so an entry is automatically created using the default_factory function which returns an empty list. The list.append() operation then attaches the value to the new list."

키가 없을 경우라고 하셨는데, 없는 경우가 아니라 각각의 키가 최초 발생 시 key와 매핑되지 않아 empty list를 리턴합니다. 즉 key가 최초 발생시 리턴된 empty list와 key를 매핑 한다는 내용입니다.

처음에 제가 쓴 "key와 매핑되는 value 자체가 리스트입니다." 는 key와 매핑되는 value는 actual value가 아닌 default_factory에 의해 리턴된 엠티리스트 입니다.
defaultdict.values()때문에 value는 리스트라고 썼는데 이게 actual value와 헷갈릴 수는 있겠네요.

따라서 defaultdict.values()는 actual values를 리턴해 주는 것이 아니라 각각의 key와 매핑된 리스트 모두를 리턴합니다.
각각의 리스트 안에 actual values가 있으니 리턴 타입 List[List[str]]을 리턴합니다.

word = "eat"
anagrams_dic[''.join(sorted(word))]
print(anagrams_dic)
-> defaultdict(<class 'list'>, {'aet': []})
위의 예는 key('aet') 와 매핑되는 value(empty list) 입니다.

anagrams_dic[''.join(sorted(word))].append(word)
print(anagrams_dic)
-> defaultdict(<class 'list'>, {'aet': ['eat']})
key('aet')와 매핑되는 value(empty list)에 actual value('eat')가 추가 됩니다.

word = "tea"
anagrams_dic[''.join(sorted(word))]
print(anagrams_dic)
-> defaultdict(<class 'list'>, {'aet': ['eat', 'tea']})

도움 되셨으면 합니다.

저는 원문을 인용 했고 원문에 대해 가깝게 해석했습니다.

그리고 예문을 드시면서 "최초 발생"이 다르게 이해 할 소지가 있다고 하셨는데 원문의 내용은 개발자가 아닌 defaultdict 관점에서 설명한 것 입니다.

예를 드신 것 처럼 이 전에 발생했던 키를 지우고 동일한 키가 다시 발생하면 defaultdict는 이전에 지운 키를 기억하지 못하니 최초 발생인 겁니다. 기억하면 지운게 아니죠.

다만 개발자만 입력하고 지웠던 내용을 기억 할 수도 있을 뿐이죠. 따라서 defaultdict 입장에서 키가 최초 발생 시 라고 해석하는게 더 명확합니다.

그리고 help 함수 출력처럼
self[key] = value = self.default_factory()
제가 최초 언급한 value는 list라는 말은 맞습니다.

그런데 제 실수는 defaultdict.values() 함수는 모든 value를 리스트로 그룹핑해서 리턴하겠지라고 추측한 것입니다.
결론적으로 저는 틀렸고 답변이의 말대로 list(anagrams.values()) 가 맞습니다.

제가 파이썬 초보자다 보니 문서의 예제 일부분만 보고 view 오브젝트에 대한 이해 없이 defaultdict.values()를 추측한 것이 뼈 아프네요.

type()만 한 번 했어도 하는 아쉬움이 있지만, 실수를 통해서 많이 배우고 갑니다.
감사합니다.