18

Pythonが辞書を実装する方法を研究しています。Python 辞書実装の方程式の 1 つは、次の方程式を使用して、空の辞書スロットの疑似ランダム プローブを関連付けます。

j = ((j*5) + 1) % 2**i

ここで説明されています。

この質問を読みました。Python の組み込み辞書はどのように実装されていますか? 、基本的に辞書がどのように実装されているかを理解しています。

私が理解していないのは、方程式の理由/方法です:

j = ((j*5) + 1) % 2**i

の残りのすべてを循環します 2**i。たとえばi = 3、合計開始サイズが 8 の 場合j、次のサイクルが実行されます。

0
1
6
7
4
5
2
3
0

開始サイズが 16 の場合、次のサイクルを実行します。

0 1 6 15 12 13 2 11 8 9 14 7 4 5 10 3 0

これは、ディクショナリ内のすべてのスロットをプローブするのに非常に役立ちます。 しかし、なぜそれが機能するのですか? なぜ機能 するのに機能しj = ((j*5)+1)ないのか、j = ((j*6)+1) またはj = ((j*3)+1) その両方が小さなサイクルで立ち往生するのか.

方程式が機能するだけでなく、これをより直感的に理解できることを望んでおり、それが彼らがそれを使用した理由です。

4

1 に答える 1

13

これは、ジャスパーが示唆したように、疑似乱数ジェネレーター、つまり線形合同ジェネレーターが使用するのと同じ原理です。線形合同ジェネレーターは、関係に従うシーケンスですX_(n+1) = (a * X_n + c) mod m。ウィキページより、

一般的な LCG の周期は最大でも m であり、因子の選択によってはそれよりもはるかに短いものがあります。次の場合に限り、LCG はすべてのシード値に対して完全な期間を持ちます。

  1. mそしてc比較的素数です。
  2. a - 1のすべての素因数で割り切れmます。
  3. a - 1が で割り切れる場合、mは 4 で割り切れ4ます。

aこれらの要件を満たすには 5 が最小であることは明らかです。

  1. 2^i と 1 は互いに素です。
  2. 4 は 2 で割り切れます。
  3. 4 は 4 で割り切れます。

また興味深いことに、これらの条件を満たす数は 5 だけではありません。9も使えます。利回りmを使用して、16 としj=(9*j+1)%16ます。

0 1 10 11 4 5 14 15 8 9 2 3 12 13 6 7

これら 3 つの条件の証明は、元の Hull-Dobell 論文の5 ページにあり、興味深い PRNG 関連の定理も多数あります。

于 2016-05-22T20:13:13.870 に答える