Pythonでビット配列を使って配列内の重複を検出する方法

n個の数値からなる配列があるとします。nは最大でも32,000であり、配列には重複した要素が含まれている可能性がありますが、nの具体的な値は分かりません。ここで、使用できるメモリがわずか4キロバイトしかないという制約のもと、配列内のすべての重複をどのように表示すればよいでしょうか?

例えば、入力が [2, 6, 2, 11, 13, 11] の場合、2と11がそれぞれ複数回出現しているため、出力は [2, 11] となります。

なぜビット配列なのか

通常、重複検出にはハッシュセットなどを使用しますが、32,000個の整数をそのまま格納すると必要なメモリが制限を超えてしまいます。そこで各数値を「1ビット」で管理するビット配列(ビットマップ)を用います。32,000ビット = 4,000バイト = 約4KB に収まるため、厳しいメモリ制約下でも問題を解決できます。

解決手順

この問題を解くために、以下の手順に従います。

• バイト配列型のデータ構造 bit_arr を作成します。このクラスは次のメソッドを持ちます。
• コンストラクタを定義し、引数として n を受け取ります。
• arr := サイズ (n ÷ 2^5) + 1 の配列を作成し、0で初期化します。
• 関数 get_val(pos) を定義します。
• index := pos ÷ 2^5
• bitNo := pos AND 31
• (arr[index] AND (2^bitNo)) が0でなければ true を返します。
• 関数 set_val(pos) を定義します。
• index := pos ÷ 2^5
• bitNo := pos AND 31
• arr[index] := arr[index] OR (2^bitNo)

続いて、メイン処理では以下を行います。

• arr := bit_arr(320000)
• i を 0 から配列サイズまでループします。
  • num := arr[i]
  • arr.get_val(num) が真であれば、num を表示します。
  • そうでなければ、arr.set_val(num) を呼び出してビットをセットします。

実装例

理解を深めるために、以下の実装を見てみましょう。

class bit_arr:
    def __init__(self, n):
        self.arr = [0] * ((n >> 5) + 1)
    def get_val(self, pos):
        self.index = pos >> 5
        self.bitNo = pos & 31
        return (self.arr[self.index] & (1 << self.bitNo)) != 0
    def set_val(self, pos):
        self.index = pos >> 5
        self.bitNo = pos & 31
        self.arr[self.index] |= (1 << self.bitNo)
def is_duplicate(arr):
    arr = bit_arr(320000)
    for i in range(len(arr)):
        num = arr[i]
        if arr.get_val(num):
            print(num, end = " ")
        else:
            arr.set_val(num)
arr = [2, 6, 2, 11, 13, 11]
is_duplicate(arr)

入力

[2, 6, 2, 11, 13, 11]

出力

2 11

ポイント解説

この実装では、シフト演算 >> 5 による32での除算、および & 31 による剰余計算を利用することで、高速にインデックスとビット位置を求めています。各数値の出現有無を1ビットで記録するため、時間計算量はO(n)、空間計算量も約n/8バイトと非常に効率的です。メモリが厳しく制限された組み込みシステムや面接試験などでよく問われるテクニックなので、ぜひ覚えておきましょう。