長いテキストから文字列取り出し、narrayに結合を繰り返していると処理が遅くなってゆく

Question

比較的長めの文章（txtで40MB,おそらく80万行ほど）から1行ごとにre.finditerで特定の文字列を取り出し、
numpyの2次元配列に結合する、というコードを書きました。
序盤は対象配列を抽出、クリーニング、arrayに結合　まで0.01sec程度で終わっていたのですが
次第に遅くなり、0.1sec、0.3secと遅くなり続けています。

for string in re.finditer(("some_regex"),txt, re.MULTILINE):
        get = string.group()
        get_2 = string.group(1)
        ##re split subなどで整形
        cleaned_data = [datax,datay,dataz]
        array = np.vstack((array,cleaned_data))

このようなコードです。
遅くなる原因としてarrayのデータ量が大きくなっていきvstackの際に時間がかかっているのでは
と考えました。
そのため、for内部にカウンターを設置しカウンターが1000になるまでは一時保存配列に整形データを格納、
1000を超えたらarrayに格納、というようにすればarrayの呼び出し回数が減り処理速度の遅延も回避できるかと思ったのですが
他になにか良い方法があれば教えていただきたいです。

Answer 1

1行が50byteの文章のデータで80万行ということであれば、Numpy ではなくて Pandas を使った方が便利です。データの内容が質問の中にないので詳しいことは書けませんが、以下のコードで基本的なところの処理はできて、残りの処理は str アクセサーを使えばできると思います。

import pandas as pd

df = pd.read_csv(filepath, header=None)
df = df[0].str.extract("some_regex")

パフォーマンスは、通常の python の処理とあまり変わらないと思いますが、コードは分かり易くなります。また、Numpy を使いたいのであれば、Pandas の Series から変換すればいいです。

文章がどういうデータになっているかを質問に追記してもらえれば、もう少し詳しコードを書くことが可能です。

Answer 2

すでにquiquiさんの回答されている通り、np.appendはただでさえ遅い操作であり、更に文字列をnumpy配列に格納するとデフォルトでは固定長フォーマットで取り扱われるためメモリ効率も悪くなります。

基本的にはlistで取り扱うことを推奨しますが、どうしてもnumpy配列に格納したい場合は、object型を使えば固定長フォーマットになる問題だけは解消し、pythonのstr（※python3前提）をlistに格納したのと同等になります。

この場合はpythonの演算子を使った基本的な文字列操作を一括で適用できるほか、indexingなどnumpy配列のリッチな機能も使えるので、用途によってはありかもしれません（コードが書きやすいというだけで、パフォーマンス自体は愚直にループなどを使って書くのと大差ないはずです）。

>>> import numpy as np
>>> a = ["hoge", "fuga", "piyo", "hogehoge", "fugafuga", "piyopiyo"]
>>> np.array(a)
array(['hoge', 'fuga', 'piyo', 'hogehoge', 'fugafuga', 'piyopiyo'],
      dtype='<U8')
>>> np.array(a, dtype=object)
array(['hoge', 'fuga', 'piyo', 'hogehoge', 'fugafuga', 'piyopiyo'],
      dtype=object)
>>> a = np.array(a, dtype=object)
>>> a + "!"
array(['hoge!', 'fuga!', 'piyo!', 'hogehoge!', 'fugafuga!', 'piyopiyo!'],
      dtype=object)
>>> a * 2
array(['hogehoge', 'fugafuga', 'piyopiyo', 'hogehogehogehoge',
       'fugafugafugafuga', 'piyopiyopiyopiyo'], dtype=object)
>>> a[[1,3]]
array(['fuga', 'hogehoge'], dtype=object)

Comments

[nifch]

objectで格納、かなり便利そうですね。
いくつか自分の作業の中で活用できそうです。ありがとうございます。

Answer 3

numpy.ndarrayは固定の大きさの配列を効率よく操作するためのデータ構造ですから……。
単純なタプルのリストでいいのではないですか。
どうしてもnumpy.ndarrayが欲しいなら最後にnumpy.ndarrayにすればいいかと。

