アルゴリズム・データ構造図鑑 · 基礎から応用へ

ビット位置で集合をまとめて扱う

集合演算をビットへ対応させ、補集合の幅、末尾の未使用ビット、密な集合と疎なIDの容量を比較します。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 集合の所属をビットへ対応させる
  2. 和・積・差を一桁ずつ確かめる
  3. 余った末尾ビットを見落とさない
  4. 小さな宇宙を全て検査する
  5. 語数と宇宙の大きさで費用を数える
  6. 容量と変換の費用を比較する
  7. 別の幅を受け取ったときの契約
  8. 補集合の範囲を決める課題
  9. この記事をロゲイアに質問する理解を確かめる

集合の所属をビットへ対応させる

要素の宇宙を0以上10未満の整数へ固定し、要素iが属するなら整数のi番目のビットを1にします。集合A={0,3,9}なら、三つの位置だけが立ちます。名前が似ていても、任意の整数キーを圧縮なしに効率よく保存できるとは限りません。要素数が三個でも、最大のIDが十億なら、直接対応するビット列には十億に近い位置まで領域が必要です。要素数と宇宙の大きさを別に考えます。

ビット集合は、集合の積や和を複数要素まとめて計算できる点が特徴です。ただし、意味のあるビット位置を呼出し側と揃える必要があります。商品IDを途中で振り直した場合、同じビット列が別の商品を表すかもしれません。今回の入力は固定した小さな整数IDで、範囲外をエラーにします。外部IDの辞書から位置へ変換する場合、その対応表と版も集合の意味の一部です。

和・積・差を一桁ずつ確かめる

B={3,4}とすると、A OR Bは{0,3,4,9}、A AND Bは{3}です。差A−Bは、Aに属しBには属さない位置なのでA AND NOT Bで求めます。ただしNOTを取る範囲を固定する必要があります。Pythonの整数で単に~Bを使うと負の値となり、十個だけの反転した集合という意味にはなりません。下位10ビットのmask=(1<<10)−1を使い、~B AND maskへ制限します。

左右差の順序も重要です。A−BとB−Aは一般に同じではありません。所属を全部反転する補集合なら、同じ宇宙に対するmaskとAの排他的論理和でも表せます。数式だけを覚えるのでなく、ある位置についてAにあるか、Bにあるかの四通りを表へ並べ、その結果を確かめてください。集合演算の真理値表とビット演算の真理値表が同じことを利用しています。

Aに所属Bに所属A−Bに所属
いいえいいえいいえ
いいえはいいいえ
はいいいえはい
はいはいいいえ

余った末尾ビットを見落とさない

64ビットの語で10要素の宇宙を表すなら、上位54ビットは要素に対応しません。反転後にその領域を1のまま残してpopcountすると、存在しない要素まで数えてしまいます。宇宙の大きさが64の倍数でない複数語の実装でも、最後の語へ同じ注意が必要です。今回はPython整数へmaskをかけることで、同じ境界条件を小さく示します。

単一語のシフトでは、型の幅以上だけ動かした場合の言語仕様も確認します。C/C++の固定幅整数とPythonの大きな整数は、シフトや補数の扱いが同じとは限りません。抽象的な集合の定義と、選んだ整数型の規則を二段階で検討してください。範囲の検査を外して高速化する場合も、どこで入力を保証するかを決め、検査なしの不正な位置を正常な所属として受け入れないようにします。

小さな宇宙を全て検査する

掲載コードではAとBの全ての6ビットの組、64×64=4,096通りを作り、集合へ戻したPythonのsetと積・差を比べます。10ビットの補集合は要素数が7であることも検査します。Aの要素が三つなら、同じ十要素の宇宙での残りは七つです。ビットの順序を画面へ文字で出す場合、左からの桁順とi番目の位置が逆向きに見えることがあるため、数値の添字で照合してください。

bitsは要素を順に取り、対応するビットをORで立てます。同じ要素を二回渡しても集合の所属は変わりません。要素10を幅10へ入れる要求はValueErrorです。今回のwidthは正の固定値で使います。一般のライブラリへ切り出すなら、幅自体の型や負値、巨大な確保要求に対する契約も加えます。短い例が受け入れていない用途まで、検証済みとは広げないようにします。

