파이썬 후드 아래

A deep dive into sortedcontainers Source Code

약 1년전쯤 아마존베를린의 폰화면에서 이question를 해결했습니다. 그러나 최적의 시간 복잡성이 없습니다. 그 이후로 어떻게 하면 더 잘할 수 있을지 여러 번 고민했습니다.

오늘은 리트코드의 데일리 챌린지에서 다시 만났습니다.

누락된 부분은 당시 나에게 알려지지 않은 데이터 구조인 Sorted Dictionary라는 것이 밝혀졌습니다. 이에 대한 Python 소스 코드에 대한 심층 분석을 포함하여 오늘의 결과가 있습니다. 저널이 되는 것 외에도 이 게시물이 다음과 같은 사람들에게 도움이 되기를 바랍니다.

Python 소스 코드를 파헤치는 것이 그렇게 무섭지 않다는 것을 깨닫습니다.

새로운 데이터 구조를 배웁니다.

Leetcode 솔루션 확인

from sortedcontainers import SortedDict

class MyCalendarThree(object):

    def __init__(self):
        self.diff = SortedDict()

    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: int
        """
        self.diff[start] = self.diff.get(start, 0) + 1
        self.diff[end] = self.diff.get(end, 0) - 1
        maxK = k = 0

        for val in self.diff.values():
            k += val
            maxK = max(maxK, k)

        return maxK

맙소사, 저를 괴롭혔던 질문이 너무 간단했거든요?!

아니요, SortedDict()의 추상화된 논리 때문에 믿을 수 없을 정도로 단순해 보입니다. 잠시 후에 살펴보겠지만 먼저 게으른 엔지니어에 관한 것입니다...

표준 Python 사전 정렬, dict()

최고의 엔지니어는 게으르다는 말을 들은 기억이 납니다. 효율성에 집착하는 세상의 본질인 일을 처리하는 가장 쉬운 방법을 찾기 때문입니다.



그런 마음으로 표준 Python dict() 함수에 대한 기존 지식으로 해킹을 시도했습니다. 전체 기사는 아래에 있지만 TLDR; 작동하지 않았습니다. 1시간 이내에 완료될 것으로 예상되는 Leetcode Hard 질문(Google 엔지니어가 언급함)에 너무 미친 것처럼 보이는 튜플/목록/딕셔너리 변환 및 람다 표현식이 너무 많습니다.

https://realpython.com/sort-python-dictionary/#sorting-dictionaries-in-python

정렬된 컨테이너로 다이빙

from sortedcontainers import SortedDict 를 작성했으므로 먼저 SortedDict() 를 찾아봅시다!



음.. 꽤 좋은 문서가 있어서 필요한 메서드__getItem__ 및 __setItem__를 아주 빨리 볼 수 있습니다.
__getItem__는 dict에서 상속되었으므로 탐색할 필요가 없으며 이미 함수를 알고 있습니다.
__setItem__는 흥미로운 것입니다.



잠깐.. 저게 뭐야 self._list_add(key) ?





이진 검색 및 삽입과 관련된 것 같습니다.

재료 모으기

이제 우리는 SortedDict() 구현에 다음이 포함된다는 것을 알고 있습니다.

해시맵의 키 순서를 추적하기 위한 정렬된 목록입니다(해시맵의 키는 순서가 없기 때문).

이진 검색 및 정렬된 목록에 삽입.

마지막 해결책

class MyCalendarThree(object):

    def __init__(self):
        self.diff = {}
        self.sortedIdx = []

    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: int
        """
        def binarySearchAndInsert(arr, target):
            l, r = 0, len(arr)-1

            while l <= r:
                mid = l + (r-l)//2
                if arr[mid] > target:
                    r = mid - 1
                else:
                    l = mid + 1

            arr.insert(l, target)
            return arr

        if start not in self.diff:
            self.sortedIdx = binarySearchAndInsert(self.sortedIdx, start)
        self.diff[start] = self.diff.get(start,0) + 1

        if end not in self.diff:
            self.sortedIdx = binarySearchAndInsert(self.sortedIdx, end)
        self.diff[end] = self.diff.get(end,0) - 1

        maxK = k = 0

        for idx in self.sortedIdx:
            val = self.diff[idx]
            k += val
            maxK = max(maxK, k)

        return maxK

결론

내가 작성한 전체 Leetcode 토론 게시물은 링크되어 있습니다here.

그 외에도 계속 게으른 엔지니어로 지내다가 다음에 비슷한 질문이 올라오면 그냥 aSortedDict()를 사용할 것 같아요😎