해시라이프

Hashlife
6,366,548,773,463,667,669,985,195,496,000 (6조 1천억원) 세대는 골리의 해시라이프를 사용하는 인텔 코어 듀오 2GHz CPU에서 30초 이내에 계산했다.패턴에서 반복 주기를 탐지하고 요청된 세대로 건너뛰어 계산한다.

해시라이프는 콘웨이 게임 오브 라이프 및 관련 셀룰러 오토마타에서 주어진 출발 구성의 장기적인 운명을 계산하기 위한 메모화된 알고리즘으로, 자동화의 각 셀의 각 시간 단계를 시뮬레이션하는 대체 알고리즘을 사용하여 가능한 것보다 훨씬 더 빠르게 계산한다.이 알고리즘은 1980년대 초 빌 고스퍼가 제록스 팔로 알토 연구센터에서 연구를 하던 중 처음 기술한 것이다.해시라이프는 원래 향미 확장자의 도움을 받아 심볼릭 리스프 기계에서 구현되었다.

해시라이프

해시라이프는 대부분의 라이프 규칙에서 대량의 공간적, 시간적 중복성을 이용하도록 설계되었다.예를 들어, 콘웨이 라이프에서, 겉보기에는 무작위로 보이는 많은 패턴들이 단순한 정물화와 진동자의 집합으로 끝난다.

표현

그 분야는 전형적으로 이론적으로 무한 격자로 취급되는데, 문제의 패턴은 원점 부근을 중심으로 한다.4중 트리는 그 들판을 나타내기 위해 사용된다.해시 테이블은 나무의 k번째 레벨에서 한쪽에2k 2개씩k 2개씩 정사각형 모양의 셀을 저장한 후, 향후k−2 2세대에k−1k−1 걸쳐 중앙에 2개씩 저장한다.예를 들어, 4×4 사각형의 경우 1세대를 전진하는 2×2 센터를 저장하고, 8×8 사각형의 경우 2세대를 전진하는 4×4 센터를 저장한다.

해싱

쿼드 트리는 일반적으로 다른 간단한 표현(예: 비트 행렬 사용)보다 훨씬 더 많은 오버헤드를 가지고 있지만, 다양한 최적화를 허용한다.이름에서 알 수 있듯이 알고리즘은 해시 테이블을 사용하여 쿼드트리 노드를 저장한다.나무의 많은 하위 패턴들은 보통 서로 동일하다; 예를 들어 연구되고 있는 패턴은 같은 우주선의 많은 복사본들, 또는 심지어 빈 공간의 큰 얼룩들을 포함할지도 모른다.이러한 서브패턴은 모두 해시 테이블의 동일한 위치에 해시되므로 동일한 해시 테이블 항목을 사용하여 동일한 서브패턴의 많은 복사본을 저장할 수 있다.또한 이러한 하위 패턴은 다른 Life 알고리즘처럼 사본당 한 번이 아니라 한 번만 평가하면 된다.

이것은 그 자체로 자원 요구사항의 상당한 개선을 이끌어낸다. 예를 들어 다항식 속도로 성장하는 다양한 브리더와 스페이스필러의 세대는 로그 공간과 시간을 이용하여 해시라이프에서 평가될 수 있다.

초고속 및 캐싱

여러 패턴에 대한 추가 속도 향상은 서로 다른 속도로 다른 노드를 진화시킴으로써 달성할 수 있다.예를 들어, k번째 수준과 비교하여 (k+1)-th 수준에서 한 노드의 전진 세대 수를 (k+1)-th 수준에서 두 배로 계산할 수 있다.고전적인 글라이더 건과 같이 희박하거나 반복적인 패턴의 경우, 이것은 엄청난 속도 상승을 야기할 수 있고, 더 높은 세대에서 더 큰 패턴을 더 빠르고 때로는 기하급수적으로 계산할 수 있다.이 기능을 최대한 활용하려면 과거 세대의 서브패턴도 살려야 한다.

다른 패턴이 다른 속도로 실행되도록 허용되기 때문에, 일부 구현은, 고스퍼의 자체와 같다.hlife프로그램, 대화형 디스플레이는 없지만, 단순히 시작 패턴에 대한 사전 설정된 결과를 계산하는 것, 일반적으로 명령행에서 실행된다.그러나 골리와 같은 최근의 프로그램들은 해시라이프 기반 엔진을 구동시킬 수 있는 그래픽 인터페이스를 가지고 있다.

해시라이프 프로그램이 트리를 만드는 데 도움이 되는 패턴에 대해 해시라이프 프로그램의 일반적인 동작은 다음과 같다: 첫째 알고리즘은 해시 및 트리 구축과 관련된 일정한 오버헤드 때문에 다른 알고리즘에 비해 느리게 실행되지만, 나중에 충분한 데이터가 수집되고 속도가 엄청나게 증가할 것이다 – 빠른 속도가 종종 설명된다.d는 "d"로 한다.

단점

해시라이프는 많은 메모화된 코드와 마찬가지로 특히 엔트로피가 많은 중간 크기의 패턴에 비해 다른 알고리즘보다 훨씬 많은 메모리를 소비할 수 있으며, 쿼드트리 노드의 경계(즉, 2개의 크기)에 제대로 정렬되지 않은 서브패턴을 포함하고 있다. 캐시는 취약한 구성요소다.또한 이러한 패턴에 대한 다른 알고리즘보다 더 많은 시간을 소비할 수 있다.골리는 다른 라이프 시뮬레이터 중에서도 해시라이프와 기존 알고리즘 사이에서 전환 옵션을 가지고 있다.

해시라이프 또한 구현하기 훨씬 더 복잡하다.예를 들어 캐시에서 사용하지 않는 노드를 제거하기 위한 전용 가비지 수집기가 필요하다.

일반적으로 예측 가능한 패턴을 처리하도록 설계되었기 때문에, 혼란스럽고 폭발적인 규칙은 일반적으로 다른 구현에서보다 해시라이프에서 훨씬 더 형편없이 작동한다.[1]

참고 항목

  • 순기능 데이터 구조, 해시드 쿼드리가 하나임
  • 해시라이프의 원래 구현에 사용된 핵심 전략이었던 해시 컨센싱.

참조

  1. ^ 골리의 HashLife 알고리즘 설명: "HashLife는 매우 혼란스러운 패턴에서 매우 낮은 성능을 발휘하므로, 그러한 경우에는 QuickLife로 전환하는 것이 더 낫다."
  • Gosper, Bill (1984). "Exploiting Regularities in Large Cellular Spaces". Physica D. Elsevier. 10 (1–2): 75–80. doi:10.1016/0167-2789(84)90251-3.

외부 링크