python3とpandasを使っています。  
df1,df2の2つのDataframeのうち同じIDの人物の日付を比較し、期間重複がある行のIDを取り出したいです。  
実際には10万行ほどあります。

```

    data1 = [[1, "2010-01-01", "2010-01-20"], [1, "2010-03-20", "2010-03-30"],
            [2, "2010-02-01", "2010-04-20"], [3, "2010-06-10", "2010-06-15"],
            [3, "2010-06-20", "2010-06-30"], [3, "2010-07-10", "2010-06-20"]]
    
    data2 = [[1, "2010-01-15", "2010-01-30"], [1, "2010-04-20", "2010-04-30"],
            [2, "2010-05-01", "2010-05-10"], [2, "2010-05-20", "2010-05-25"],
            [3, "2010-02-01", "2010-02-15"], [3, "2010-06-15", "2010-06-25"]]
    
    columns1 = ["ID", "start_date", "end_date"]
    
    df1 = pd.DataFrame(data=data1,columns=columns)
    df2 = pd.DataFrame(data=data2,columns=columns)
    
```

これをIDで比較して、下記のようなリストがほしいです。

result_list = [1,3]

```

    result_list = []
    for index,row1 in df1.iterrows():
        if not row1["ID"] in result_list:
            for index,row2 in df2.iterrows():
                if row1["ID"] == row2["ID"] and row2["start_date"] <= row1["end_date"] and row2["end_date"] >= row1["start_date"]:
                    result_list.append(row1["ID"])
                    break
    result_list = list(set(result_list))
    result_list
    
```

試行錯誤して，求める結果を得ることができましたが  
効率が悪いような気がしてなりません…多重for文を書かずに済む方法はないものでしょうか．  
アドバイス宜しくお願い致します.
CC BY-SA 4.0
2019-08-22T12:04:26.953
57545
2022-04-25T00:50:37.217
35563
question
python pandas
2つのDataframeで期間重複するIDを抽出したい
**再検討：**  
その後、高速化の記事など眺めながら考えていて、「多重for文を書かない」というか、それに類似するであろう「ループを書かない」前提条件を思いっきり無視し、かつ全然簡潔では無い内容ですが、頭の体操みたいなものとして、高速化は出来るだろう処理を作ってみました。

こんな考え方にしています。

・データは`ID`を1番目、`start_date`を2番目のキーとしてソート済みであることを前提にする  
・1つのDataFrameの中では重複は無いものとする  
・メインの処理では pandas は使わず、Python基本のリストを使う  
・`ID`や`start_date`, `end_date`の範囲をチェックし、不要な範囲での重複検出ループを回さない

チェック前のデータを(csv等で?)作成する時点であらかじめソートしておくくらいは前提として許されるのでは？  
一応以下の2行を呼び出せば出来ますが、それはそれで時間とメモリがかかるので。  
プロファイラではかると、約 4.5ms, 0.406MiB 程度かかっていました。

```

    df1 = df1.sort_values(['ID','start_date'])
    df2 = df2.sort_values(['ID','start_date'])
    
```

そして以下が重複検出処理です。以下の全部で、約 1ms弱, 0.078MiB 程度かかっていました。

