DataFramesの連結が指数関数的に遅くなるのはなぜですか？

Question

私は大部分がバケットにデータを処理するために、DataFrameを処理する関数を持っていて、pd.get_dummies(df[col])を使用して特定の列にフィーチャのバイナリ行列を作成します。 （メモリの外に出るとクラッシュするiPythonを引き起こす）一度この機能を使用して、私のすべてのデータの処理を回避するには

、私が使用してチャンクに大きなデータフレームが壊れています

chunks = (len(df)/10000) + 1 
df_list = np.array_split(df, chunks) 

pd.get_dummies(df)を自動的に作成します。 df[col]の内容に基づく新しい列で、dfの場合はdf_listでそれぞれ異なる可能性があります。

処理の後、私が使用して一緒に戻ってデータフレームを連結しています：

for i, df_chunk in enumerate(df_list): 
    print "chunk", i 
    [x, y] = preprocess_data(df_chunk) 
    super_x = pd.concat([super_x, x], axis=0) 
    super_y = pd.concat([super_y, y], axis=0) 
    print datetime.datetime.utcnow() 

を最初のチャンクの処理時間は完全に受け入れている、しかし、それはチャンクごとに成長！これは、増加する理由がないので、preprocess_data(df_chunk)とは関係ありません。 pd.concat()への呼び出しの結果、この時間が増加していますか？

以下のログを参照してください。これをスピードアップするための回避策は

chunks 6 
chunk 0 
2016-04-08 00:22:17.728849 
chunk 1 
2016-04-08 00:22:42.387693 
chunk 2 
2016-04-08 00:23:43.124381 
chunk 3 
2016-04-08 00:25:30.249369 
chunk 4 
2016-04-08 00:28:11.922305 
chunk 5 
2016-04-08 00:32:00.357365 

ありますか？私は2900チャンクを処理するので、どんな助けもありがとう！

Pythonの他の提案にもオープン！

Answer 1

forループ内でDataFrame.appendまたはpd.concatを呼び出すことはありません。それは二次的なコピーにつながる。

pd.concat新しいDataFrameが返されます。新しい DataFrameにスペースを割り当てる必要があり、古いDataFramesのデータを新しい DataFrameにコピーする必要があります。

super_x = pd.concat([super_x, x], axis=0) 

| iteration | size of old super_x | size of x | copying required | 
|   0 |     0 |   1 |    1 | 
|   1 |     1 |   1 |    2 | 
|   2 |     2 |   1 |    3 | 
|  ... |      |   |     | 
|  N-1 |     N-1 |   1 |    N | 

1 + 2 + 3 + ... + N = N(N-1)/2：（各xサイズ1を有すると仮定して）for-loop内部このラインによって必要とされるコピーの量を考えます。だから ループを完了するために必要なコピーはO(N**2)です。

今リストへの追加

super_x = [] 
for i, df_chunk in enumerate(df_list): 
    [x, y] = preprocess_data(df_chunk) 
    super_x.append(x) 
super_x = pd.concat(super_x, axis=0) 

がO(1)操作であり、コピーを必要としないことを検討してください。今すぐ ループが完了した後にpd.concatへの単一の呼び出しがあります。 super_xがこのように構築されたときに1だから、super_xはO(N) コピーを必要なサイズのN データフレームが含まれているため pd.concatへのこの呼び出しは、N個のコピーを行うことが必要です。

Answer 2

連結するたびに、データのコピーが返されます。

チャンクのリストを保持し、すべてを最後のステップとして連結します。

df_x = [] 
df_y = [] 
for i, df_chunk in enumerate(df_list): 
    print "chunk", i 
    [x, y] = preprocess_data(df_chunk) 
    df_x.append(x) 
    df_y.append(y) 

super_x = pd.concat(df_x, axis=0) 
del df_x # Free-up memory. 
super_y = pd.concat(df_y, axis=0) 
del df_y # Free-up memory.