I have a problem which requires resetting all values in a column to 0 or 1. The code which i am using is normal naive approach to set values by iterating each time. Is there any faster implementation.
//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 can be 0 or 1
Well, other then iterating the columns there are few optimizations you might want to make:
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)
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.
The problem is taken from running codechef long contest.... hail cheaters .. close this thread
