[python] Python 3.6 이상에서 사전이 주문됩니까?

Python 3.6 이상에서 사전이 주문됩니까?

그것들은 삽입 순서가되어있다 ^[1] . Python 3.6부터 CPython Python 구현에서 사전 은 삽입 된 항목의 순서를 기억합니다 . 이것은 Python 3.6에서 구현 세부 사항으로 간주됩니다 . 다른 파이썬 구현 OrderedDict에서 보장 되는 삽입 순서 (및 기타 정렬 된 동작 ^[1] ) 를 원할 경우 사용해야 합니다 .

Python 3.7부터는 더 이상 구현 세부 사항이 아니며 언어 기능이됩니다. GvR의 python-dev 메시지에서 :

그렇게 만들어. “사전 삽입 순서 유지”는 판결입니다. 감사!

이것은 단순히 당신이 그것에 의존 할 수 있다는 것을 의미 합니다 . 파이썬의 다른 구현은 파이썬 3.7의 적합한 구현이 되려면 삽입 순서 사전을 제공해야합니다.

---

어떻게 파이썬 않는 3.6사전 구현은 더 잘 수행 ^[2] 이전보다가 그대로 유지하면서 요소 순서를?

본질적으로 두 개의 배열 을 유지함으로써 .

• 첫 번째 배열 인 에는 사전에 대한 dk_entries항목 ( 유형PyDictKeyEntry )을 삽입 된 순서대로 보유합니다 . 보존 순서는 새 항목이 항상 끝에 삽입되는 추가 전용 배열 (삽입 순서)로 이루어집니다.

• 두 번째 dk_indices는 dk_entries배열 의 인덱스 (즉,에서 해당 항목의 위치를 ​​나타내는 값 dk_entries)를 보유합니다. 이 배열은 해시 테이블 역할을합니다. 키가 해시되면 키가 저장된 인덱스 중 하나로 연결되고 dk_indices해당 항목은 색인화하여 가져옵니다 dk_entries. 인덱스 만이 유지되므로, 이러한 배열의 형태가 사전의 전체 크기 (레인 징의 타입에 따라 int8_t( 1바이트)로 int32_t/ int64_t( 4/ 8바이트)에 32/ 64비트 빌드)

이전 구현에서는 유형 PyDictKeyEntry과 크기 의 희소 배열을 dk_size할당해야했습니다. 불행히도, 성능상의 이유로 어레이가 2/3 * dk_size가득 차는 것을 허용하지 않았기 때문에 빈 공간이 많이 생겼습니다 . (그리고 빈 공간에는 여전히 크기 가 있습니다!).PyDictKeyEntry

단지 때문에 지금 그렇지 않다 필요한 항목의 입력은 희소 배열 (삽입 된 것)에 저장된다 intX_t( X딕셔너리 크기에 따라) 2/3 * dk_size의 전체 유지된다. 빈 공간이 유형에서 PyDictKeyEntry로 변경되었습니다 intX_t.

따라서, 희소 한 유형의 배열을 생성하는 PyDictKeyEntry것은 ints 를 저장하기위한 희소 배열보다 훨씬 더 많은 메모리를 요구 합니다.

관심이 있다면이 기능에 관한 Python-Dev 의 전체 대화 를 볼 수 있습니다 .

---

Raymond Hettinger의 원래 제안에서 , 사용 된 데이터 구조의 시각화를 통해 아이디어의 요점을 파악할 수 있습니다.

예를 들어 사전은 다음과 같습니다.

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

현재 [keyhash, key, value]로 저장됩니다 :

entries = [['--', '--', '--'],
           [-8522787127447073495, 'barry', 'green'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           ['--', '--', '--'],
           [-9092791511155847987, 'timmy', 'red'],
           ['--', '--', '--'],
           [-6480567542315338377, 'guido', 'blue']]

대신, 데이터는 다음과 같이 구성되어야합니다.

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, 'timmy', 'red'],
            [-8522787127447073495, 'barry', 'green'],
            [-6480567542315338377, 'guido', 'blue']]

시각적으로 볼 수 있듯이 원래 제안에서 충돌을 줄이고 조회 속도를 높이기 위해 많은 공간이 기본적으로 비어 있습니다. 새로운 접근 방식을 사용하면 인덱스에서 실제 필요한 위치에 스 퍼니스를 이동하여 필요한 메모리를 줄일 수 있습니다.

---

_{[1] : OrderedDict가 있으면 “ordered”는 dict개체 가 제공하지 않는 추가 동작을 나타 내기 때문에 “inserted ordered” 가 아니라 “ordered” 가 아닙니다 . OrderedDict는 가역적이며 순서에 민감한 방법을 제공하며 주로 순서에 민감한 등식 테스트 ( ==, !=)를 제공합니다. dict현재 이러한 행동 / 방법을 제공하지 않습니다.}

---

_{[2] : 새로운 딕셔너리 구현은보다 간결하게 설계되어보다 나은 메모리 성능을 제공합니다 . 이것이 주요 이점입니다. 현명하게도, 그 차이는 그다지 급격하지는 않습니다. 새로운 dict이 약간의 회귀 ( 예 : 키 조회)를 유발할 수있는 반면, 다른 경우 (반복 및 크기 조정이 떠오를 경우)에는 성능 향상이 있어야합니다.}

_{전반적으로, 특히 실제 상황에서 사전의 성능은 도입 된 소형화로 인해 향상됩니다.}

---

답변