質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

pandas

Pandasは、PythonでRにおけるデータフレームに似た型を持たせることができるライブラリです。 行列計算の負担が大幅に軽減されるため、Rで行っていた集計作業をPythonでも比較的簡単に行えます。 データ構造を変更したりデータ分析したりするときにも便利です。

Q&A

解決済

1回答

14508閲覧

Python pandas 差分のある2つのデータフレームを比較して結合する際の計算量と時間について

_Victorique__

総合スコア1392

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

pandas

Pandasは、PythonでRにおけるデータフレームに似た型を持たせることができるライブラリです。 行列計算の負担が大幅に軽減されるため、Rで行っていた集計作業をPythonでも比較的簡単に行えます。 データ構造を変更したりデータ分析したりするときにも便利です。

0グッド

0クリップ

投稿2019/04/16 09:48

編集2019/04/17 04:04

2つの差分があるデータフレームを結合するのに以下のコードを利用します。
(その他良い方法があれば教えて欲しいです)

python

1import pandas as pd 2 3df1 = pd.DataFrame([["Jack","Male","USA",20,"mucsician","rock","movie"], 4 ["Mary","Female","Canada","game",24,"unemployed","None"], 5 ["Marco",25,"Italy","designer","fashion","tennis","None"], 6 ["Isabel","Female","France",24,"shopping","actress","None"]]) 7 8df2 = pd.DataFrame([["Jack","Male","USA",20,"mucsician"], 9 ["Mary","Female","Canada",24,"unemployed"], 10 ["Marco","None","Italy",25,"designer"], 11 ["Isabel","Female","France",24,"actress"]]) 12 13ret = pd.concat([df2, df1], axis=1).apply(lambda d: d.drop_duplicates().reset_index(drop=True), axis=1) 14print(ret) 15# 0 1 2 3 4 5 6 16# 0 Jack Male USA 20 mucsician rock movie 17# 1 Mary Female Canada 24 unemployed game None 18# 2 Marco None Italy 25 designer fashion tennis 19# 3 Isabel Female France 24 actress shopping None 20

差分のある2つのデータはそれぞれ100万づつあります。共通の要素をもつ二つのデータフレームを探し、結合するという作業をしたいです。
単純にやろうとすると、

  • 条件にマッチするペアのデータフレームを探しだす(O(N))
  • データを結合する

という作業をN個の要素に対してやるのでO(N^2)の時間がかかることになります。
今回の場合、N=1000000なので10^13の計算量がかかります。
とてもじゃないですが計算が終わらないことが予想されます。
pandasの使う関数によっては実行時間を減らすことができるかもしれません。ですがそれでも計算時間は多すぎます。

上記を満たす、条件にmatchする際に最適なメソッドと結合の際に最適なメソッドはどれが良いでしょうか?
よろしくお願いします。

追記

例えば以下のデータフレームがあるとします。

python

1df1 2# 0 1 2 3 4 5 6 3# 0 Jack Male USA 20 mucsician rock movie 4 5df2 6# 0 1 2 3 4 5 6 7# 0 Jack Male USA 20 mucsician rock NaN 8# 1 Mary Female Canada 24 unemployed game NaN 9# 2 Marco None Italy 25 designer fashion NaN 10# 3 Isabel Female France 24 actress shopping NaN

比較の方法としては0~5までのカラムを比較して一致しているものを全部取り出すという操作がしたいです。
上記の例だと行インデックス0が条件に一致します(一つだけとは限らない)
この場合、カラム全部を指定すれば検索できるとは思うのですが、全部指定するのはスマートじゃないと思っています。
もっとスマートに比較して検索する方法はありますでしょうか?

追記2

・データフレームM, N
・データ数
M, N共に百万程度(数は一致しない)
・カラム数
M = 7
N = 10
N(05のカラム) ≡ N(05のカラム) 完全一致でペアとみなす
・検索と結合
Mを元にNを走査し、マッチするものをマージして新しいデータフレームに追加

追記にも書きましたが、完全一致のスマートな書き方はありますでしょうか?

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

TakaiY

