Алгоритм — установить все значения строки и / или столбца в c ++ равными 1 или 0

Question

Алгоритм — установить все значения строки и / или столбца в c ++ равными 1 или 0

У меня есть проблема, которая требует сброса всех значений в столбце в 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++;}
}

у может быть 0 или 1

-1

algorithm c++memset

Решение

Другие решения

Проблема берется из длинного конкурса Codechef …. Привет читеры .. закрыть эту тему

0

Источник

Accepted Answer

Ну, а затем итерируя столбцы, есть несколько оптимизаций, которые вы могли бы сделать:

Итерация столбцов менее эффективна, чем итерация строк (примерно на * 4 медленнее) из-за кэш спектакль. В итерации столбцов у вас есть пропуск кэша для каждого элемента — в то время как в итерации строк у вас есть пропуск кэша для 1 из 4 элементов (обычно это зависит от архитектуры и размера данных, но обычно строка кэша соответствует 4 целым числам).

Таким образом — если вы итерируете столбцы чаще, чем строки — измените его, чтобы итерировать строки чаще. Эта тема обсуждает похожую проблему.

Кроме того, после того, как вы это сделаете — вы можете использовать memset() который я считаю лучше оптимизирован для этой задачи.

(Примечание: в некоторых случаях компиляторы могут сделать это автоматически)
Вы можете использовать ленивую инициализацию, есть на самом деле O(1) алгоритм инициализации массива с постоянным значением, более подробно он описан здесь: инициализировать массив в постоянное время. Это происходит за счет удвоения объема пространства и более масштабного поиска в дальнейшем.

Идея этого (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) также может применяться здесь.

2