set で重複を除去する

「もう出た値か」を配列に聞く

タグや都市の記録から重複を取り除きます。結果の配列に既にあるかを調べ、なければ追加する方法でも答えは出ます。ただし、配列にあるかどうかは先頭から順に探すため、結果が増えるほど確認も増えます。

異なる値が n 個並ぶ場合、後半ほど長い配列を探します。比較回数は 0 + 1 + … + (n − 1) です。1万個なら 10000 × 9999 ÷ 2 = 49995000回になります。これはすべて異なる場合の数です。

「あるかどうか」を答える集合

set は同じ値を重ねて持たない集合です。Python では add で値を加え、in であるかどうかを確かめます。

seen = set()
seen.add("tokyo")
seen.add("osaka")
seen.add("tokyo")
print(len(seen))         # 2
print("osaka" in seen)   # True
print("kyoto" in seen)   # False

len は種類数です。tokyo を2回加えても増えません。True はある、False はないという結果です。出現回数は次の回の辞書に保存します。

値から置き場所を計算して探す仕組みにより、追加と存在確認は平均 O(1) です。置き場所が重なる場合などもあるため、毎回必ず一定時間という保証ではありません。n個を追加する重複除去は平均 O(n) と考えます。

並び順は別に決める

JavaScript の Set は追加順を保ちます。順序の保証は言語ごとに確認します。数値の昇順には並べ替えが必要です。

console.log([3, 20, 100].sort());                // [100, 20, 3]
console.log([3, 20, 100].sort((a, b) => a - b)); // [3, 20, 100]

既定の sort は文字として比べるため、100が20より前になります。a - b は数値の大小で比べる指定です。昇順も求めると、並べ替えの時間も必要です。

例題で確かめる

記録された値 [8, 2, 8, 15, 2] から重複を除き、数値の昇順で表示します。左から集合への追加を追います。

残る種類は8、2、15の3つです。数値として並べ替えた答えは [2, 8, 15]。重複した2件が減り、5 − 2 = 3件になっています。