2019/04/16 11:15

DataFrameには、drop_dupulicates() という関数がありますが、これを使った場合にどれくらいかかるのでしょう。 また、その時間をどれくらいに縮めたいのでしょうか。
magichan

2019/04/16 11:21

2つのデータフレームを結合する際に、質問のコードではお互いのIndexが対応しているような記述となっておりますが、実際は何を持って対応している(ペアである)と判断するのでしょうか? また、それぞれのデータフレームにおいてペアになる対象がない場合はどのような処理を行うべきなのでしょうか。
_Victorique__

2019/04/17 01:15

どれくらいという時間の目安はありません。 最速の方法が知りたいです。 実際はペアが存在しないものがあります(どちらも同じ100万というわけではない)。なので、結合する側のデータフレームと同じ部分が含まれているペアを探しだす必要があります。同じカラムの項目が存在しているのでそこを比較すればペアを特定することが可能です。
magichan

2019/04/17 02:15

すみません。追加質問です。 『比較の方法としては0~5までのカラムを比較して一致しているものを全部取り出す・・・(一つだけとは限らない)』 とありますが、0~5までのカラムが全て一致したものが結合対象なのでしょうか?それとも1つでも一致したものが結合対象なのでしょうか? また、結合対象はかならず 1:1 の対応なのでしょうか?それとも 1:n または m:n の結合もありえるのでしょうか?
can110

2019/04/17 06:09

例示では df1の["Marco",25,"Italy","designer","fashion","tennis","None"]と df2の["Marco","None","Italy",25,"designer"]が一致とみなされているようですが 「N(0~5のカラム) ≡ N(0~5のカラム) 完全一致」の「完全一致」というのがよく分かりません。 一般的な完全一致とは、列0~5の値が順序も同じの場合一致していると考えるかと思うのですが この問題では、列0~5の値は順不同で(集合とみなして)一致と判断するということでしょうか?
_Victorique__

2019/04/17 06:14

申し訳ないです。例示のデータは不備があります。 正確には順序も同じ、値も同じものを完全一致としたいです。
can110

2019/04/17 06:21

了解です。もう一点 df1が[a,b,c,d,e,f,hoge]、df2が[a,b,c,d,e,f,huga,h,i,j] のように列0~5列まで完全一致しているのでマージすべきと思いますが 6列目が異なる値「hoge」と「huga」となっている場合、 マージ後の列0~9の値はどのようになるべきかを例示ください。
_Victorique__

2019/04/17 07:11

Mの比較部以外の部分に関しては、一致していてもいなくてもNの値で上書きしたいと考えています。 つまり、0〜5列は共通で、それ以降はNの値のデータフレームということになります。
can110

2019/04/17 07:49

なるほど。了解しました。
guest

回答1

0

ベストアンサー

以下、問題を単純化するために列数はM(=df1)=3, N(df2)=4、完全一致とみなす列は先頭2列、値は整数とします。

まず、問題のシンプルな回答としては.mergeを使った以下のようになるかと思います。
すなわち、先頭2列をキーとして内部結合し、重複する列のうちN側のみ残します。

Python

1import pandas as pd 2import numpy as np 3 4df1 = pd.DataFrame([[1,1,2], 5 [1,2,3]]) # この行がペアになる 6 7df2 = pd.DataFrame([[1,2,4,5], # この行がペアになる 8 [2,3,3,3]]) 9 10 11# 先頭2列で内部結合 12# 重複列において右側はそのまま、左側の重複列名には「_dup」を付加する 13df = pd.merge(df1,df2,on=list(range(2)), how='inner',suffixes=['_dup','']) 14 15df = df.drop('2_dup', axis=1) # 左側の重複列は不要なので削除 16print(df) 17""" 18 0 1 2 3 190 1 2 4 5 20"""

.mergeの内部で具体的にどのように処理されているかは不明ですが

という作業をN個の要素に対してやるのでO(N^2)の時間がかかることになります。

よりは高速だと思われます。

