Python 3.6 이상에서 딕셔너리 정렬

질문 : 사전은 Python 3.6 이상에서 정렬됩니까?

---

사전은 이전 버전과 달리 Python 3.6 (적어도 CPython 구현 아래)에서 주문됩니다. 이것은 상당한 변화처럼 보이지만 문서 의 짧은 단락 일뿐입니다. 이는 언어 기능이 아니라 CPython 구현 세부 사항으로 설명되지만 향후 표준이 될 수도 있음을 의미합니다.

새 사전 구현은 요소 순서를 유지하면서 이전 구현보다 어떻게 더 잘 수행됩니까?

다음은 문서의 텍스트입니다.

dict() 이제 PyPy가 개척 한 "콤팩트"표현을 사용합니다. 새로운 dict ()의 메모리 사용량은 Python 3.5에 비해 20 %에서 25 % 작습니다. PEP 468 (함수에서 ** kwargs의 순서 유지)는 이것에 의해 구현됩니다. 이 새로운 구현의 순서 유지 측면은 구현 세부 사항으로 간주되며 의존해서는 안됩니다 (향후에 변경 될 수 있지만 언어 사양을 변경하기 전에 몇 가지 릴리스에 대해이 새로운 dict 구현을 언어로 포함하는 것이 바람직합니다. 현재 및 미래의 모든 Python 구현에 대해 순서 보존 의미 체계를 의무화합니다. 이것은 또한 임의 반복 순서가 여전히 유효한 언어의 이전 버전 (예 : Python 3.5)과의 하위 호환성을 유지하는 데 도움이됩니다. (INADA Naoki가 27350 호에 기고 함 . 원래 Raymond Hettinger가 제안한 아이디어.)

2017 년 12 월 업데이트 : dict 의 삽입 순서 유지는 Python 3.7에 대해 보장됩니다.

답변

---

사전은 Python 3.6 이상에서 정렬됩니까?

게재 신청서 ^[1] . Python 3.6부터 Python의 CPython 구현을 위해 사전은 삽입 된 항목의 순서를 기억합니다 . 이것은 Python 3.6에서 구현 세부 사항으로 간주됩니다 . Python의 다른 구현 (및 기타 정렬 된 동작 ^[1] )에서 보장 되는 삽입 순서를 원하는 경우 OrderedDict 를 사용해야합니다.

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

그렇게 만들어. "Dict는 삽입 순서를 유지합니다"가 판결입니다. 감사!

이것은 단순히 당신이 그것에 의존 할 수 있다는 것을 의미합니다. Python의 다른 구현은 Python 3.7의 준수 구현을 원하는 경우 삽입 순서 사전도 제공해야합니다.

Python 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 full 이상이 될 수 없기 때문에 많은 빈 공간이 발생했습니다. (그리고 빈 공간에는 여전히 PyDictKeyEntry 크기가 있습니다!).

필요한 항목 만 저장되고 (삽입 된 항목) intX_t 유형의 희소 배열 (딕셔너리 크기에 따라 X 2/3 * dk_size s full이 유지되므로 현재는 그렇지 않습니다. 빈 공간이 intX_t PyDictKeyEntry 로 변경되었습니다.

PyDictKeyEntry 유형의 희소 배열을 만드는 것은 int 를 저장하기위한 희소 배열보다 훨씬 더 많은 메모리를 요구합니다.

관심이 있다면이 기능에 대한 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']]

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

출처 : https://stackoverflow.com/questions/39980323/are-dictionaries-ordered-in-python-3-6