125:巨大で疎な配列を使う

125：巨大で疎な配列を扱う

Python の場合、配列ではなくてリストですね。 巨大で疎なリストを作った場合、その大半は無駄になってしまいます。:

   >>> L = [None] * 10000
   >>> L[0] = 0
   >>> L[10] = 10
   >>> L[100] = 100
   >>> L[1000] = 1000
   >>> L
   [0, None, None, None, None, None, None, None, None, None, 10, None, None, None,
   None, None, None, None, None, None, None, None, None, None, None, None, None, No
   ne, None, None, None, None, None, None, None, None, None, None, None, None, None
   , None, None, None, None, None, None, None, None, None, None, None, None, None,
   ・・・（中略）
   >>> print L[0]
   0
   >>> print L[1]
   None

この代替として辞書を用います。 10000 ならともかく、億とか兆といった数を捌くならば辞書型です。 また、 100 ～ 10000 程度の数の場合、速度と空間のトレードオフが心配かもしれません。 この場合でも Python の辞書型を一度、信じて使ってみてくださいませ。十分な速さがあることがわかるはずです。:

   >>> d = {}
   >>> d[0] = 0
   >>> d[10] = 10
   >>> d[100] = 100
   >>> d[1000] = 1000
   >>> d
   {0: 0, 1000: 1000, 10: 10, 100: 100}
   >>> d[0]
   0
   >>> d[1]
   Traceback (most recent call last):
     File "<stdin>", line 1, in <module>
   KeyError: 1

値の入れていない箇所に何らかの初期値があるとみなしたければ、値を得るとき get メソッドを用い、その第２引数に値を入れます。:

   >>> print d.get(0, None)
   0
   >>> print d.get(1, None)
   None

速度比較

リスト長さ 10000 vs 代替の辞書。値の数 4 つ。説明に使ったものと一緒のリスト、辞書です。 10000 件すべてにアクセスを 10000 回試して速度計測してみました。 辞書のほうが約 3.68 倍時間かかりました。 10000 件すべてにアクセスするのにかかった時間は１回当たり 1.56ms, 5.66ms といずれも数ミリ秒でした。:

    >>> L = [None] * 10000
    >>> L[0] = 0
    >>> L[10] = 10
    >>> L[100] = 100
    >>> L[1000] = 1000
    >>> d = {}
    >>> d[0] = 0
    >>> d[10] = 10
    >>> d[100] = 100
    >>> d[1000] = 1000
    >>>
    >>> import timeit
    >>> ltimer = timeit.Timer(stmt="""for i in range(10000):
    ...     L[i]
    ... """, setup="from __main__ import L")
    >>> dtimer = timeit.Timer(stmt="""for i in range(10000):
    ...     d.get(i, None)
    ... """, setup="from __main__ import d")
    >>> ltimer.timeit(10000) / 10000.0
    0.0015582651705733496
    >>> dtimer.timeit(10000) / 10000.0
    0.0056575143768272029
    >>> dtimer.timeit(10000) / ltimer.timeit(10000)
    3.6826023933913818