set ()은 어떻게 구현됩니까?

set ()은 어떻게 구현됩니까?

---

사람들은 set파이썬의 객체에 O (1) 멤버쉽 검사가 있다고 말합니다 . 이것을 허용하기 위해 내부적으로 어떻게 구현됩니까? 어떤 종류의 데이터 구조를 사용합니까? 그 구현에 어떤 다른 의미가 있습니까?

여기에있는 모든 대답은 실제로 깨달았지만 하나만 받아 들일 수 있으므로 원래 질문에 가장 가까운 대답으로 갈 것입니다. 정보 주셔서 감사합니다!

---

이 스레드 에 따르면 :

실제로 CPython의 세트는 더미 값을 가진 사전 (키가 세트의 멤버 인 사전)과 같이 구현되며, 이러한 값 부족을 악용하는 최적화가 있습니다.

기본적으로 a set는 기본 데이터 구조로 해시 테이블을 사용합니다. 해시 테이블에서 항목을 찾는 것이 평균적으로 O (1) 작업이므로 O (1) 멤버쉽 확인에 대해 설명합니다.

Achim Domma 에 따르면 대부분 구현 에서 잘라내어 붙여 넣는 set에 대한 CPython 소스 코드를 찾아 볼 수도 있습니다 .dict

---

사람들이 세트에 O (1) 회원 확인이 있다고 말하면 평균 사례 에 대해 이야기하고 있습니다. 에서 최악의 경우 (모든 해시 값이 충돌 할 때) 멤버 검사가 O (N)이다. 시간 복잡성에 대한 파이썬 위키를 참조하십시오 .

위키 백과 문서는 말한다 최상의 경우 크기 조정하지 않는 해시 테이블에 대한 시간 복잡도를 O(1 + k/n). Python 세트는 크기가 조정되는 해시 테이블을 사용하므로이 결과는 Python 세트에 직접 적용되지 않습니다.

위키 피디 기사에있어서 약간은에 대해 말한다 평균 케이스와 시간 복잡도는 간단 균일 해싱 함수를 가정하고 O(1/(1-k/n)), k/n일정에 의해 제한 될 수 c<1.

Big-O는 점근 적 행동만을 n → ∞로 나타냅니다. k / n은 n과 관계 없이 상수 c <1에 의해 제한 될 수 있으므로 ,

O(1/(1-k/n))보다 더 큰 없습니다 O(1/(1-c))에 해당하는 O(constant)= O(1).

따라서 균일 한 간단한 해싱을 가정 할 때 평균적 으로 파이썬 세트에 대한 멤버십 확인은 O(1)입니다.

---

나는 일반적인 실수, set조회 (또는 그 문제에 대한 해시 테이블)가 O (1)이 아니라고 생각합니다 .
위키 백과에서

가장 간단한 모델에서 해시 함수는 완전히 지정되어 있지 않으며 테이블 크기는 조정되지 않습니다. 최적의 해시 함수 선택을 위해 열린 주소 지정을 가진 크기 n의 테이블은 충돌이없고 최대 n 개의 요소를 보유하며, 성공적인 조회를위한 단일 비교와 연결 및 k 키가있는 크기 n의 테이블은 최소값을 갖습니다. 조회에 대한 (0, kn) 충돌 및 O (1 + k / n) 비교 해시 함수의 최악의 선택의 경우, 모든 삽입시 충돌이 발생하고 해시 테이블은 선형 검색으로 퇴화되며, 삽입 당 Ω (k)의 상각 비교와 성공적인 조회를 위해 최대 k 개의 비교가 이루어집니다.

관련 : 자바 해시 맵은 O (1) 정말?

---

우리 모두는 소스에 쉽게 접근 할 수 있으며 , 앞의 주석은 set_lookkey()다음과 같습니다.

/* set object implementation
 Written and maintained by Raymond D. Hettinger <python@rcn.com>
 Derived from Lib/sets.py and Objects/dictobject.c.
 The basic lookup function used by all operations.
 This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
 The initial probe index is computed as hash mod the table size.
 Subsequent probe indices are computed as explained in Objects/dictobject.c.
 To improve cache locality, each probe inspects a series of consecutive
 nearby entries before moving on to probes elsewhere in memory.  This leaves
 us with a hybrid of linear probing and open addressing.  The linear probing
 reduces the cost of hash collisions because consecutive memory accesses
 tend to be much cheaper than scattered probes.  After LINEAR_PROBES steps,
 we then use open addressing with the upper bits from the hash value.  This
 helps break-up long chains of collisions.
 All arithmetic on hash should ignore overflow.
 Unlike the dictionary implementation, the lookkey function can return
 NULL if the rich comparison returns an error.
*/


...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif

/* This must be >= 1 */
#define PERTURB_SHIFT 5

static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)  
{
...

---

To emphasize a little more the difference between set's and dict's, here is an excerpt from the setobject.c comment sections, which clarify's the main difference of set's against dicts.

Use cases for sets differ considerably from dictionaries where looked-up keys are more likely to be present. In contrast, sets are primarily about membership testing where the presence of an element is not known in advance. Accordingly, the set implementation needs to optimize for both the found and not-found case.

source on github

참고URL : https://stackoverflow.com/questions/3949310/how-is-set-implemented