```

    # pandas DataFrame から Python基本のリストへ
    #
    df1limit = len(df1)
    df2limit = len(df2)
    df1ID = df1['ID'].tolist()
    df1start = df1['start_date'].tolist()
    df1end = df1['end_date'].tolist()
    df2ID = df2['ID'].tolist()
    df2start = df2['start_date'].tolist()
    df2end = df2['end_date'].tolist()
    
    # メインの重複検出処理
    #
    result_list = []
    df1index = 0
    df2index = 0
    while df1index < df1limit:
      CurrentID = df1ID[df1index]
    
      # df1 と df2 で比較開始時の'ID'が同じになるようにリストのインデックスを調整
      #
      df2IDFounded = False
      while df2index < df2limit:
        if CurrentID > df2ID[df2index]:  # df2 の方の'ID'が小さいので読み飛ばし
          df2index += 1
        else:
          if CurrentID == df2ID[df2index]:
            df2IDFounded = True
          break
      else:
        break  # df2 が終わったので検出処理終了
    
      if not df2IDFounded:  # df1 と同じ'ID'が df2 に無ければ、df1 の'ID'を読み飛ばす
        while df1index < df1limit and CurrentID == df1ID[df1index]:
          df1index += 1
        continue
    
      # 日付比較して重複検出する処理
      #
      df2compareTop = df2index  # df2 の同じ'ID'の先頭インデックスをセーブ
      DuplicateFounded = False  # 重複検出フラグクリア
    
      while df1index < df1limit and CurrentID == df1ID[df1index]:  # df1 の'ID'が同じ間はループ
        StartDate1 = df1start[df1index]  # df1 の比較用日付をリストから取得(少しでも時間短縮)
        EndDate1 = df1end[df1index]      #   〃
        df2index = df2compareTop         # df2 の同じ'ID'の先頭インデックスをリストア
    
        while df2index < df2limit and CurrentID == df2ID[df2index]:  # df2 の'ID'が同じ間はループ
          if df2start[df2index] <= EndDate1 and df2end[df2index] >= StartDate1:  # 重複検出の比較処理
            result_list.append(CurrentID)  # 重複検出したのでリストへ追加
            DuplicateFounded = True        # 重複検出フラグ設定してループ終了
            break
          elif df2start[df2index] > EndDate1:  # これ以後は重複しないのでループ終了
            break
          else:
            df2index += 1     # df2 の同じ'ID'の次のデータへ
        #
        # df2 との重複検出処理ループの底
    
        df1index += 1
        if DuplicateFounded:  # 重複検出したのでループ終了して次の'ID'へ
          break
      #
      # df1 の同一'ID'での重複検出処理ループの底
    
      while df1index < df1limit and CurrentID == df1ID[df1index]:  # df1 の次の'ID'のまで読み飛ばし
        df1index += 1
      while df2index < df2limit and CurrentID == df2ID[df2index]:  # df2 の次の'ID'のまで読み飛ばし
        df2index += 1
    
    # 全部の重複検出処理ループの底
    
    print(result_list)  # 重複'ID'リスト表示
    
```

* * *

コメントで聞いておいて答えも待たずに書いてしまいます。  
かえって効率が悪いかもだったり、forのネストが深かったりしますが、一応両方思いついたので。

ちなみに、質問記事ソースコードの`data1`の最後`[3, "2010-07-10",
"2010-06-20"]`の終了期日は、おそらく`"2010-07-20"`の書き間違いでしょう。  
そして`columns1 = ["ID", "start_date",
"end_date"]`の変数名も数字の付かない`columns`の書き間違いでしょうね。

* * *

