OrderedDict은 항목의 삽입 순서를 유지해야하기 때문에 get/set/popitem의 성능이 Python 2.7에서 궁금합니다. 지금까지 공식 문서를 찾지 못했습니다. 나는 get이 O(1)이고, set이 O(logN)이고 popitem이 O(1) 인 것으로 추측하고 있습니다.OrderedDict의 get 및 popitem 성능
여기는 collection.OrdereDictdocumentation입니다.
방금 Implementation of python Orderedlist object from Python mercurial repository을 확인했습니다. odictobject.c 파일의 주석에서 다음과 같이 설명했습니다. One invariant of Python's OrderedDict is that it preserves time complexity of dict's methods, particularly the O(1) operations.
감사합니다. 귀하의 회신에 투표하십시오. 나는 그들의 구현 로직에 대한 코드 레포 (code repo)를 읽고'popitem' 구현 논리에 대해 약간 혼란스러워했다. 나는 그것이'O (1)'을 사용하여 어떻게 구현되는지 궁금합니다. 일반적으로 삽입 순서를 유지하기 위해 힙 또는 다른 유사한 데이터 구조가 있어야합니다. 이렇게하면 마지막 또는 처음의 팝이 항상 올바른 항목을 찾을 수 있습니다. –
(계속) 코드 구현에서, 나는 그들이 힙이나 다른 데이터 구조를 사용하고있는 것을 보지 않는다. 그래서 나는 당신이 O (1) 구현을 사용하고있는 것이 맞다고 생각한다. 그들은'O (1)'을 사용하여 성능을 달성합니다. :) –
안녕하세요 Kun, 위의 질문에 조언 할 수 있다면 좋을 것입니다. 감사. –
@Kun, 감사합니다. 나는 묻기 전에 온라인으로 몇몇 문서와 토론을 참조했다. 언급 한 토론에서 결론/get/popitem은 모두'O (1)'입니다. 그러나 저는 그들이 정말로 'O (1)'라는 공식 문서는 찾지 못했습니다. BTW, 내 게시물을 읽으면, 내 질문은 어디 OrderedDict 시간 복잡성에 대한 공식 문서입니다. :) 내가 잘못 읽은 경우 언제든지 저를 시정 해주십시오. –