python
def bits(values,width):
    result=0
    for value in values:
        if not 0<=value<width:raise ValueError('outside universe')
        result|=1<<value
    return result
width=10;mask=(1<<width)-1
A=bits([0,3,9],width);B=bits([3,4],width)
assert A&B==bits([3],width)
assert A|B==bits([0,3,4,9],width)
assert A&(~B&mask)==bits([0,9],width)
assert (~A&mask).bit_count()==7
for a in range(1<<6):
    for b in range(1<<6):
        x={i for i in range(6) if a>>i&1};y={i for i in range(6) if b>>i&1}
        assert a&b==bits(x&y,6)
        assert a&(~b&63)==bits(x-y,6)
try:bits([10],10)
except ValueError:pass
else:raise AssertionError('range check missing')
print('4096 pairs checked; complement masked to width')

語数と宇宙の大きさで費用を数える

宇宙の大きさをU、機械語のビット数をwとすると、固定語配列で集合全体の演算を行う費用は通常O(ceil(U/w))です。Uが一語に収まる条件なら定数回の演算になりますが、任意の大きさの集合の積を常にO(1)とは書けません。PythonのintのANDも、必要な内部の桁へ処理が及ぶため、大きさに無関係な単一命令という意味ではありません。

列挙では立っているビットを順に探し、必要な要素を出力します。全ての位置を確認する単純な実装と、下位の立ったビットを取り除く実装では、費用の数え方が異なります。固定幅のビット操作の回数と、出力する要素数を分けて説明してください。大量の集合の積を繰り返す検索では有利でも、宇宙が極端に疎なら、整列リストやハッシュ集合の方が保存量を抑えられる場合があります。

容量と変換の費用を比較する

たとえば宇宙が1,000なら、ビットだけの論理量は125バイトです。所属する要素が900個なら、一要素ずつ整数を保存する方式より小さくできる候補です。一方、宇宙が十億で所属が二個なら、直接ビット列の論理量は約125メガバイトになり、二つのIDを保存する費用とは大きく異なります。実オブジェクトのヘッダーや確保単位は、この論理量へ別に加わります。

IDを0から連続する番号へ圧縮すると小さくできますが、変換表を作る時間と保存量を無視できません。新しいIDを途中へ追加する場合や、別プロセスへ集合を送る場合にも、同じ番号対応が必要です。操作時間を測るなら、変換済み集合のANDだけなのか、入力IDから変換し結果をIDへ戻す全体なのかを記録します。速い論理演算と、アプリ全体の速さを混同しないためです。

別の幅を受け取ったときの契約

二つのビット集合を受け取るAPIでは、幅やIDの対応表が同じかを確認します。片方が幅8、他方が幅10の場合、積の整数演算自体はできても、補集合や列挙の意味をどう扱うかが曖昧になります。幅を広い方へ拡張する、違いをエラーとするなど、採用する規則を明示します。

送受信する形式ではビットの並び、語のバイト順、末尾の未使用位置も仕様です。同じ整数を表示したという一回の検査だけで、別言語との互換性を確認したとは言えません。0番と最終の有効位置、語境界の前後を使う小さな往復検査を用意すると、位置のずれを見つけやすくなります。

補集合の範囲を決める課題

課題は宇宙0〜7、A={1,6}、B={0,1,7}について、積、A−B、Aの補集合を求めることです。解答は{1}、{6}、{0,2,3,4,5,7}です。補集合を計算するmaskは255で、Aの外側の無限のビットではありません。B−Aなら{0,7}になり、差の順序が変わると結果も変わることを確認します。正しい要素数だけでなく、各位置の所属も照合してください。

追加課題では、宇宙の上限を8から10へ変えます。AとBの積や差は変わりませんが、Aの補集合へ8と9が追加されます。所属する要素が同じでも補集合は宇宙の定義へ依存するからです。保存するビット列だけでなく幅も一緒に扱う理由を説明してください。問題の要素数、表す宇宙、語数、実メモリ量を区別できれば、容量の実験へつなげられます。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 9

学習コースから次を選ぶ