setPythonのオブジェクトにはO（1）メンバーシップチェックがあると言われているのを見てきました。これを可能にするために、それらはどのように内部的に実装されていますか？どのようなデータ構造を使用していますか？その実装には他にどのような影響がありますか？
ここでのすべての答えは本当に啓発的でしたが、私は1つしか受け入れることができないので、元の質問に最も近い答えを使用します。情報をありがとう！
84829 次
6 に答える
188
このスレッドによると：
実際、CPythonのセットは、ダミー値（セットのメンバーであるキー）を持つ辞書のようなものとして実装され、この値の欠如を利用するいくつかの最適化が行われます。
したがって、基本的にsetは、基礎となるデータ構造としてハッシュテーブルを使用します。ハッシュテーブル内のアイテムの検索は平均して操作でO(1)あるため、これはメンバーシップチェックを説明しています。O(1)
気になる場合は、Achim Dommaによると、元々は実装からのカットアンドペーストであったCPythonソースコードを参照することもできます。setdict
注：現在、setおよびdictの実装は大幅に異なるため、さまざまなユースケースでの正確な動作（たとえば、任意の順序と挿入順序）およびパフォーマンスは異なります。それらはまだハッシュテーブルの観点から実装されているので、平均的なケースのルックアップと挿入は残りますO(1)がset、もはや単なる「dictではなく、ダミー/省略されたキー」です。
于 2010-10-16T14:47:43.110 に答える
92
セットにO（1）メンバーシップチェックがあると人々が言うとき、彼らは平均的なケースについて話している。最悪の場合（すべてのハッシュ値が衝突する場合）、メンバーシップチェックはO（n）です。時間計算量については、Pythonwikiを参照してください。
ウィキペディアの記事によると、サイズ変更されないハッシュテーブルの最良のO(1 + k/n)時間計算量はです。Pythonセットはサイズ変更するハッシュテーブルを使用するため、この結果はPythonセットには直接適用されません。
ウィキペディアの記事のもう少し先では、平均的なケースで、単純な均一ハッシュ関数を想定すると、時間計算量はO(1/(1-k/n))でありk/n、定数で制限できますc<1。
Big-Oは、漸近的振る舞いのみをn→∞と呼びます。k / nは定数c<1で制限できるため、nに関係なく、
O(1/(1-k/n))=O(1/(1-c))と同等の値よりも大きくはありません。O(constant)O(1)
したがって、均一な単純なハッシュを想定すると、平均して、PythonセットのメンバーシップチェックはですO(1)。
于 2010-10-16T16:47:12.853 に答える
15
よくある間違いだと思います。setルックアップ（またはそのことについてはハッシュテーブル）はO（1）ではありません。
ウィキペディアから
最も単純なモデルでは、ハッシュ関数は完全に指定されておらず、テーブルのサイズは変更されません。ハッシュ関数を最適に選択するために、オープンアドレス法を使用したサイズnのテーブルには衝突がなく、最大n個の要素を保持し、ルックアップを成功させるための単一の比較を行います。また、チェーンとkキーを使用したサイズnのテーブルの最大値は最小です。 （0、kn）衝突とルックアップのためのO（1 + k / n）比較。ハッシュ関数の最悪の選択では、挿入ごとに衝突が発生し、ハッシュテーブルは線形検索に縮退します。挿入ごとにΩ（k）の償却された比較と、ルックアップを成功させるための最大kの比較が行われます。
于 2010-10-16T14:57:26.020 に答える
14
私たちは皆、ソースに簡単にアクセスできます。前のコメントに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)
{
...
于 2010-10-16T14:59:38.607 に答える
3
set'sとの違いをもう少し強調するために、コメントセクションdict'sからの抜粋を示しsetobject.cます。これは、ディクトに対するセットの主な違いを明確にしています。
セットのユースケースは、ルックアップされたキーが存在する可能性が高い辞書とはかなり異なります。対照的に、セットは主に、要素の存在が事前にわからないメンバーシップテストに関するものです。したがって、セットの実装は、見つかった場合と見つからなかった場合の両方に対して最適化する必要があります。
githubのソース
于 2017-11-15T08:58:10.640 に答える
2
Pythonのセットは、内部でハッシュテーブルを使用します。まず、ハッシュテーブルについて説明します。ハッシュテーブルに格納したい要素がいくつかあり、ハッシュテーブルに31個の場所があります。要素を2.83、8.23、9.38、10.23、25.58、0.42、5.37、28.10、32.14、7.31とします。ハッシュテーブルを使用する場合は、最初に、これらの要素が格納されるハッシュテーブルのインデックスを決定します。モジュラス関数はこれらのインデックスを決定する一般的な方法です。したがって、一度に1つの要素を取得し、それを100で乗算し、モジュロを31で適用するとします。要素に対するこのような各操作により、次のように一意の数値が得られることが重要です。チェーンが許可されていない限り、ハッシュテーブルのエントリは1つの要素のみを格納できます。このようにして、各要素は、モジュロ演算によって取得されたインデックスによって管理される場所に格納されます。ここで、このハッシュテーブルを使用して基本的に要素を格納するセット内の要素を検索する場合、要素のインデックスが一定時間のモジュロ演算を使用して計算されるため、O（1）時間で要素を取得します。モジュロ演算について説明するために、次のコードも記述します。
piles = [2.83, 8.23, 9.38, 10.23, 25.58, 0.42, 5.37, 28.10, 32.14, 7.31]
def hash_function(x):
return int(x*100 % 31)
[hash_function(pile) for pile in piles]
出力：[4、17、8、0、16、11、10、20、21、18]
于 2020-10-23T07:26:00.950 に答える