Zenn
❄️

[Python] リストの代わりに Immutable なタプルでメモリ節約

2022/06/28に公開
Python
#
データ構造
#
メモリ
アルゴリズム
#
immutable
tech

概要

Python で大きめのデータを扱う際に Immutable なデータ構造であるタプルを利用してメモリ使用量を節約する方法を紹介します。

100万件のサンプルデータを生成

Yes, No で回答する全5問のアンケート結果を100万件分析するシーンを考えます。

データ構造は次のような2次元配列で表し、Yes=1, No=0 とします。

[
  [0, 0, 1, 0, 0],
  [1, 0, 0, 1, 1],
  [1, 0, 1, 0, 0],
  ...
  [0, 1, 0, 1, 1],
  [0, 0, 0, 1, 0],
]

まずはランダム値で100万件分の2次元配列を生成します。
（※内包表記の方が楽に生成できますが今回は分かりやすさを優先）

from random import Random

rand = Random()
data1 = []
for i in range(1000000):
    data1.append([rand.randrange(2) for _ in range(5)])

メモリ使用量の計測には同一オブジェクトを除外しながらリストやタプルを再帰的にカウントするために以下のメソッドを利用します。

import sys

def recursive_getsizeof(o):
    calculated = set()
    def getsizeof(o):
        if id(o) in calculated:
            return 0
        calculated.add(id(o))
        return (
            sys.getsizeof(o)
            + (sum(map(getsizeof, o)) if isinstance(o, list) else 0)
            + (sum(map(getsizeof, o)) if isinstance(o, tuple) else 0)
        )
    return getsizeof(o)

data1 のメモリ使用量を取得すると以下の通り約128MBでした。

>>> print(recursive_getsizeof(data1))
128448780

タプルでメモリ節約

タプルはリストよりも省メモリな構造なので単純にタプルに変換しただけでもメモリ使用量は削減されます。

data2 = list(map(tuple, data1))

list(map(tuple, data1)) で data1 内の各要素をタプルに変換してリストの各要素にタプルを持つ次のようなデータ構造とします。

[
  (0, 0, 1, 0, 0),
  (1, 0, 0, 1, 1),
  (1, 0, 1, 0, 0),
  ...
  (0, 1, 0, 1, 1),
  (0, 0, 0, 1, 0),
]

これだけで以下の通り約88MBとなり、3割ほど削減されました。

>>> print(recursive_getsizeof(data2))
88448780

等価オブジェクトの重複を排除してメモリ節約

タプルは Immutable なので同一オブジェクトをリスクなく複数の用途で共有できます。
そこで次は data1 の各要素をタプルに変換しつつ、等価のタプルを1つのオブジェクトにまとめてみます。

今回分析しているアンケート結果はYES/NOを5問なので、2の5乗で32種類のデータがあります。
つまり等価であるタプルの重複を排除すれば100万件のレコード数でも保持するオブジェクトは32個だけで済みます。

singleton = {}
data3 = []
for row in data1:
    value = tuple(row)
    data3.append(singleton.setdefault(value, value))

重複を排除している上記コードは後ほど解説します。
結果は以下の通り約8MBとなり、128MBから比べると9割以上削減されました。

>>> print(recursive_getsizeof(data3))
8451340

参考までに先頭要素の参照カウント数を取得してみます。

>>> print(data3[0])
(0, 0, 1, 0, 0)
>>> sys.getrefcount(data3[0])
31536

すると 31,536 箇所から参照されていました。（※正確には getrefcount 自身の参照をマイナスした 31,535箇所）
100万件がランダムな32種類のデータに分布するので、理論値は 100万÷32 ≒ 31,250 となり、おおよそ近い数値となっています。

どのように重複を排除しているか

では重複排除の方法を詳細に解説します。

重要なのは singleton.setdefault(value, value) です。
dict の setdefault() はキーが存在すればその値を返却し、存在しなければ二つ目の引数の値をセットしつつ返却します。
つまり等価比較（==）が True となるタプルが singleton 内に存在していればそのオブジェクトが返却され、なければ singleton 内に保持しつつ返却します。
この動作で等価のタプルがすべて最初にセットされた1つのオブジェクトになります。

ちなみに value = tuple(row) で生成されたタプルは参照がなくなればすぐに破棄され、一時的にしかメモリを確保しないので気にする必要はありません。
（※Pythonのメモリ管理は参照カウントを基本として、それで回収できない循環参照をGCで回収します。今回のような単純なオブジェクトの生成と解放はGCに頼らず即時に解放されます。）

これだけでは分かりづらいので、setdefault の部分の動作をさらに詳細に見てみましょう。
まずは等価かつ非同一である二つのタプル、value1 と value2 を生成します。

value1 = tuple([1, 1, 0, 0, 1])
value2 = tuple([1, 1, 0, 0, 1])

print(value1)            # (1, 1, 0, 0, 1)
print(value2)            # (1, 1, 0, 0, 1)
print(id(value1))        # 140421751063488
print(id(value2))        # 140421751063744
print(value1 == value2)  # True
print(value1 is value2)  # False

value1 と value2 は同じ内容ですが、2回生成しているのでオブジェクト識別子（id() の返却値）は異なります。
等価比較（==）は True ですが、同一性を比較（is）すると False になります。

singleton = {}

value = singleton.setdefault(value1, value1)
print(value)             # (1, 1, 0, 0, 1)
print(id(value))         # 140421751063488
print(value is value1)   # True
print(value is value2)   # False

singleton が空の状態で setdefault(value1, value1) すると value1 にヒットするキーは存在しないので二つ目の引数に渡した value1 がセットされつつ返却されます。
つまり value is value1 が True であり、 id(value) と id(value1) が同一です。

続けて value2 です。

value = singleton.setdefault(value2, value2)
print(value)             # (1, 1, 0, 0, 1)
print(id(value))         # 140421751063488
print(value is value1)   # True
print(value is value2)   # False

singleton には value2 と等価のキーを含むので、setdefault(value2, value2) の結果は先ほどセットした value1 のオブジェクトが返却されます。
取得した value は value2 とは同一でなく、value1 と同一となっていることから等価のオブジェクトを1つのオブジェクトに集約することができています。

まとめ

今回は単純なデータ構造でしたが、より現実に即したデータでも Immutable かつ等価のオブジェクトを意識すれば同一のオブジェクトに集約できるものがあります。

例えば今回のアンケートが全100問だった場合は単純に重複を排除しても効果はほとんど得られません。しかし少し工夫して以下のような10問ずつに分割すれば効果を得られます。

[
  (
    (0, 0, 1, 0, 0, 1, 0, 0, 1, 1),
    (1, 0, 1, 0, 0, 0, 1, 0, 0, 0),
    ...
    (0, 1, 0, 1, 1, 0, 0, 0, 1, 0),
  ),
  (
    (1, 0, 1, 0, 0, 0, 0, 1, 0, 1),
    (1, 0, 1, 1, 0, 1, 1 ,0, 0, 0),
    ...
    (0, 0, 1, 1, 1, 1, 1, 0, 1, 0),
  ),
]

小規模なデータ構造なら単純に保持すれば問題ありませんが、大規模なデータセットを工夫なく扱うと実行環境のメモリ容量が潤沢でないと実行できなったり、実行できてもスワップの影響で現実的な速度で動作しないことがあります。
そういったシーンに出くわした場合は単純にオブジェクトを生成して保持するのではなく工夫して保持しましょう。

Discussion