bitsetで集合演算をword並列化する

概要

bitsetによるword並列集合演算

真偽集合をbit列へ詰め、交差・和・shift・popcountをword単位で実行して遷移や組数計算を加速する。

考え方

真偽集合をwordへ詰め、AND・OR・shiftをw bitずつ処理する。集合演算、到達集合、部分和の遷移を多数のscalar更新からword単位へまとめる。

集合の要素iをword floor(i/w)のbit i mod wに置く。交差はAND、unionはOR、対称差はXOR、個数は各wordのpopcountの和。shift kではword移動q=floor(k/w)とbit移動r=k mod wへ分け、隣接二wordからrとw−r bitを合成する。r=0はword移動だけにしてword幅ちょうどのshiftを避け、最後のwordのM以降のpaddingを0へmaskする。

0/1部分和の到達集合ならbit0だけ1で始め、正の重さaを一個読むごとに bits←bits OR (oldBits<<a) とする。未選択と一回選択の二集合を合併する遷移である。in-placeでwordを処理する場合は高い方から更新して、同じ品物を二回使う伝播を防ぐ。bitset式の右辺が旧値から計算されることと、word実装の更新順を合わせる。

成立条件と計算量

M bitの一演算はO(⌈M/w⌉)。bitset操作をO(1)と数えない。shift後の範囲外bit、長さのpadding、in-place更新の意味を確認する。数え上げの多重度は真偽集合だけでは保存できない。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。真偽配列の演算をbit演算へ写し、word幅を含めた計算量を見積もる。

対象色の読み方は本書の読み方を参照してください。

概念上の親: データ構造と問い合わせ。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-bitset-word-parallel

習得する技能

  • 集合をbit列へ符号化し、交差・和・shift・popcountをword並列に実行した計算量を評価できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

集合の交差・和・shiftを機械語word単位で同時処理し、要素ごとの走査をword幅だけ短縮する。

このUnitでは扱わないもの

  • 集合状態そのものを一つずつ遷移するbitmask DP、および単一整数のbit演算だけで完結する処理。

根拠