配列内で重複のない連続領域の抽出

Question

Pythonで”配列内で重複のない右側からの連続領域の抽出”を　最も計算コストの低い方法で実現したいです。

具体的には、
[1,2,3,4,1,2,5]
という配列があったとして、右側から値を見ていき、重複が出るまで左に進む、
というようなイメージです。このケースでは得たい結果は
[3 4 1 2 5]
ということになります。

パッと思いつくのは、

arr = np.array([1,2,3,4,1,2,5])

max_index = 0
for i in arr:
    if arr[max_index:].size != np.unique(arr[max_index:]).size:
        max_index += 1

print(arr[max_index:])

のようなコードなのですが、配列を実質全部サーチするのに近い処理となり、
配列が長くなると処理時間が掛かりそうです。

上記コード以外で、何か良い方法があればご教示いただけますでしょうか

Answer 1

重複チェック用の変数をSet型か何かで用意しておいて、右から順にチェックしていけば良いのでは?
たとえば、こんな感じで。

import numpy as np

data = [1,2,3,4,1,2,5] * 10**5
arr = np.array(data)

duplicated = set()
res = []
for a in reversed(arr):
    if a in duplicated:
        break
    res.append(a)
    duplicated.add(a)

ans = np.array(res[::-1])
print(ans)

Comments

[lehshell]

append しない方が少し速そうです。
arr = np.array(data)
duplicated = set()
for i,a in enumerate(reversed(arr)):
    if a in duplicated:
        break
    duplicated.add(a)

ans = arr[len(arr)-i:]

[退会済みユーザー]

確かに。ただ、これだとarr内に重複が無い場合に arr[1:] となって1つ欠けませんか。
こちらの環境(Python 3.8.11)で試した限りでは、以下の方式でもlehshellさんの案と同じくらい速いです????

# 辞書順が保証される環境のみ
seen = {}
for a in reversed(arr):
if a in seen:
break
seen[a] = True
ans = np.array(list(reversed(seen)))

[lehshell]

失礼しました。確かに重複がない場合に欠けてしまいます。
set で行う場合は次のコードに修正が必要です。
arr = np.array(data)
duplicated = set()
idx = 0
for i,a in enumerate(reversed(arr)):
    if a in duplicated:
        idx = len(arr)-i
        break
    duplicated.add(a)

ans = arr[idx:]

[ppaul]

ftlobwさん、
ans = np.array(list(reversed(seen)))
よりも、
ans = list(seen.keys())[::-1]
の方が軽いでしょう。

[shinjukuzame]

回答およびその後のディスカッション、大変参考になりました。
ftlobw様、lehshell様、ppaul様、どうもありがとうございました。