Q&A
自分の予想していた挙動はなんでしょうか。その差を書いてもらうと回答しやすいです。
画像中のバグ？について何か知っている方がいらっしゃれば、教えて頂けないでしょうか。
自分が予想していた挙動は
>>s.add(504)
>>s
{501, 502, 503, 504}
または、
>>s.add(504)
>>s
{504, 501, 502, 503}
>>s.add(505)
>>s
{504, 501, 502, 503, 505}
(もしくは {505, 504, 501, 502, 503})
です。
回答2件
0
ベストアンサー
組み込みの集合は挿入順序を保証しませんので、仕様通りの動作です。
追記
CPythonの実装をざっと読んでみました。
- セットの内部テーブルの初期サイズは8
- mask領域の5倍がテーブルサイズの3倍以上になったとき、テーブルを拡大する処理が入る (註1)
- テーブルはただの配列で、ハッシュ値 mod テーブル長 番目の領域にデータが格納される
n5 < 83 を満たさない最小の整数nは5です。
つまり5要素目を追加するときにテーブルの拡大処理が入っていることになります。
hash(504) mod 8 = 0 ですので(註2)、リサイズ前は他の要素より先に置かれるのも納得できます。
Python
1>>> {4, 5, 6, 7} 2{4, 5, 6, 7} ← hash(n) mod 8 の昇順に並ぶ 3>>> {5, 6, 7, 8} 4{8, 5, 6, 7} ← hash(n) mod 8 の昇順に並ぶ 5>>> {5, 6, 7, 8, 9} 6{5, 6, 7, 8, 9} ← hash(n) mod 16 の昇順に並ぶ
註1
mask領域は、使用済み(used)領域とダミー領域の和。
ダミー領域がテーブル上に置かれるのは、要素を取り除くような処理を行った場合。
註2
充分小さい自然数nについて、hash(n) = n だったように記憶しています。
出典は忘れました。ドキュメントのどっかに書いてあった筈。多分実装依存。
参考：
一年越しの追記
64bitマシンのCPythonの場合、2**61-2までの自然数nは hash(n) = n と言えそうです。
組み込み型 — Python 3.7.9 ドキュメント
Python
1def hash_fraction(m, n): 2 """Compute the hash of a rational number m / n.
Assumes m and n are integers, with n positive. Equivalent to hash(fractions.Fraction(m, n)). """ P = sys.hash_info.modulus
# Remove common factors of P. (Unnecessary if m and n already coprime.) while m % P == n % P == 0: m, n = m // P, n // P
if n % P == 0: hash_value = sys.hash_info.inf else: # Fermat's Little Theorem: pow(n, P-1, P) is 1, so # pow(n, P-2, P) gives the inverse of n modulo P. hash_value = (abs(m) % P) * pow(n, P - 2, P) % P if m < 0: hash_value = -hash_value if hash_value == -1: hash_value = -2 return hash_value
0 <= m < P, n = 1 のとき、次のように簡略化できます。
Python
1def hash_fraction(m, n): 2 P = sys.hash_info.modulus 3 4 hash_value = m 5 return hash_value
hash_value = (abs(m) % P) * pow(n, P - 2, P) % P がちょっと分解しづらいですが、
0. n = 1, 2 < P なので、pow(n, P-2) = 1.
hash_value = (abs(m) % P) * (1 % P) % P
0. 0 <= m なので、abs(m) = m.
hash_value = (m % P) * (1 % P) % P
0. x < P, xが自然数 なら、x % P = x.
hash_value = m * 1 % P
hash_value = m % P
hash_value = m
投稿2019/11/21 03:53
編集2020/11/15 05:34
総合スコア35668
順序を保持しないのはわかるのですが、add()が末尾に追加したり先頭に追加したりするのはランダムな仕様なのですか？
なぜ４番目だけ必ずこのような形になるのかが理解できないのです。自分が確認した範囲では、１桁の整数（１，２，３，４‥）、２桁の整数（１１，１２，１３，１４）では同様の現象が起こりませんでしたが、３桁（１０１，１０２，１０３，１０４）ではこのようになります。
仕様では定められていませんので、途中どんな順序に入れ替わろうがバグではありません。
> なぜ４番目だけ必ずこのような形になるのかが理解できないのです。
バージョンや環境が変われば別な結果になるかもしれない、その程度のものです。仕様として何も決まっていないことに悩んでも使いみちはありません。
@dyossy さん
CPython実装上において、考えられる原因を追記しました。これでご納得いただけますか。
LouiS0616 さん
ありがとうございます！！すごくすっきりしました。
環境が変わればこのあたりの仕組みも変わるかもしれませんが、なぜこうなるのか規則性がある気がしてならずとても気になっていたので大変助かりました。
本当にありがとうございました。
0
順序が保障されていない
と
順序はランダム
はイコールではありません。
たまたま、実行環境上ではその順序で並ぶというだけです。
投稿2019/11/21 04:17
退会済みユーザー
総合スコア0
あなたの回答
tips
プレビュー