In [1]: import numpy as np

In [2]: def arr(n):
      :     a = np.array([['', '']])
      :     for i in range(n):
      :         data = [(str(i), str(i+1))]
      :         a = np.vstack((a, data))
      :     return len(a)
      :
      :

In [3]: def list_append(n):
      :     """ひとつのリストに追加していく"""
      :     a = [('', '')]
      :     for i in range(n):
      :         data = [(str(i), str(i+1))]
      :         a.append(data)
      :     return len(a)
      :

In [4]: def list_new(n):
      :     """連結したリストを都度新しく作る"""
      :     a = [('', '')]
      :     for i in range(n):
      :         data = [(str(i), str(i+1))]
      :         a = a + data
      :     return len(a)
      :

In [5]: %timeit arr(10000) == 10001
245 ms ± 56.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [6]: %timeit list_append(10000) == 10001
8.12 ms ± 978 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [7]: %timeit list_new(10000) == 10001
241 ms ± 48.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

---

このコード片だけだとdtypeがわかりませんが、numpy.ndarrayは固定の大きさの配列を背後に持っている以上、
配列の大きさ×(入っている文字列の最大長×α)
のメモリを使います。

In [1]: import numpy as np

In [2]: np.array([['0', 'a']])
Out[2]: array([['0', 'a']], dtype='<U1')

In [3]: np.vstack((np.array([['0', 'a']]), [['bbbbb', 'ccccc']]))
Out[3]:
array([['0', 'a'],
       ['bbbbb', 'ccccc']], dtype='<U5')

In [4]: np.array([['0', 'a']]).nbytes
Out[4]: 8

In [5]: np.array([[['0', 'a'], ['b', 'c']]]).nbytes
Out[5]: 16

In [6]: np.array([[['0', 'a'], ['bbbbb', 'ccccc']]]).nbytes
Out[6]: 80

vstackによって、もともとの「入っていた文字列の最大長」より長い文字列を追加するとdtypeが変わっているのが分かりますか。
固定の配列の大きさがdtypeの変化に見合った分大きくなっているのが分かりますか。

質問のソースはnumpy.ndarrayを使うメリットを捨てて、デメリットばかりを背負っているように見えます。
（再度ですが、このコード片だけで想像できる範囲の話です。「dtypeがobjectにしてる」とか、「そういったことが起きないように注意を払っている」なら後半は無視していただいてかまわないのですが、この質問が出るということはそうではないだろうとも想像します）

Comments

[nifch]

比較検証までしてくださり大変わかりやすかったです。
「ndarrayは固定長の配列の操作に用いる」という前提を理解できず、やってしまっていました。
dtypeもご指摘の通りunicodeです。
タプルリストでappendし、最後にndarrayに変換しようと思います。

ところでndarrayは「固定の大きさの配列を背後に持っている」ためその大きさに比例したメモリを使用するとおっしゃっていましたが、リストで消費するメモリの大きさはndarrayのそれに比べて小さいため、処理に大きな差が生まれる　ということなのでしょうか？

[quickquip]

リストは「可変である」ことが前提で、「オブジェクトへの参照」を保持します。
1バイトの文字列と100MBの文字列を保持したリストは、「1バイトの文字列」と「100MBの文字列」と「2個の参照」を保持します。「1GBバイトの文字列」をappendすると「2個の参照」が「3個の参照」になって参照を2個コピーするだけで済む（と想像されます。正しくは実装は知りません）。「1バイトの文字列」「100MBの文字列」「1GBバイトの文字列」はコピーも移動もしません。

[nifch]

ありがとうございます。理解できました。
それに対して私はvstackで毎回配列のコピーを行っていたため処理が大きくなった　ということですよね、、？

[nifch]

教えていただいたとおりリストで実行したところ、20分もかからず完了しました。
ありがとうございました。