c# - 定数時間設定操作

Question

バイナリセットの共通部分と和集合の定数時間アルゴリズムはありますか？

メモリ内の要素へのポインタを持つビットマップを使用し、和集合にはORを使用し、共通部分にはANDを使用することを想像します。

誰かが今解決策を持っていますか？

Answer 1

BitArrayクラスでは最大32要素の定数時間です。基になるulong[]を使用して、最大64個の要素を取得するカスタム要素を作成できます。アンマネージコードにより、_mm_or_si128および_mm_and_si128組み込み関数で128個の要素が可能になります。メモリアライメント要件のために使用するのは難しく、ガベージコレクションされたヒープからそれを取得することはできません。

この種のコードを最適化したい場合、これらはほとんどの場合実用的な量ではありません。これは基本的に、 Ohが非常に小さいO（n）アルゴリズムです。BitArrayを使用することもできます。