-1

列のすべての値を 0 または 1 にリセットする必要がある問題があります。私が使用しているコードは、毎回反復して値を設定する通常の素朴なアプローチです。より高速な実装はありますか。

//Size of board n*n
i=0;
cin>>x>>y;x--;
if(query=="SetRow")
{
  while(i!=N){ board[i][x]=y;i++;}
}
else
{
  while(i!=N){ board[i][x]=y;i++;}
}

y は 0 または 1 です

4

2 に答える 2

2

さて、列を反復する以外に、実行したい最適化がいくつかあります。

  1. 列の反復は、キャッシュのパフォーマンスのために、行の反復よりも効率が低くなります (約 *4 遅くなります) 。列の反復では、要素ごとにキャッシュ ミスがありますが、行の反復では、4 つのうち 1 つの要素でキャッシュ ミスがあります (通常、アーキテクチャとデータのサイズによって異なりますが、通常、キャッシュ ラインは 4 つの整数に適合します)。
    したがって、列を行よりも頻繁に反復する場合は、行をより頻繁に反復するために再設計します。このスレッドでは、同様の問題について説明しています。 また、それを行った後、このタスクにより最適化されていると思われるものを
    使用できます。(注: 場合によっては、コンパイラが自動的にそれを行うことがあります)memset()

  2. 遅延初期化を使用できます。実際にはO(1)、定数値で配列を初期化するアルゴリズムがあります。詳細については、ここで説明します: initalize an array in constant time。これには、スペースの量が最大 3 倍になり、後でより拡張的なシークが発生します。

その背後にある考え方 (2) は、追加のスタック (論理的には、配列 + トップへのポインターとして実装) と配列を維持することです。追加の配列は、最初に初期化されたとき (0 から n までの数値) を示し、スタックはどの要素を示すかを示します。既に変更されていました。

にアクセスするとarray[i]、stack[additionalArray[i]] == i && additionalArray[i] < top配列の値がarray[i]. それ以外の場合は、「初期化された」値です。

を実行するときarray[i] = xに、(前に見たように) まだ初期化されていない場合は、 を設定additionalArray[i] = stack[top]して増加させる必要がありますtop。

これによりO(1)初期化が行われますが、前述のように、追加のメモリが必要になり、各アクセスがより拡張されます。

配列の初期化に関する記事で説明されているのと同じ原則をO(1)ここでも適用できます。

于 2013-02-03T11:12:46.807 に答える
0

この問題は、codechef の長いコンテストを実行することから得られます....チーターを歓迎します..このスレッドを閉じます

于 2013-02-03T12:28:57.370 に答える