c++ - 在 c++ 中将行和/或列的所有值设置为 1 或 0

Question

我有一个问题，需要将列中的所有值重置为 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

Answer 1

Well, other then iterating the columns there are few optimizations you might want to make:

1. Iterating columns is less efficient then iterating rows (about *4 slower) due to cache performance. In columns iteration, you have a cache miss for each element - while in rows iteration you have cache miss for 1 out of 4 elements (usually, it depends on architecture and size of data, but usually a cache line fits 4 integers).
   Thus - if you iterate columns more often then rows- redesign it, in order to iterate rows more often. This thread discusses a similar issue.
   Also, after you do it - you can use memset() which I believe is better optimized for this task.
   (Note: Compilers might do that for you automatically in some cases)

2. You can use lazy initialization, there is actually O(1) algorithm to initialize an array with constant value, it is described with more details here: initalize an array in constant time. This comes at the cost of ~triple the amount of space, and more expansive seek later on.

The idea behind it (2) is to maintain additional stack (logically, implemented as array+ pointer to top) and array, the additional array will indicate when it was first initialized (a number from 0 to n) and the stack will indicate which elements were already modified.

When you access array[i], if stack[additionalArray[i]] == i && additionalArray[i] < top the value of the array is array[i]. Otherwise - it is the "initialized" value.

When doing array[i] = x, if it was not initialized yet (as seen before), you should set additionalArray[i] = stack[top] and increase top.

This results in O(1) initialization, but as said it requires additional memory and each access is more expansive.

The same principles described by the article regarding initializing an array in O(1) can also be applied here.

Answer 2

问题出在运行 codechef long 比赛.. 万岁骗子.. 关闭此线程