У меня есть проблема, которая требует сброса всех значений в столбце в 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
Ну, а затем итерируя столбцы, есть несколько оптимизаций, которые вы могли бы сделать:
Итерация столбцов менее эффективна, чем итерация строк (примерно на * 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)
также может применяться здесь.
Проблема берется из длинного конкурса Codechef …. Привет читеры .. закрыть эту тему