Алгоритм битового сопоставления

Question

Набор данных представляет собой двумерную сетку. Обновление сетки из источника в реальном времени происходит на чрезвычайно высокой частоте, но обработка этих данных занимает много времени.

Таймер отображает сетку в фиксированные моменты времени для ячеек, помеченных грязными и нуждающихся в обработке.

Накладные расходы, чтобы начать обработку, назовем ее функцией P() занимает очень много времени для начальной загрузки. P может принимать одномерную матрицу, например, горизонтальную или вертикальную.

Вопрос заключается в том, как разработать эффективный алгоритм, который может «вырезать» произвольный набор грязных битов в 2D-сетке в строки сканирования, чтобы свести к минимуму количество срабатываний P()?

Answer 1

Вы можете изучить вариант алгоритма prefix sum для быстрого сканирования параллельного растрового изображения, выделения грязных блоков и указателей упаковки на эти грязные блоки в новый массив или «scanline», которые могут быть переданы ваша функция P().

Например, используя параллельные потоки, выполняйте префиксную сумму в 2D-массиве, где грязные блоки имеют значение 1, а не грязные блоки имеют значение 0. После того, как вы сделали префиксную сумму, все грязные блоки будут подсчитываться вверх от 1....N. Теперь, используя набор параллельных потоков, скопируйте или создайте указатели на пронумерованные грязные блоки в новый массив «scanline» ... значение из суммы префикса станет основным хэш-значением для слота в массиве scanline, который каждый грязный на блок должен ссылаться.