두 개의 32x64 2 차원 배열을 정확히 비교할 수있는 좋은 방법이 있습니까?

Question

저는 임베디드 장치에서 Conway의 Game of Life를 구현하려고합니다. 나는 단지 1kb의 RAM 만 가지고 놀았고 총 2048 개의 셀이 512 바이트와 같습니다. 저는 한 번에 차세대 8x8 셀을 계산할 것입니다. 그래서 한 지점에서 RAM에 2 세대를 저장할 필요가 없습니다.

그러나 내가하고 싶은 것은 GoL이 루프/정적 상태에있을 때 감지합니다. PC에서 실물 모형을 만들었을 때, 나는 단지 마지막 세대와 천대의 세대를 저장하고 현재 세대와 그것을 비교했습니다. 나는 1kb의 RAM으로 이것을 할 수 없다. 내가하고있는 일은 단순히 마지막 x 세대의 해시를 계산하고 그 해시를 현재 세대의 해시와 비교하는 것이다.

XTEA 또는 SHA1의 매우 가벼운 구현이 있지만 두 세대의 각 개별 셀이 동일한 지 확인해야하기 때문에 해싱이 실제로이 목적에 적합한 지 잘 모르겠습니다. 무엇을 추천하나요?

감사합니다,

조

편집 : 그냥 생각 나는 실제로 일치의 수를 계산하고 특정 임계 값에 도달하면 다음 루프에 있다고 가정 할 수, 그것은 매우를 작동하지 않을 것입니다 수천 세대마다 반복되는 패턴에도 좋습니다.

Answer 1

나는 더 많은 RAM을 가진 장치를 얻는 것을 결정했다. 그러나 내가 관찰 한 한가지는 패턴이 있다면 매 x 세대마다 같은 패턴이 매치 될 것이고, 단지 무작위 해시 충돌이라면 ' 티. 따라서 다음 세대가있는 경우 :

123* 
231 
312 
123* 
231 
312 
123* 

123 세대가 매 세대마다 일치합니다. 이것은 해시 충돌과 함께 발생하지 않습니다.

다른 답변은 정확하고 가치가 있지만 문제에 대한 해결책을 제공하는 유일한 답변입니다. 자신의 질문에 대답 할 때 어떤 예의가 있는지 모르겠다. 대답으로 표시해서는 안된다면 투표를하지 말고, 그냥 나에게 메시지를 보내면 정답을 다시 지정할 것이다.

감사합니다,

조

Answer 2

해싱은 상황이 이 아니고이 아닐 때 알려주는 것이 좋습니다. 해시가 동일하면 개별 비교를 수행하려면 여전히 (잘 이어야 함)이 필요합니다.

Answer 3

꽤 좋은 선택이라고 생각합니다. 해시 충돌 가능성이 매우 낮으므로 응용 프로그램에 적용 할 수 있습니다. 원자로가 아닙니다.