OrderedDict를 사용하지 않는 이유가 있습니까?

OrderedDict를 사용하지 않는 이유가 있습니까?

---

주문 된 사전 인 모듈 의 OrderedDict 를 참조하고 collections있습니다.

주문할 수있는 추가 기능이있는 경우, 종종 필요하지 않을 수도 있지만 그렇더라도 단점이 있습니까? 느린가요? 기능이 누락 되었습니까? 누락 된 방법을 보지 못했습니다.

즉, 왜 안 나는 항상 정상적인 사전 대신이 사용합니까?

---

OrderedDict의 하위 클래스이며 dict키가 추가되는 순서를 추적하려면 더 많은 메모리가 필요합니다. 이것은 사소한 것이 아닙니다. 이 구현 dict은 커버 아래 에 두 번째를 추가하고 모든 키 (순서를 기억하는 부분)의 이중 링크 목록 및 약한 참조 프록시를 추가합니다. 그것은 아니다 많이 느리지 만 적어도 평범한를 사용을 통해 메모리를 두 배로 dict.

그러나 적절하다면 그것을 사용하십시오! 그래서 거기에 :-)

작동 원리

기본 dict는 키를 값에 매핑하는 일반 dict 일뿐입니다. "순서"가 전혀 없습니다. 때 <key, value>쌍 첨가되면,이 key리스트에 추가된다. 목록은 순서를 기억하는 부분입니다.

그러나 이것이 Python 목록 인 경우 키를 삭제 하면 목록에서 키 를 찾는 데 O(n)시간 이 걸리고 O(n)목록 O(n)에서 키를 제거하는 데 시간이 두 번 걸립니다 .

따라서 대신 이중으로 연결된 목록입니다. 그러면 키 상수 ( O(1)) 시간 이 삭제 됩니다. 하지만 여전히 키에 속하는 이중 연결 목록 노드를 찾아야합니다. 이 작업 O(1)시간 을 만들기 위해 두 번째 숨겨진 dict는 이중 연결 목록의 노드에 키를 매핑합니다.

따라서 새 <key, value>쌍을 추가하려면 해당 쌍을 기본 dict에 추가하고, 키를 보관할 새 이중 연결 목록 노드를 만들고, 새 노드를 이중 연결 목록에 추가하고, 숨겨진 dict의 새 노드에 키를 매핑해야합니다. . 작업량은 두 배가 조금 넘지 만 O(1)전체적으로는 여전히 (예상되는 경우) 시간입니다.

마찬가지로, 존재하는 키를 삭제하는 것은 작업량이 두 배가 넘지 만 O(1)전체적으로 예상되는 시간입니다. 숨겨진 사전을 사용하여 키의 이중 연결 목록 노드를 찾고 목록에서 해당 노드를 삭제하고 두 사전 모두에서 키를 제거하십시오.

Etc. 매우 효율적입니다.

---

멀티 스레딩

잠금없이, 특히 동기화 지점으로 여러 스레드에서 사전에 액세스하는 경우.

바닐라 사전 작업은 원자 적이며 Python에서 확장 된 모든 유형은 그렇지 않습니다.

사실 OrderedDict가 스레드로부터 안전하다는 것도 확신하지 못합니다 (잠금없이). 매우 신중하게 코딩되어 재진입의 정의를 충족 할 가능성을 무시할 수는 없습니다.

하급 악마

이러한 사전을 많이 만드는 경우 메모리 사용량

모든 코드가 이러한 사전을 엉망으로 만드는 경우 CPU 사용량

---

일반 사전 대신 항상 이것을 사용하면 안되는 이유

Python 2.7에서 일반적인 OrderedDict사용은 참조주기를 생성 합니다. 따라서를 사용 OrderedDict하려면 메모리를 해제하기 위해 가비지 수집기를 활성화해야합니다. 예, 가비지 컬렉터는 CPython에 기본적으로 설정되어 있지만 해제하는 것은 그 용도가 있습니다 .

예 : cPython 2.7.14 사용

from __future__ import print_function

import collections
import gc

if __name__ == '__main__':
    d = collections.OrderedDict([('key', 'val')])
    gc.collect()
    del d
    gc.set_debug(gc.DEBUG_LEAK)
    gc.collect()
    for i, obj in enumerate(gc.garbage):
        print(i, obj)

출력

gc: collectable <list 00000000033E7908>
gc: collectable <list 000000000331EC88>
0 [[[...], [...], 'key'], [[...], [...], 'key'], None]
1 [[[...], [...], None], [[...], [...], None], 'key']

빈 OrderedDict( d = collections.OrderedDict())을 만들고 여기에 아무것도 추가하지 않거나 clear메서드 ( d.clear()이전 del d) 를 호출하여 명시 적으로 정리하려고하더라도 자체 참조 목록이 하나만 표시됩니다.

gc: collectable <list 0000000003ABBA08>
0 [[...], [...], None]

This seems to have been the case since this commit removed the __del__ method in order to prevent the potential for OrderedDict to cause uncollectable cycles, which are arguably worse. As noted in the changelog for that commit:

Issue #9825: removed __del__ from the definition of collections.OrderedDict. This prevents user-created self-referencing ordered dictionaries from becoming permanently uncollectable GC garbage. The downside is that removing __del__ means that the internal doubly-linked list has to wait for GC collection rather than freeing memory immediately when the refcnt drops to zero.

---

Note that in Python 3, the fix for the same issue was made differently and uses weakref proxies to avoid cycles:

Issue #9825: Using __del__ in the definition of collections.OrderedDict made it possible for the user to create self-referencing ordered dictionaries which become permanently uncollectable GC garbage. Reinstated the Py3.1 approach of using weakref proxies so that reference cycles never get created in the first place.

---

Since Python 3.7, all dictionaries are guaranteed to be ordered. The Python contributors determined that switching to making dict ordered would not have a negative performance impact. I don't know how the performance of OrderedDict compares to dict in Python >= 3.7, but I imagine they would be comparable since they are both ordered.

See also:

• Will OrderedDict become redundant in Python 3.7?

참고URL : https://stackoverflow.com/questions/18951143/are-there-any-reasons-not-to-use-an-ordereddict