たくさんの文字列(や離散的な符号列)をメモリに載せないといけないんだけど、いろんな制約があって通常のList[str]では載らない…ということありませんか?(まぁあんまりなさそうですね) たまたまそういうことがあったので、その際に検討した内容をまとめておきます TL;DR メモリをもっと増やしましょう 富豪的 に解決できるならいつでもそれが最高です しかし、世の中それでなんとかならんこともたくさんあります 用途があうのであれば専用のデータ構造を採用する 例えばもし共通のprefixやsuffixが存在し、順序に興味がなければtrie treeなどが使えます 例えば、 弊社 であれば、法人名をメモリに持ちたいなんてときもあります。そういうときに法人名の辞書をtrieで持ったりすることがあります 「株式会社」「 一般財団法人 」や「銀行」といった共通語がたくさんでてくるのでtrie treeでごりごり削れます pygtrie とか marisa-trie とかが簡単に使えます 他にも様々なデータ構造はあるので、そういうものが使える場合もあるかもしれません 短い文字列が大量にある場合は、とりあえず結合し、各文字列の始点のindexをnumpyのint arrayで持つ Python では1つobjectを作るために50byte程度が消費されます。そして Python の配列はobjectのポインタの配列であり、配列の要素の数だけメモリ上の別の場所にobjectが存在しています したがって、短い文字列を大量に配列で抱えていると、配列内のobjectのポインタ(8byte) + objectを作るためのオーバーヘッド(50byte程度) で大量のメモリが浪費されます 長大な1つのstringのobjectと、indexを持つnumpy array配列であれば、これらの浪費は起きません numpy arrayは要素も含めて1つのobjectになっています 固定長であれば、numpyのmatrixで持つ 固定長の文字列であれば、numpyの2次元配列が活用できるかもしれません。 この場合、固定長であることを利用して、indexの配列が不要になります str型/bytes型の範囲で工夫する Python3.3以降のstr は含まれる文字の範囲によって、1,2,4byte/文字を使い分けてくれます たとえば、ASCIIであらわせる範囲の文字列だけしか含まれない場合、すべての文字が1byte/文字になりますし、ひらがな等の範囲の文字が含まれれば、すべての文字が2byte/文字になります。絵文字が含まれると4byte/文字になるイメージですね したがって、絵文字などを削除してstrを作り直せば、日本語が含まれていても多くの文字列は2byte/文字にはできる可能性があります さらに、bytes型にencodeする手法でもっと圧縮できる場合があります strの エンコーディング は UTF-8 であると思いがちですが、strは unicode のコードポイントをそのまま保存しているので UTF-8 /16/32のどれにも直接対応しているわけではありません。 UTF-8 や UTF-16 は可変長 エンコーディング であり、strのように1文字でもASCIIでない文字が入ったら全部2byte or 4byte / 文字になります、みたいなことはなくいい感じに圧縮して出してくれます 扱う文字列にあったencodingを選択することで、圧縮が可能です 使われる文字が決まっている場合は、bit単位での表現を用いることでメモリを削減できる さらに、出現する文字列の範囲を制限すればメモリを削減できるというア イデア は、1byte単位ではなくbit単位で適用することができます このような場合には bitarray を使えます。例えば、 塩基配列 であれば2bitで1文字を表すことができますが、bitarrayでは(変換処理が入るために)CPU時間を犠牲にコレを実現できます この記事では、ここのコードを載せます 細かく見ていくと… さて、まとめとしてはこれくらいなのですが、以下、2,3,4,5のところについて詳しくみていきます モチベーション: Python のList / numpyの文字列型は意外とメモリを食う まず、いろいろな形式で保存した際のメモリサイズを測定してみましょう。 突然ですが、 Python において以下の文字列のメモリサイズは何byteでしょうか?ナイーブに考えると、char型で表現するとして、”a”は1byte、[“a”,”b”]は2byteですね クイズ "a" ["a","b"] np.array(["a","b]) np.array(["a","bc"]) こたえ 1: 50byte >>> import sys >>> sys.getsizeof("a") 50 でっかいですね!これは Python には GC などもついているので、各オブジェクトにそのための参照カウンタなどがついていたりするからです 2: 172byte >>> sys.getsizeof(["a","b"]) + sys.getsizeof("a") + sys.getsizeof("b") 172 超でかいですね! なぜこの計算になるかというと、 Python のListはそれぞれのオブジェクトへのポインタの配列となっているからです。 以下のように、普通にgetsizeofをすると72byteに見えるのですが、先述の通り、 ポインター の配列なので、これには”a”や”b”といった中身のメモリが含まれてないんですよね。 なので、文字を増やしても同じ長さです >>> sys.getsizeof(["a","b"]) 72 >>> sys.getsizeof(["alphabet","beta"]) 72 要 素数 に合わせて、PyObjectへの ポインター (8byte)が増えていっているのがわかりますね >>> sys.getsizeof([]) 56 >>> sys.getsizeof([0]) 64 >>> sys.getsizeof([0,1]) 72 3: 112byte numpyのarrayは1つのobjectとしてまるっと測定できます >>> import numpy as np >>> sys.getsizeof(np.array(["a","b"])) 112 1つの要素を増やすごとに4byte = 32bitを使ってますね >>> sys.getsizeof(np.array(["a","b","c"])) 116 >>> sys.getsizeof(np.array(["a","b"])) 112 >>> sys.getsizeof(np.array(["a"])) 108 numpyの配列は、要 素数 を増やせばほとんど Python のobjectのオーバーヘッドは考えなくて良くなりそうです 4: 112byte かといってなんでもnumpyにstrをつっこめばいいかというとそうではありません。 1文字増やしただけなのに、8byte = 64bit増えました。 >>> sys.getsizeof(np.array(["a","bc"])) 120 なぜかというと、実は、dtypeが”<U1”から”< U2 ”に変わっているからです。Uは Unicode という意味で、1は文字数です。numpyは行列演算ライブラリですから、各要素のメモリ上のサイズは一緒になるようにレイアウトすることが前提になっています。今までは Unicode を1文字扱えるメモリを確保して各要素を扱っていたのが、2文字のデータが入ってくるようになったので、すべての要素を2文字でようにしているわけですね。結果として、4byte x 2要素分 = 8byte確保されたメモリが増えたのでした。ASCIIの文字列の範囲でも1文字が4byteなのは、冒頭に述べたようなPython3.3以降の工夫などを採用せず、numpyではすべての文字をコードポイントそのまま、つまりint32的に扱っているからのようですね。行列演算ライブラリとしての設計上の要請だと思いますが。 データによって型が決まるのはこのときだけで、この後に長い文字列を追加しても自動的に型が変わるわけではありません。以下のように U2 の配列だと3文字目は落ちてしまいますね >>> arr = np.array(["a","b","cd"]) >>> arr[0] = "aaa" >>> arr array(['aa', 'b', 'cd'], dtype='<U2') さて、長々書いてきましたが、こういう感じなので、すっと思いつくコンテナはこういう欠点がありそうなことがわかります Listで持つと Python のObjectのオーバーヘッドが大きいため、要 素数 が多いとメモリを浪費する(1objectあたり50byteとかそういうオーダー) numpyの文字列型は文字列の最大長x4byteのメモリを確保する Listに関しては、長文であればまぁ別に良いとも言えますが、文ごとに配列に持っているみたいな場合だと、実は数十パーセントが Python 関連のメモリに使われてしまいます。心理学の日本語論文の1文は平均72字らしいですが、例えばこの記事の冒頭の75字の文は224byteになりますが、このうちの50byte近くが Python のわちゃわちゃなわけで、20%以上のメモリが浪費されていそうです >>> sys.getsizeof("学生の作文を添削した際、僕が「1文ずつが長い」と指摘すると、彼は「『何文字程度』というような基準はあるのでしょうか?」と尋ねて(反駁して?)きました。") 224 numpyの場合は、文字数が揃ってないと相当メモリ量が厳しそうです。また、 ナチュラ ルにやると1文字4byteになってしまいます。コレを防ぐには、文字列表現の型をちゃんといじればよさそうですね。 適切な型やencodingを選択する str型の1文字が何byteなのかというのは実は1,2,4byteの3通りがあります 。含まれる文字の unicode コードポイントの最大値が1,2,4byteのどの範囲に入るかによって変わります。そのため、こんな挙動になります >>> sys.getsizeof("a") # asciiのみなら1byte/文字 50 >>> sys.getsizeof("aa") 51 >>> sys.getsizeof("aaa") 52 >>> sys.getsizeof("あ") # ひらがなが入ると2byte/文字 76 >>> sys.getsizeof("ああ") 78 >>> sys.getsizeof("あああ") 80 >>> sys.getsizeof("ああa") # ascii範囲の文字も2byte/文字になる 80 >>> sys.getsizeof("💫") # 絵文字が入ると4byte/文字 80 >>> sys.getsizeof("💫💫") 84 >>> sys.getsizeof("💫💫💫") 88 >>> sys.getsizeof("💫💫a") # ascii範囲の文字も4byte/文字になる 88 ですから、絵文字みたいな文字を削除するとさくっとメモリ専有量が半分になるかもしれません。 さらに、 UTF-8 のような 可変長エンコーディング を使うとより圧縮できます。1文字にXbyte使う、ということを先に決めず、適応的に変更するためより効率よく表現できる場合があります。 >>> sys.getsizeof("今日はいい天気ですね。It's nice weather today.") 144 >>> sys.getsizeof("今日はいい天気ですね。It's nice weather today.".encode("UTF-8")) 90 >>> sys.getsizeof("今日はいい天気ですね。") 96 >>> sys.getsizeof("今日はいい天気ですね。".encode("UTF-8")) 66 この場合、型がbytes型になることに注意が必要です >>> "今日はいい天気ですね。".encode("UTF-8") b'\xe4\xbb\x8a\xe6\x97\xa5\xe3\x81\xaf\xe3\x81\x84\xe3\x81\x84\xe5\xa4\xa9\xe6\xb0\x97\xe3\x81\xa7\xe3\x81\x99\xe3\x81\xad\xe3\x80\x82' bitarrayを使う 特定の ユースケース では文字種別がもっと少ない場合がありそうです。 例えば、英語の大文字とスペースだけしか入ってこないテキストであれば、28種類しか トーク ンは存在しないわけで、これは2^5=32>28なので本当は5bitで表記できそうです。 塩基配列 のようなデータの場合、 トーク ンはATCGの4種類、つまり2bitで表せます。ここまでくると、いい感じの型が用意されてないですね。こういうときに bitarray が便利です。 github.com より頑張る方法として、複数の文字を1つの単位にpackする方法がありますが、そこまではだるいので今回はやりません。本当は例えば、5種類の トーク ンであれば、何も工夫しなければ、3bit (2^3=8>5) をそれぞれの トーク ンに割り当てることになりますが、5x6 =30 < 32 = 2^5なので、2つの トーク ンを3bit x 2 = 6bitではなく、5bitであらわせます(2 トーク ン目として6をかけているのは、2 トーク ン目が存在しない場合を表さないといけないので)。また、 トーク ンの出現頻度に応じてビット列を割当てる Huffman Codingもできる のですが、これも今回はやめときましょう。 では、ここではbitarrayを用いて大量の 塩基配列 データを持つことを考えましょう。bitarrayのobjectをたくさん持つと、 Python のobjectがいっぱい生成されてしまうので、長いbitarrayのobjectを用意し、各stringのindexを別の配列に持つようにします from random import choice, randint from bitarray import bitarray import numpy as np # 文字種をさだめます。塩基配列を例に取ります alphabets = [ "A" , "T" , "C" , "G" ] alphabet_size = len (alphabets) # 何bitを1文字に割り当てればよいかを決め、bit列(bitarrayクラスのインスタンス)と実際の文字の対応関係をdict型で作ります bits_per_char = int (np.ceil(np.log2(alphabet_size))) dictionary: Final[Dict[ str , bitarray]] = { ch: bitarray( bin (idx)[ 2 :].zfill(bits_per_char)) for idx, ch in enumerate (alphabets) } dictionaryの中身はこんな感じです >>> dictionary {'A': bitarray('00'), 'T': bitarray('01'), 'C': bitarray('10'), 'G': bitarray('11')} 変換するデータを用意します。ここでは1文字以上最大長100文字の一様分布の長さの 塩基配列 を10000シーケンス用意します max_len = 100 n = 10000 data_to_convert = [ "" .join([choice(alphabets) for _ in range (randint( 1 ,max_len)) ]) for x in range (n)] 変換しましょう。 indices に各シーケンスの開始地点を持っておきます converted_data = bitarray() indices = [] for seq in data_to_convert: indices.append( len (converted_data)) converted_data.encode(dictionary,seq) indices = np.array(indices,dtype=np.int32) # numpyのint32arrayに変換しておきましょう これで、変換ができました。bitarrayのindex accesorを直接叩くとbit列が得られますが、 >>> converted_data[:100] bitarray('1001011001011011100111000110110111100100101000010011000100101011010000111111000111110011000101001010') さきほどの辞書を用いて復号すると、きちんと文字列が得られます >>> seq = converted_data[indices[0]:indices[1]] >>> "".join(seq.decode(dictionary)) 'CTTCTTCGCTGATCGTGCTACCATAGATACCGTAAGGGATGGAGATTACCCCTATCGCGCACCTA' 一致しますね。 >>> data_to_covert[0] 'CTTCTTCGCTGATCGTGCTACCATAGATACCGTAAGGGATGGAGATTACCCCTATCGCGCACCTA' メモリ使用量を確認してみると… >>> sys.getsizeof(converted_data) + sys.getsizeof(indices) 170282 >>> sys.getsizeof(data_to_convert) + sum([sys.getsizeof(x) for x in data_to_convert]) 1082618 1,082,618byte - 170,282 = 912,336byte 20%弱くらいになってますね!うれしーい。 ここでは、冒頭で書いた2,5の工夫を両方取り入れていますが、 寄与分 を試算してみると、だいたいこんな感じっぽいですね 2bitで表現した分の寄与 (もともとのstr(ascii範囲)は1byte/文字=8bit/文字ぐらい) 10,000シーケンス x 平均50文字 x -6bit = -3,000,000bit = -375,000byte 10,000object -> 1objectになったことの寄与 減少分: -50byteぐらい x 10,000シーケンス = -500,000byte numpy配列の追加分: 4byte (int32) x 10,000シーケンス = +40,000byte 実際には、さまざまな ユースケース でどの工夫がどれくらいきくかはデータ依存かと思いますが、これくらい削減できることもあるということを知っておくともしかしたら役立つことがあるかもしれません MNTSQ株式会社( モンテスキュー )では大量の文字列を扱うエンジニアを募集しています!(が、実際あんまりこういうことはしませんね…) www.mntsq.co.jp この記事を書いた人 堅山耀太郎 MNTSQ社で取締役として 機械学習 ・ 自然言語処理 に関わるもろもろをやっています。好きな食べ物は担々麺です。