Mexを求める時に要素の最大値がわからない場合に計算量を抑える方法

Question

前提・実現したいこと

Mex(要素に含まれていない最小の自然数)を求める際、シンプルに実装する場合mex1関数で、計算量を考える場合、要素の最大値が要素数に対して大きすぎない場合はmex2で求めるのがいいと考えたのですが、要素の最大値が定められていない場合は計算量に考慮する場合どのような実装方法がいいのか全く思いつかないです。mex1が一番いいのでしょうか。もし、知恵のある方がいたら、教えてくださるとうれしいです！

def mex1(inp):
    ans = 1
    while ans in inp:
        ans += 1
    return ans

def mex2(inp):
    N = max(inp)
    judge = [0] * (N+2)
    ans = 1
    for i in inp:
        judge[i] = 1
    while judge[ans] == 1:
        ans += 1
    return ans

Comments

[退会済みユーザー]

「要素は昇順にソート済で、全ての要素値は異なる」みたいな追加条件はありますか?

[makkesann5392]

要素はランダムでソートされていません。

[makkesann5392]

同じ要素値のものも複数含まれることもあります

[fana]

> 要素に含まれていない最小の値

ってどういう意味？
例えば，{ 3, -2400, 9 } とかいう３要素に対しては，何になる？

[makkesann5392]

説明不足で申し訳ないです。正確には要素に含まれていない自然数なので、その例では答えは1になります。

[fana]

単に，昇順にソートして要素を小さい側から見ていけばいいだけに思えますが，それだともう計算量の観点でアウトだという話なのでしょうか？

あと，mex2 って，
{ 1, 100臆万} だとか { -2400, -8 } とか言われた場合に大丈夫なんですか？

Answer 1

計算量を考える場合、要素の最大値が要素数に対して大きすぎない場合はmex2で求めるのがいいと考えたのですが、要素の最大値が定められていない場合は計算量に考慮する場合どのような実装方法がいいのか全く思いつかないです。

MEXを考える場合には要素数Nに対して[1, N]の範囲の要素しか考慮する必要はありません。
この範囲外にある要素はMEXに影響を与えないからです。

なのでこの範囲の要素だけ考慮するようにすれば、最大値が定まっていなくてもmex2のような方法でMEXを求めることが可能です。

Comments

[makkesann5392]

回答ありがとうございます！返信遅くなって申し訳ないです。
とてもシンプルなことですが目から鱗でした笑

Answer 2

計算量・考え方はmex2と同じですが、オマケでnumpyを使ったmex5を作ってみました。
速度はmex2より2割くらいマシですが、mex1, 3, 4より遅いですね。

---

ディスカッションのスタート用に何パタンか書いてみました。

ソートして二分探索するとワースト実行時間を改善できるかと思いましたが、

• おそらくmex3にはバグがある
• 探す値がリストの前半にある場合、シンプルな実装より遅い

ので、自分で書くならmex4ですかね。

from timeit import timeit
from random import choices, shuffle
import numpy as np

def mex1(inp):
    check = set(inp)            # set化しないと遅い
    ans = 1
    while ans in check:
        ans += 1
    return ans

def mex2(inp):
    N = max(inp)
    judge = [0] * (N+2)
    ans = 1
    for i in inp:
        judge[i] = 1
    while judge[ans] == 1:
        ans += 1
    return ans

# 二分探索っぽく探す(未チェック)
def mex3(inp):
    arr = sorted(set(inp))
    lb, ub = -1, len(arr)
    while ub > lb + 1:
        mid = (lb + ub) // 2
        lb, ub = (mid, ub) if arr[mid] == mid + 1 else (lb, mid)
    return arr[lb] + 1 if lb != -1 else 1

# mex1を書換えただけ
def mex4(inp):
    check = set(inp)
    return next(i for i in range(1, len(check)+2) if i not in check)

# mex2と同じ考え方をnumpyブール型で
def mex5(inp):
    arr = np.array(inp)
    sieve = np.zeros(len(inp)+10, dtype=bool)
    sieve[0] = True
    sieve[np.where(arr > len(inp), 0, arr)] = True
    return np.where(sieve == False)[0][0]

size = 10**6
ans = {987654, 525252}          # この数字以外のリストを生成
arr = [i for i in range(1, size) if i not in ans]
arr = arr + list(choices(arr * 5, k=size*3)) # 重複を入れていろいろまぜる
shuffle(arr)

r1 = mex1(arr)
r2 = mex2(arr)
r3 = mex3(arr)
r4 = mex4(arr)
print(r1 == r2 == r3 == r4, r1, min(ans)) # 同じ答えになっているかチェック

print('mex1', timeit('mex1(arr)', globals=globals(), number=5))
print('mex2', timeit('mex2(arr)', globals=globals(), number=5))
print('mex3', timeit('mex3(arr)', globals=globals(), number=5))
print('mex4', timeit('mex4(arr)', globals=globals(), number=5))

# mex1 2.0568706
# mex2 6.3567640999999995
# mex3 1.801850899999998
# mex4 2.099546499999999

Comments

[bsdfan]

mex4 ですが、range で +2 しないと、例えば mex4([1])で StopIteration になります。
next(generator)で先頭だけを取り出す書き方はいいですね。

[退会済みユーザー]

コメントありがとうございます。元々はinp内に必ず穴がある想定だったので len(check)で十分でした。書くなら len(check) +2 か len(check) +0 のどちらかですね。

[makkesann5392]

丁寧な回答ありがとうございます！返信遅くなって申し訳ないです。
ハッシュ探索についての知識がなかったので勉強になりました！また、他のパターンについても勉強させていただきます！
丁寧でわかりやすかったのでベストアンサーにさせていただきます！
また機会があればよろしくお願いしますm(__)m

Answer 3

inpがリストだと mex1() は O(N^2) ですが、

Find Minimum excludant ( MEX )

に書いてあるようにinpをリストからハッシュに変換してからmex1()と同じことをやれば O(N) です。

Comments

[makkesann5392]

回答ありがとうございます！返信遅くなって申し訳ないです。
ハッシュ探索についての知識がなかったのでとてもためになりました！