非常に特定の条件で、並べ替えられていない 2 つの小さな配列を交差させるアルゴリズムを探しています。
ブルートフォース/ソートアンドインターセクトのソリューションはどちらもそれほど悪くはありませんが、十分に高速だとは思いません。より最適なソリューションはありますか?
配列はプリミティブ型であり、キャッシュ ラインに収まるほど短いため、迅速な実装では、大規模な複雑さではなく、比較の戦術的なメカニズムに焦点を当てます。たとえば、ハッシュ テーブルは一般にハッシュと間接化を伴い、常に多くの管理オーバーヘッドを伴います。
2 つの並べ替えられた配列がある場合、交差は O(n+m) です。sort-then-intersect は「ブルート フォース」だとおっしゃっていますが、これより速く実行することはできません。
もちろん、配列がソートされて格納されている場合は、交差点を頻繁に呼び出していると言うので、さらに利益が得られます。
交差自体はSSE で行うことができます。
考えられる最適化は次のとおりです。両方の配列の最大要素数が 32 以下 (または 64、あるいは 16) であるかどうかを確認します。一致する場合は、そのサイズの 2 つのビットマップ (タイプuint32_tなど) を塗りつぶし、バイナリ AND を使用して交差し&ます。そうでない場合は、ソートに頼ります。
または、並べ替えの代わりに、 O( m + n ) 構成と O(min( m , n )) 交差との線形時間交差を可能にする Briggs と Torczon による非常に効率的な整数セット表現を使用します。これは、ソートよりも優れた境界を持つハッシュ テーブルよりもはるかに高速です。
配列が非常に小さいため、これら 2 つの配列を並べ替えるには挿入並べ替えを使用するのが最も速い方法です。C++ STL は、16 項目より小さい配列にも挿入並べ替えを使用します。次に、これら 2 つの配列に対して反復子を使用して、配列を比較および交差させることができます。
より高速に実行される他のアルゴリズムが存在する可能性がありますが、これらのアルゴリズムのオーバーヘッドは、配列ごとに 3 ～ 4 個の項目に対して大きすぎる可能性があります。
両方のセットの交差を決定するには、すべての要素を少なくとも 1 回検査する必要があります。つまり、最適な解のクラスは O(n + m) を生成します。ここで、n は 1 つのセット内の要素の数、m は要素の数です。他の要素。
これは、ハッシュ テーブルを使用して実現できます。アイテムが整数型であることを考えると、高速なハッシュ関数を見つけることが期待できます。簡単なアルゴリズムは次のようになります。
これは、ハッシュとハッシュ ルックアップが O(1) であると仮定すると、O(n + m) になります。
セットが頻繁に空であることがわかっている場合、最初にセットの 1 つが空であるかどうかを確認することでこれを最適化できます。空である場合は、空のセットを返すだけです。もちろん、事前にカウントを知っていて、セットを反復せずに計算できると仮定しています。その場合は、常に最初に小さい方のセットを読み取ってハッシュし、ハッシュ テーブルのメモリ使用量が 2 つのうち小さい方になるようにすることで、さらに最適化できます。