※現在、ブログ記事を移行中のため一部表示が崩れる場合がございます。
順次修正対応にあたっておりますので何卒ご了承いただけますよう、お願い致します。

Python簡単実験:集合は大きくなっても小さくならない


2016年 12月 27日

Pythonには、数学の集合と同様の動きをする集合(set)が用意されている。
要素の個数に特に制限はなく、要素に順序もない。
もちろん要素の個数が増えれば、そのぶん集合のサイズが増加するはずだが、サイズを調べるとなかなか不思議な増え方をする。
>>> import sys
>>> a = set()
>>> sys.getsizeof(a)
224
>>> a = {1,2,3}
>>> sys.getsizeof(a)
224
>>> a = {0,1,2,3,4,5,6,7,8,9}
>>> sys.getsizeof(a)
736
空集合でも224バイトもある。 要素をいくつか追加しても、サイズは変化しない。 でも、あるとき、急にサイズが増えるようなのだ。 集合のサイズの増え方を調べるために、以下の実験をした。

sizeofset(n)は、最初に空集合をつくり、その後集合に数字を1つずつn個になるまで追加する。
そのとき、直前のバイトサイズよりも大きくなったときに、集合の要素数とバイト数を表示するようにした。

>>> def sizeofset(n):
...     a = set()
...     pvbsz = sys.getsizeof(a)
...     print('{0:10d}  {1:10d}'.format(len(a),pvbsz))
...     for i in range(1,n):
...         a.add(i)
...         bsz = sys.getsizeof(a)
...         if pvbsz != bsz:
...             print('{0:10d}  {1:10d}'.format(len(a),bsz))
...             pvbsz = bsz
...
>>> sizeofset(10000000)
0         224
6         736
22        2272
86        8416
342       32992
1366      131296
5462      524512
21846     2097376
87382     4194528
174763     8388832
349526    16777440
699051    33554656
1398102    67109088
2796203   134217952
5592406   268435680
これを見ると、サイズが6,22,86,342,…になったy瞬間に集合のバイトサイズが増えている。
87382個までは、大きくなるときには約4倍ずつ大きくなり、それ以上では約2倍ずつ大きくなっている。

大きくなった集合の要素を消していくと、集合のバイトサイズはどうなるだろうか。
実験ではこんな結果になった。


>>> a = {i for i in range(10000000)}
>>> sys.getsizeof(a)
268435680
>>> for i in range(10000000):
...     a.discard(i)
...
>>> a
set()
>>> sys.getsizeof(a)
268435680
要素数1000万個の集合を作ってサイズを求め、次に要素を全部消した。
集合はset()と表示されたので空集合になっている。
しかし、サイズは要素数1000万個のときと同じであり、巨大な空集合ができてしまった(トホホ)。

一度大きくなった集合は、要素がいくら少なくなっても小さくならない。
気をつけなければ。