上記の処理でも遅い場合は、先頭2列をマルチインデックスにして同様に処理してみてください。
一般的に、テーブル構造に対してインデックスを張ると、内部にキーテーブルなどが作成され、キーによるアクセスでの大幅な速度アップ、極端に云えばO(1)程度が見込めます。
これがpandasでも通用すれば速度は速くなると思われます。

Python

1import pandas as pd 2import numpy as np 3 4df1 = pd.DataFrame([[1,1,2], 5 [1,2,3]]) # この行がペアになる 6 7df2 = pd.DataFrame([[1,2,4,5], # この行がペアになる 8 [2,3,3,3]]) 9 10# 先頭2列をマルチインデックスにする 11df1 = df1.set_index(list(range(2)), drop=True) 12df2 = df2.set_index(list(range(2)), drop=True) 13 14# インデックスで内部結合 15# 重複列において右側はそのまま、左(M)側の重複列名には「_dup」を付加する 16df = pd.merge(df1,df2,left_index=True,right_index=True, how='inner',suffixes=['_dup','']) 17 18df = df.drop('2_dup', axis=1) # 左(M)側の重複列は不要なので削除 19df = df.reset_index() # マルチインデックスを通常の(シングル)インデックスに戻す 20print(df) 21""" 22 0 1 2 3 230 1 2 4 5 24"""

マルチインデックスにしても速度に変化が見られない場合は、以下のように自力で先頭2列からハッシュ値を算出し、インデックスに指定してみてください。

Python

1import pandas as pd 2import numpy as np 3 4df1 = pd.DataFrame([[1,1,2], 5 [1,2,3]]) # この行がペアになる 6 7df2 = pd.DataFrame([[1,2,4,5], # この行がペアになる 8 [2,3,3,3]]) 9 10# 先頭2列(タプルとして)のハッシュ値を得る 11df1['hash'] = df1.apply(lambda r: hash((r[0],r[1])),axis=1) 12df2['hash'] = df2.apply(lambda r: hash((r[0],r[1])),axis=1) 13 14# ハッシュ値をインデックスとする 15df1 = df1.set_index('hash',drop=True) 16df2 = df2.set_index('hash',drop=True) 17 18# インデックスで内部結合 19# 重複列において右側はそのまま、左(M)側の重複列名には「_dup」を付加する 20df = pd.merge(df1,df2,left_index=True,right_index=True, how='inner',suffixes=['_dup','']) 21 22# 左(M)側の重複列は不要なので削除 23for col in df.columns: 24 if '_dup' in str(col): 25 df = df.drop(str(col), axis=1) 26 27df = df.reset_index(drop=True) # 通常のインデックスに戻す 28print(df) 29""" 30 0 1 2 3 310 1 2 4 5 32"""

以上、実際に実行時間の計測や計算量の確認は行っておらず多くが推測による回答となりましたが、参考まで。

投稿2019/04/17 08:22

編集2019/04/17 09:07
can110

総合スコア38233

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

_Victorique__

2019/04/18 02:23

回答ありがとうございます! パターン分けまでされていて大変分かりやすいです。計測しながら試してみようと思います! もう一つ質問なのですが、drop関数に指定するカラム名に正規表現は使えないのでしょうか?調べてみた感じ、複数削除する場合はリストで指定するようになっていましたが、正規表現が使えれば簡単だと思いました。
can110

2019/04/18 02:53

計測結果は気になるので、結果が分かりましたらコメントなりで教えてください。 なお、カラム名に正規表現は使えないようです。
_Victorique__

2019/04/18 07:16

最初のコードで検証しました。 CPU Intel(R) Xeon(R) CPU E5-2676 v3 @ 2.40GHz メモリ 4GB データ数:190万と130万 100回merge平均:1.86秒 これだけでもうめちゃくちゃ早いですね。
can110

2019/04/18 07:44

予想よりずいぶん速くて驚きです。 最初のコードのon指定で内部的にインデックスが張られているのかもしれません。 もしそうなら2,3番目のコードとの速度差はないかもしれませんね。
_Victorique__

2019/04/18 08:04

私もびっくりしました。 時間があるときに残りも試してみます。 またコメントで報告しますね。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問