1. 問題

まず問題を説明したいが説明すること自体が難しい。

実装したいのは最初の行から自分自身の行までの要素のユニークカウント。

文章だけでは表現が難しいのでデータで説明します。

1.1. 問題データ

下記のようなquestionに対して…​

question

7

7

1

5

9

8

7

5

8

6

1.2. 答え

answerのように集計した結果を実装する。

question answer 説明

7

1

初値+1

7

1

+0

1

2

初値+1

5

3

初値+1

9

4

初値+1

8

5

初値+1

7

5

+0

5

5

+0

8

5

+0

6

6

初値+1

2. 問題について

説明が難しいので検索して調べるのも難しい。

日本語では有用な情報を検索できず英語でやっと有用な情報を見つけることができました。

検索できた最も有用だったページがこちら。

Calculating a unique count within a rolling time window @ stackexchange.com

実装方法はこちらの内容を参考にしました。

私の問題との違いはrolling sizeが不要なこと。

私の問題では最初の行からすべてカウント対象です。

3. 実装

２種類の実装方法を紹介します。

  1. expanding + nunique

  2. collections.Counter

実はgroupby+firstを使用する方法も思いついたのですが実装が複雑になってしまうため今回は除外しました。

実装の簡便度と処理速度を整理すると下記のようになります。

type 簡便度 処理速度

1. ex+nun

○

×

2. col.Con

×

○

処理速度を測定してみると明らかに大きな差が生じるので2. のcollections.Counterを使用する実装がおすすめです。

expanding+nuniqueを使用する方法はデータ件数が多いと現実的な時間では処理できなくなってしまいます。

3.1. 問題データの作成

example.py
import random
import pandas as pd
from collections import Counter


random.seed(0)
q = pd.Series(
    [
        random.randint(1, 10)
        for i in range(10)
    ]
)
q
output
In [3]: q
Out[3]:
0    7
1    7
2    1
3    5
4    9
5    8
6    7
7    5
8    8
9    6
dtype: int64

3.2. 実装１. expanding + nunique

example.py
a = (
    q
    .expanding()
    .apply(
        lambda x: x.nunique()
    )
)
a
output
In [134]: a
Out[134]:
0    1.0
1    1.0
2    2.0
3    3.0
4    4.0
5    5.0
6    5.0
7    5.0
8    5.0
9    6.0
dtype: float64

3.3. 実装２. collections.Counter

example.py
def expanding_nunique(s):
    uniq = Counter()
    result = list()
    for x in q:
        uniq.update(str(x))
        result.append(len(uniq))
    result = pd.Series(result)
    return result

expanding_nunique(q)
output
In [135]: expanding_nunique(q)
Out[135]:
0    1
1    1
2    2
3    3
4    4
5    5
6    5
7    5
8    5
9    6
dtype: int64

4. 処理時間の計測

ipythonの%%timeitを使用して処理時間を計測しました。

type 処理時間

1. ex+nun

2490us

2. col.Con

216us

10行のデータで10倍の差が開きました。

件数が多くなればもっと差が開きます。

そして件数が多すぎるとexpanding+nuniqueでは現実的な時間では処理ができなくなってしまいます。

4.1. expanding+nunique

output
In [136]:
%%timeit
a = (
    q
    .expanding()
    .apply(
        lambda x: x.nunique()
    )
)
a
--
2.49 ms ± 294 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

4.2. collections.Counter

output
In [137]:
%%timeit
expanding_nunique(q)
--
216 µs ± 25.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

5. まとめ

地味に面倒で情報も少ない問題の実装方法について処理時間も考慮して検討しました。

計算量オーダーについて理解している方なら困らずに実装可能かもしれませんが慣れていない方にとっては注意が必要な問題だと思います。