**「1つのDataFrame内でも重複とみなす」** 方法  
参考記事  
[pandas
Timestampとdate_rangeの使い方](https://qiita.com/u1and0/items/ed37fa4571f327b897e0)  
[Python pandas 図でみる データ連結 /
結合処理](http://sinhrks.hatenablog.com/entry/2015/01/28/073327)  
[pandas.DataFrame, Seriesの重複した行を抽出・削除](https://note.nkmk.me/python-pandas-
duplicated-drop-duplicates/)

あまり洗練されては無さそうな強引な方法です。  
ただ、必要ならば全ての重複期間のデータを取得することも出来ます。

  * 両方のDataFrameを混ぜてしまう
  * 'ID' でグルーピングし、以下を ID 毎に処理する
  * 該当期間の1日を1件としてDataFrameに展開して連結する
  * pandasの機能を使って1行で重複のチェックと重複件数取得(件数自身には意味なし)
  * 重複があれば続けて結果リストにIDを追加する処理が行われる
  * 重複が無い場合は例外になってID追加処理が行われないのを利用する、例外は無視する

以下の様な処理になります。

```

    df3 = pd.concat([df1,df2], ignore_index=True)
    
    result_list = []
    for ID, grp in df3.groupby('ID'):
      arr = []
      for index, item in grp.iterrows():
        arr.append(pd.DataFrame(pd.date_range(start=item['start_date'], end=item['end_date'])))
    
      arr = pd.concat(arr, ignore_index=True)
      try:
        dup = arr.duplicated().value_counts()[True]
        result_list.append(ID)
      except:
        pass
    
    print(result_list)
    
```

* * *

**「2つのDataFrame間で重複しないと重複とは見なさない」** 方法  
参考記事  
[日付期間の重複チェック](https://qiita.com/yaju/items/a58a78f41ee41258a5fe)  
[2つの期間が重なり合うかどうかを判定する。](http://koseki.hatenablog.com/entry/20111021/range)  
[Pythonで多重ループ（ネストしたforループ）からbreak](https://note.nkmk.me/python-break-nested-
loops/)

for のネストは深くなりますが、1件毎のID比較が省略されるので少しは効率が上がるかも。

  * DataFrame1を'ID' でグルーピングし、以下を ID 毎に処理する
  * DataFrame2から同じ ID のデータを抽出する
  * DataFrame1の各データを中間ループ、同IDで抽出したDataFrame2のデータを内側ループとし、参考記事の方法で重複チェック
  * 重複があれば結果リストにID追加処理を行い、中間ループもbreakして次のIDの処理に行く

以下になります。

```

    result_list = []
    for ID, grp1 in df1.groupby('ID'):
      grp2 = df2[df2['ID'] == ID]
      for index1, item1 in grp1.iterrows():
        start1 = item1['start_date']
        end1   = item1['end_date']
        for index2, item2 in grp2.iterrows():
          if item2['start_date'] <= end1 and start1 <= item2['end_date']:
            result_list.append(ID)
            break
        else:
          continue
        break
    
    print(result_list)
    
```

* * *

@Yuki Inoueさんの冒頭を見て「pandas for 遅い」で検索したら、たしかに色々あるようで、そういう主義にもなりますね。  
メモ兼用として参考に置いておきます。  
[pandas.DataFrame のforループをゆるふわ△改良して300倍高速化する](https://kunai-
lab.hatenablog.jp/entry/2018/04/08/134924)  
[うわっ…私のpandas、遅すぎ…?って時にやるべきこと（先人の知恵より）](https://shinyorke.hatenablog.com/entry/pandas-
tips)  
[pandasで1000万件のデータの前処理を高速にするTips集](https://qiita.com/kishiyama/items/b9d0a7ba3f03fd4089f3)  
[pandasで複数カラムを参照して高速に1行1行値を調整する際のメモ](https://qiita.com/simonritchie/items/dd737a52cf32b662675c)  
[pandas
いかたこのたこつぼ](https://ikatakos.com/pot/programming/python/packages/pandas) /
[PandasのDataFrameのappendの高速化](https://takazawa.github.io/hobby/pandas_append_fast/)  
[python – Pandas：遅い日付変換](https://codeday.me/jp/qa/20190301/344891.html) /
[遅いpandasのread_csvを高速化する方法(dask)](https://qiita.com/lucky0707/items/ff8ce66a40c492945229)  
[今すぐ使えるpandas高速化テクニック](https://qiita.com/KTaskn/items/07e49a4f21e9afdad35f) /
[Pandasでforループを回して処理する方法と注意点](https://deepage.net/features/pandas-
iteration.html#for%E3%83%AB%E3%83%BC%E3%83%97%E3%82%92%E4%BD%BF%E3%82%8F%E3%81%AA%E3%81%84%E6%96%B9%E6%B3%95)  
[Pythonの高速化のまとめ Ver.1](https://www.crz33.com/software/python/python_speedup) /
[開発者がビッグデータ分析にPythonを使う時によくやる間違い](https://postd.cc/top-mistakes-python-big-
data-analytics/)  
[ISOに従っていないデータをpandas.to_datetime()すると500倍以上遅くなる可能性がある話とその対策](https://blog.ikedaosushi.com/entry/2018/10/03/033435)

* * *

**追記： &訂正**  
実は性能は質問の処理が一番早かったですね。  
あくまで質問のデータ件数・内容の条件です。10万件ならば全然変わるでしょう。  
**計測の仕方を間違えていたので数値を訂正**

所要時間  
質問:4.7ms前後, @kunif-1:20～21ms, @kunif-2:8ms前後, @Yuki Inoue:17.7ms前後 でした。

[Python プログラムの実行パフォーマンスを計測する](https://www.yoheim.net/blog.php?q=20171005)
の「行ごとの処理時間を取得する」で、df1,df2を作成した後の処理部分を計測

メモリ使用増加量  
質問:0.110MiB, @kunif-1:0.773MiB, @kunif-2:0.370～0.430MiB, @Yuki
Inoue:0.797～0.812MiB でした。

同じ記事の「メモリの使用量を調べる」のmemory_profilerを使って、同様にdf1,df2を作成した後の処理部分を計測
CC BY-SA 4.0
2019-08-23T04:19:21.147
57560
2019-08-27T12:00:12.783
2019-08-27T12:00:12.783
26370
26370
57545
answer
For 文を pandas で使いたくない派なので、ひたすらデータフレーム処理で重複を求めていくと、次のようになると思います。

```

    In [1]: import pandas as pd
    
    In [2]: data1 = [[1, "2010-01-01", "2010-01-20"], [1, "2010-03-20", "2010-03-30"],
          :         [2, "2010-02-01", "2010-04-20"], [3, "2010-06-10", "2010-06-15"],
          :         [3, "2010-06-20", "2010-06-30"], [3, "2010-07-10", "2010-07-20"]]
          :
          : data2 = [[1, "2010-01-15", "2010-01-30"], [1, "2010-04-20", "2010-04-30"],
          :         [2, "2010-05-01", "2010-05-10"], [2, "2010-05-20", "2010-05-25"],
          :         [3, "2010-02-01", "2010-02-15"], [3, "2010-06-15", "2010-06-25"]]
          :
          : columns = ["ID", "start_date", "end_date"]
          :
          : df1 = pd.DataFrame(data=data1,columns=columns)
          : df2 = pd.DataFrame(data=data2,columns=columns)
    
    In [3]: df = pd.concat([df1, df2], keys=["df1", "df2"])
          : df
    Out[3]:
           ID  start_date    end_date
    df1 0   1  2010-01-01  2010-01-20
        1   1  2010-03-20  2010-03-30
        2   2  2010-02-01  2010-04-20
        3   3  2010-06-10  2010-06-15
        4   3  2010-06-20  2010-06-30
        5   3  2010-07-10  2010-07-20
    df2 0   1  2010-01-15  2010-01-30
        1   1  2010-04-20  2010-04-30
        2   2  2010-05-01  2010-05-10
        3   2  2010-05-20  2010-05-25
        4   3  2010-02-01  2010-02-15
        5   3  2010-06-15  2010-06-25
    
    In [4]: stacked = df.set_index("ID", append=True).stack().to_frame()
          : stacked
    Out[4]:
                                  0
          ID
    df1 0 1  start_date  2010-01-01
             end_date    2010-01-20
        1 1  start_date  2010-03-20
             end_date    2010-03-30
        2 2  start_date  2010-02-01
             end_date    2010-04-20
        3 3  start_date  2010-06-10
             end_date    2010-06-15
        4 3  start_date  2010-06-20
             end_date    2010-06-30
        5 3  start_date  2010-07-10
             end_date    2010-07-20
    df2 0 1  start_date  2010-01-15
             end_date    2010-01-30
        1 1  start_date  2010-04-20
             end_date    2010-04-30
        2 2  start_date  2010-05-01
             end_date    2010-05-10
        3 2  start_date  2010-05-20
             end_date    2010-05-25
        4 3  start_date  2010-02-01
             end_date    2010-02-15
        5 3  start_date  2010-06-15
             end_date    2010-06-25
    
    In [5]: ordered = stacked.reset_index(level=2).sort_values(['ID', 0])
          : ordered
    Out[5]:
                      ID           0
    df1 0 start_date   1  2010-01-01
    df2 0 start_date   1  2010-01-15
    df1 0 end_date     1  2010-01-20
    df2 0 end_date     1  2010-01-30
    df1 1 start_date   1  2010-03-20
          end_date     1  2010-03-30
    df2 1 start_date   1  2010-04-20
          end_date     1  2010-04-30
    df1 2 start_date   2  2010-02-01
          end_date     2  2010-04-20
    df2 2 start_date   2  2010-05-01
          end_date     2  2010-05-10
        3 start_date   2  2010-05-20
          end_date     2  2010-05-25
        4 start_date   3  2010-02-01
          end_date     3  2010-02-15
    df1 3 start_date   3  2010-06-10
          end_date     3  2010-06-15
    df2 5 start_date   3  2010-06-15
    df1 4 start_date   3  2010-06-20
    df2 5 end_date     3  2010-06-25
    df1 4 end_date     3  2010-06-30
        5 start_date   3  2010-07-10
          end_date     3  2010-07-20
    
    In [14]: seq_df = ordered[["ID"]].reset_index()[["level_2", "ID"]].pipe(
           :     lambda df:
           :     df.assign(
           :         prev_level_2=df.groupby("ID").shift()
           :     )
           : )
           : seq_df
    Out[14]:
           level_2  ID prev_level_2
    0   start_date   1          NaN
    1   start_date   1   start_date
    2     end_date   1   start_date
    3     end_date   1     end_date
    4   start_date   1     end_date
    5     end_date   1   start_date
    6   start_date   1     end_date
    7     end_date   1   start_date
    8   start_date   2          NaN
    9     end_date   2   start_date
    10  start_date   2     end_date
    11    end_date   2   start_date
    12  start_date   2     end_date
    13    end_date   2   start_date
    14  start_date   3          NaN
    15    end_date   3   start_date
    16  start_date   3     end_date
    17    end_date   3   start_date
    18  start_date   3     end_date
    19  start_date   3   start_date
    20    end_date   3   start_date
    21    end_date   3     end_date
    22  start_date   3     end_date
    23    end_date   3   start_date
    
    In [15]: overlap_df = seq_df.pipe(
           :     lambda df:
           :     df[df["level_2"] == df["prev_level_2"]]
           : )
           : overlap_df
    Out[15]:
           level_2  ID prev_level_2
    1   start_date   1   start_date
    3     end_date   1     end_date
    19  start_date   3   start_date
    21    end_date   3     end_date
    
    In [16]: overlap_df["ID"].unique()
    Out[16]: array([1, 3])
    
```
CC BY-SA 4.0
2019-08-23T05:16:27.967
57561
2019-08-23T05:16:27.967
754
57545
answer
比較的ループ使わない感じで行ってみました。

  1. `df1`, `df2` それぞれに `interval`項目を用意
  2. `df1`, `df2` まとめた中で `ID`の一覧を用意 (今回のデータでは `1,2,3`になる)
  3. それぞれの `ID`で, Seriesを作って (`iv1`, `iv2`) overlapしてるか確認

注意点？

  * `ID`の一覧はループにしなくて構わないはず

  * [pandas.Interval](https://pandas.pydata.org/docs/reference/api/pandas.Interval.html) によると省略時は `closed=‘right’`で, 例えば `((1,3), (3,7))` の場合に 3はどちらに入るか。(問題になる場合もあるので)

  * 結果は, (今のところ) listではなく表示のみにしている (Trueは 被ってる意味)

```

    import pandas as pd
    data1 = [[1, "2010-01-01", "2010-01-20"], [1, "2010-03-20", "2010-03-30"],
            [2, "2010-02-01", "2010-04-20"], [3, "2010-06-10", "2010-06-15"],
            [3, "2010-06-20", "2010-06-30"], [3, "2010-07-10", "2010-07-20"]]
    
    data2 = [[1, "2010-01-15", "2010-01-30"], [1, "2010-04-20", "2010-04-30"],
            [2, "2010-05-01", "2010-05-10"], [2, "2010-05-20", "2010-05-25"],
            [3, "2010-02-01", "2010-02-15"], [3, "2010-06-15", "2010-06-25"]]
    
    columns1 = ["ID", "start_date", "end_date"]
    
    df1 = pd.DataFrame(data=data1, columns=columns1)
    df2 = pd.DataFrame(data=data2, columns=columns1)
    
    for df in (df1, df2):
        df['interval'] = df.astype({'start_date': 'M8', 'end_date': 'M8'}).apply(
            lambda v: pd.Interval(v.start_date, v.end_date), axis=1)
    
    for num in pd.unique(pd.concat([df1, df2]).ID):
        iv1, iv2 = [df.loc[df.ID == num, 'interval']for df in (df1, df2)]
        chk = iv2.map(pd.arrays.IntervalArray(iv1).overlaps)
        print(num, chk.map(any).any())
    
    # 1 True
    # 2 False
    # 3 True
    
```

* * *

#### (追記)

`df1`, `df2` に項目追加するのではなく, (それぞれに) Seriesを用意する方法  
処理の手順は元とほぼ変わらず

(`ID` が片側だけでなく両方に存在するなら, `iv2.index == iv.name` は `iv.name` だけで OK)

```

    iv1, iv2 = [df.astype({'start_date': 'M8', 'end_date': 'M8'})
                  .apply(lambda v: [v.ID, pd.Interval(v.start_date, v.end_date)], axis=1, result_type='expand')
                  .set_index(0)[1]   # 0,1 はそれぞれ ID, pd.Interval
                        for df in (df1, df2)]
    
    res = iv1.groupby(level=0).apply(lambda iv:
        iv2[iv2.index == iv.name].map(pd.arrays.IntervalArray(iv).overlaps)
                                 .map(any).any())
    res.index[res].to_list()
    # [1, 3]
    
```
CC BY-SA 4.0
2022-04-22T03:52:41.977
88447
2022-04-24T03:39:47.277
2022-04-24T03:39:47.277
43025
43025
57545
answer
ID毎に総当たりで比較。

参考：  
[【Python】ふたつの配列からすべての組み合わせを評価](https://kaisk.hatenadiary.com/entry/2014/11/05/041011)

```

    import numpy as np
    
    data1 = [[1, "2010-01-01", "2010-01-20"], [1, "2010-03-20", "2010-03-30"],
            [2, "2010-02-01", "2010-04-20"], [3, "2010-06-10", "2010-06-15"],
            [3, "2010-06-20", "2010-06-30"], [3, "2010-07-10", "2010-06-20"]]
    
    data2 = [[1, "2010-01-15", "2010-01-30"], [1, "2010-04-20", "2010-04-30"],
            [2, "2010-05-01", "2010-05-10"], [2, "2010-05-20", "2010-05-25"],
            [3, "2010-02-01", "2010-02-15"], [3, "2010-06-15", "2010-06-25"]]
    
    arr1 = np.array(data1)
    arr2 = np.array(data2)
    
    result_list = []
    
    for id in np.unique(arr1[:,0]):
        _arr2 = arr2[arr2[:,0] == id]
        if len(_arr2) == 0:
            continue
        _arr1 = arr1[arr1[:,0] == id]
        xx = np.array([[x for x in _arr1] for _ in range(len(_arr2))]).reshape(-1,3)
        yy = np.array([[y for _ in range(len(_arr1))] for y in _arr2]).reshape(-1,3)
        if np.any((xx[:,1] <= yy[:,2]) & (yy[:,1] <= xx[:,2])):
            result_list.append(id)
    
```
CC BY-SA 4.0
2022-04-24T08:13:27.167
88475
2022-04-25T00:50:37.217
2022-04-25T00:50:37.217
3060
52255
57545
answer