c# - C＃で可能な限り高速な大規模リストでのビット演算

Question

10,000個の長い値のリストがあり、そのデータを100,000個の他の長い値と比較したいのですが、ビット単位の演算です->

if (a&b==a) count++;

最高のパフォーマンスを得るために使用できるアルゴリズムはどれですか？

Answer 1

私があなたの質問を正しく理解していれば、いくつかの述語が真であるかどうかaをそれぞれに対して確認する必要があります。bしたがって、問題に対する単純な解決策は次のようになります。

var result = aList.Sum(a => bList.Count(b => (a & b) == a));

aeachに対して eachをチェックすることはできないため、これが任意の述語に対して実際に高速化できるかどうかはわかりませんb。試すことができるのは、クエリを並行して実行することです。

var result = aList.AsParallel().Sum(a => bList.Count(b => (a & b) == a));

例：

aList: 10,000 個のランダムlong値; bList: 100,000 個のランダムlong値。

• なしAsParallel: 00:00:13.3945187

• AsParallel: 00:00: 03.8190386

Answer 2

すべての をaトライ データ構造に入れます。ここで、ツリーの最初のレベルは数値の最初のビットに対応し、2 番目のレベルは 2 番目のビットに対応するというようになります。次に、それぞれについてb、トライを下ります。でこのビットが 1 の場合b、両方のブランチをカウントします。または、 でこのビットが 0 の場合b、トライの 0 ブランチのみをカウントします。これは O(n+m) であるべきだと思いますが、あまり難しく考えていません。

as のリストをソートし、ソートされたリストをトライとほぼ同じ方法で使用することにより、おそらく同じセマンティクスを取得できますが、より優れたキャッシュ特性が得られます。これは、多くの時間を検索する必要があるため、操作の数の点でわずかに悪化しますが、CPU キャッシュの尊重はそれを補う以上のものになる可能性があります.

注意: 私は big-O 記法について考えたよりも正確性について考えたことはありません。つまり、おそらく十分ではありません。