タイトルはほとんどすべてを物語っていますが、これを例に挙げます: char の配列 a と、同じく char の配列 b があるとします。b の主要な位置にある文字のみを a に入れるより良い方法はありますか? 素数の位置を持つ配列があるとします。今のところ、私の単純なコードは次のようになります。
for(i = 0; i < n; i++)
a[i] = b[j + prime[i]];
ここで、prime[i] は b の素数の位置を格納し、b は a よりもはるかに大きく、j は b の任意の位置です (j+prime[i] は b の境界を超えないため、境界外の問題は発生しません)。 .
これをアルゴリズムの観点から見てみましょう。
配列 A の各エントリに対してハッシュ関数を実行したいと考えています。配列 A の項目の状態について何も知らないと仮定すると、アルゴリズムの実行時間の下限は線形 O(n) になります。時間。一部の要素を「スキップ」したり、プロセスを最適化するのに役立つ情報がこれ以上ないため、すべてのメンバーを反復処理する必要があります。
そうは言っても、課題はアルゴリズムを O(n) に抑えることになります。あなたが示すコードは、同じ方法で非素数をコピーすることでフォローアップすると仮定して、これを行います。したがって、コピーのステップについては、アルゴリズムの観点からこれを高速化する方法はありません。ただし、ハッシング ステップの実行方法が速度に影響しないというわけではありません。
何が良いですか？1 つの方法は次のとおりです。prime[] の場所がコンパイル時にわかっている場合は、事前にキャッシュ ラインを取得するためにプリフェッチを追加できます。
これにより、メモリアクセス時間が改善されています。