비트 맵핑 알고리즘

Question

데이터 세트는 2 차원 격자입니다. 실시간 소스에서 그리드를 업데이트하는 것은 매우 높은 빈도로 발생하지만이 데이터의 처리에는 오랜 시간이 걸립니다.

타이머는 더티라고 표시된 셀에 대해 고정 시간에 그리드를 샘플링하고 처리해야합니다.

처리를 시작하기위한 오버 헤드는 P() 함수를 호출하여 부트 스트랩에 매우 오랜 시간이 걸립니다. P는 수평 또는 수직으로 스캔 라인과 같은 1 차원 배열을 취할 수 있습니다.

질문은 P() 호출 횟수를 최소화하기 위해 2D 그리드의 임의 비트 세트를 스캔 라인으로 "청크"할 수있는 효율적인 알고리즘을 설계하는 방법입니까?

Answer 1

prefix sum 알고리즘의 변형을 살펴보면 병렬로 비트 맵을 빠르게 스캔하고 더티 블록을 격리 한 다음 해당 더티 블록에 대한 포인터를 새로운 어레이 또는 전달할 수있는 "스캔 라인"으로 패킹 할 수 있습니다 귀하의 P() 기능.

예를 들어 병렬 스레드를 사용하면 더티 블록의 값이 1이고 비 더티 블록의 값이 0 인 2D 배열에서 접두어 합계를 수행합니다. 프리픽스 합계를 완료하면 더티 블록은 모두 1....N에서부터 위로 계산됩니다. 이제 일련의 병렬 스레드를 사용하여 번호가 매겨진 더티 블록에 대한 포인터를 새로운 "스캔 라인"배열로 복사하거나 만듭니다. 접두사 합으로부터의 값은 스캔 라인 배열의 슬롯에 대한 기본 해시 값이됩니다. 블록은에서 참조해야합니다.