Python set() のバグ？について

画像中のバグ？について何か知っている方がいらっしゃれば、教えて頂けないでしょうか。

TaniguchiTakaki

2019/11/21 03:49

自分の予想していた挙動はなんでしょうか。その差を書いてもらうと回答しやすいです。

dyossy

2019/11/21 04:14

自分が予想していた挙動は >>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件

ベストアンサー

組み込みの集合は挿入順序を保証しませんので、仕様通りの動作です。

追記

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

LouiS0616

総合スコア35660

dyossy

2019/11/21 04:14 編集

順序を保持しないのはわかるのですが、add()が末尾に追加したり先頭に追加したりするのはランダムな仕様なのですか？なぜ４番目だけ必ずこのような形になるのかが理解できないのです。自分が確認した範囲では、１桁の整数（１，２，３，４‥）、２桁の整数（１１，１２，１３，１４）では同様の現象が起こりませんでしたが、３桁（１０１，１０２，１０３，１０４）ではこのようになります。