반복 가능한 난수에 대한 입문서

이 글에서는 게임의 레벨/월드 생성을 사용 사례로 예시하지만, 이 교훈은 절차적 텍스처, 모델, 음악 등 다른 많은 것에도 적용할 수 있습니다. 그러나 암호화와 같이 매우 엄격한 요구 사항이 있는 애플리케이션에는 적합하지 않습니다.

왜 같은 결과를 두 번 이상 반복하고 싶을까요?

• 같은 레벨/월드를 다시 방문할 수 있습니다. 예를 들어 특정 시드에서 특정 레벨/월드를 생성할 수 있습니다. 같은 시드를 다시 사용하면 같은 레벨/월드를 다시 얻게 됩니다. 예를 들어 Minecraft에서 이 작업을 수행할 수 있습니다.
• 즉석에서 생성되는 영구적인 월드. 플레이어가 이동하면서 즉석에서 생성되는 월드가 있는 경우, 플레이어가 처음과 이후에 해당 위치를 방문할 때마다 드림 로직에 따라 매번 달라지는 것이 아니라, Minecraft나 곧 출시될 게임 No Man's Sky 등에서처럼 위치가 동일하게 유지되기를 원할 수 있습니다.
• 모두에게 같은 세상. 게임 월드가 절차적으로 생성되지 않은 것처럼 모든 플레이어에게 동일하게 보이기를 원할 수도 있습니다. 예를 들어 노 맨스 스카이의 경우입니다. 이는 위에서 언급한 같은 레벨/월드를 다시 방문하는 기능과 본질적으로 동일하지만, 항상 같은 시드를 사용한다는 점이 다릅니다.

시드라는 단어를 몇 번 언급했습니다. 시드는 임의의 출력을 얻기 위해 입력으로 사용되는 숫자, 텍스트 문자열 또는 기타 데이터일 수 있습니다. 씨앗의 특징은 동일한 씨앗이 항상 동일한 결과물을 생성하지만 씨앗에 약간의 변화만 있어도 완전히 다른 결과물이 생성될 수 있다는 것입니다.

이 글에서는 난수 생성기와 난수 해시 함수라는 두 가지 난수 생성 방법과 그 중 하나를 사용하는 이유에 대해 살펴보겠습니다. 제가 알고 있는 내용은 어렵게 얻은 것이고 다른 곳에서 쉽게 구할 수 없는 것 같아서 글로 써서 공유하는 것이 순서라고 생각했습니다.

난수를 생성하는 가장 일반적인 방법은 난수 생성기(줄여서 RNG)를 사용하는 것입니다. 많은 프로그래밍 언어에는 RNG 클래스나 메서드가 포함되어 있으며, 이름에 '랜덤'이라는 단어가 포함되어 있으므로 난수를 시작하기 위한 가장 확실한 접근 방식입니다.

난수 생성기는 초기 시드를 기반으로 난수 시퀀스를 생성합니다. 객체 지향 언어에서 난수 생성기는 일반적으로 시드로 초기화되는 객체입니다. 그런 다음 해당 객체의 메서드를 반복적으로 호출하여 난수를 생성할 수 있습니다.

C# 코드는 다음과 같습니다:

알 수 없는 블록 유형 "codeBlock"인 경우 `serializers.types` 프롭에서 해당 블록에 대한 직렬화기를 지정하세요.

이 경우 0과 가능한 최대 정수 값(2147483647) 사이의 임의의 정수 값을 얻지만 이를 특정 범위의 임의의 정수 또는 0과 1 사이의 임의의 부동 소수점 수 또는 이와 유사한 값으로 변환하는 것은 간단합니다. 이 작업을 바로 수행할 수 있는 메서드가 제공되는 경우가 많습니다.

다음은 시드 0에서 C#의 Random 클래스가 생성한 첫 번째 65536개의 숫자가 포함된 이미지입니다. 각 난수는 0(검정)과 1(흰색) 사이의 밝기를 가진 픽셀로 표시됩니다.

여기서 중요한 점은 첫 번째와 두 번째 난수를 먼저 얻지 않고는 세 번째 난수를 얻을 수 없다는 것입니다. 이는 단순한 구현상의 문제가 아닙니다. RNG는 본질적으로 이전 난수를 계산의 일부로 사용하여 각 난수를 생성합니다. 따라서 무작위 시퀀스에 대해 이야기합니다.

즉, 여러 개의 난수가 차례로 필요한 경우에는 RNG가 좋지만 특정 난수(예: 시퀀스에서 26번째 난수)를 얻을 수 있어야 하는 경우에는 운이 좋지 않습니다. Next()를 26번 호출하고 마지막 숫자를 사용할 수도 있지만 이는 매우 나쁜 생각입니다.

모든 것을 한 번에 생성하는 경우 시퀀스에서 특정 난수가 필요하지 않거나 적어도 제가 생각할 수 있는 이유는 없습니다. 그러나 즉석에서 조금씩 생성하는 경우에는 그렇게 할 수 있습니다.

예를 들어 월드에 세 개의 섹션이 있다고 가정해 보겠습니다: 플레이어는 섹션 A에서 시작하므로 섹션 A는 100개의 난수를 사용하여 생성됩니다. 그런 다음 플레이어는 100개의 다른 숫자를 사용하여 생성되는 섹션 B로 이동합니다. 생성된 섹션 A는 메모리를 확보하기 위해 동시에 소멸됩니다. 플레이어는 100이지만 다른 숫자인 C 구역으로 이동하고 B 구역은 파괴됩니다.

그러나 이제 플레이어가 다시 섹션 B로 돌아가면 섹션이 동일하게 보이려면 처음과 동일한 100개의 난수로 생성되어야 합니다.

아니요! 이것은 RNG에 대한 매우 일반적인 오해입니다. 사실 동일한 시퀀스의 서로 다른 숫자는 서로에 대해 무작위이지만, 서로 다른 시퀀스의 동일한 인덱스 번호는 언뜻 보기에 무작위처럼 보일지라도 서로에 대해 무작위적이지 않습니다.

따라서 100개의 시퀀스가 있고 각각의 시퀀스에서 첫 번째 숫자를 가져온다면, 그 숫자는 서로에 대해 무작위적이지 않습니다. 각 시퀀스에서 10번째, 100번째, 1000번째 숫자를 가져온다면 더할 나위 없이 좋을 것입니다.

이쯤 되면 회의적인 분들도 계실 텐데요, 괜찮습니다. 이 스택 오버플로 질문에서 절차적 콘텐츠에 대한 RNG에 대해 더 신뢰할 수 있는 정보를 찾아볼 수도 있습니다. 하지만 좀 더 재미있고 유익한 정보를 위해 몇 가지 실험을 해보고 그 결과를 살펴봅시다.

참조를 위해 동일한 시퀀스에서 생성된 숫자를 살펴보고 시드 0에서 65535까지 생성된 65536개의 시퀀스 각각에서 첫 번째 숫자를 가져와서 생성된 숫자와 비교해 보겠습니다.

패턴이 다소 균일하게 분포되어 있긴 하지만 무작위적인 것은 아닙니다. 실제로 비교를 위해 순수 선형 함수의 출력을 보여드렸는데, 후속 시드에서 나온 숫자를 사용하는 것이 선형 함수를 사용하는 것보다 거의 낫지 않다는 것을 알 수 있습니다.

그래도 거의 무작위인가요? 이 정도면 충분할까요?

이 시점에서는 육안으로는 무작위성을 측정할 수 없으므로 더 나은 방법을 도입하는 것이 좋습니다. 왜 안 될까요? 출력물이 무작위로 보이는 것만으로도 충분하지 않나요?

네, 결국 우리의 목표는 단순히 모든 것이 충분히 무작위로 보이는 것입니다. 하지만 난수 출력은 사용 방법에 따라 매우 다르게 보일 수 있습니다. 생성 알고리즘은 무작위 값을 다양한 방식으로 변형하여 단순한 순서로 나열된 값만 검사할 때는 숨겨져 있던 명확한 패턴을 드러낼 수 있습니다.

무작위 출력을 검사하는 다른 방법은 난수 쌍에서 2D 좌표를 생성하고 해당 좌표를 이미지로 플로팅하는 것입니다. 같은 픽셀에 더 많은 좌표가 착지할수록 해당 픽셀은 더 밝아집니다.

동일한 시퀀스의 난수와 서로 다른 시드를 가진 개별 시퀀스에서 생성된 난수에 대한 좌표 플롯을 살펴봅시다. 그리고 선형 함수도 추가해 보겠습니다.

놀랍게도 서로 다른 씨앗의 난수로 좌표를 만들 때 좌표가 균일하게 분포하는 것이 아니라 모두 가는 선으로 그려져 있습니다. 이 역시 선형 함수의 경우와 마찬가지입니다.

지형에 나무를 심기 위해 임의의 숫자로 좌표를 생성했다고 상상해 보세요. 이제 모든 나무가 일직선으로 심어지고 나머지 지형은 비어 있습니다!

난수 생성기는 특정 순서로 숫자에 액세스할 필요가 없는 경우에만 유용하다는 결론을 내릴 수 있습니다. 그렇다면 무작위 해시 함수를 살펴볼 수 있습니다.

일반적으로 해시 함수는 임의의 크기의 데이터를 고정된 크기의 데이터에 매핑하는 데 사용할 수 있는 함수로, 입력 데이터의 약간의 차이로 인해 출력 데이터에 매우 큰 차이가 발생합니다.

절차적 생성의 일반적인 사용 사례는 하나 이상의 정수를 입력으로 제공하고 임의의 숫자를 출력으로 얻는 것입니다. 예를 들어, 한 번에 파트만 생성되는 대규모 월드의 경우 일반적으로 입력 벡터(예: 월드 내 위치)와 관련된 난수를 구해야 하며, 이 난수는 동일한 입력이 주어질 때 항상 동일해야 합니다. 난수 생성기(RNG)와 달리 순서가 정해져 있지 않으므로 원하는 순서대로 난수를 얻을 수 있습니다.

C# 코드는 다음과 같을 수 있습니다. 원하는 순서대로 숫자를 가져올 수 있다는 점에 유의하세요:

알 수 없는 블록 유형 "codeBlock"인 경우 `serializers.types` 프롭에서 해당 블록에 대한 직렬화기를 지정하세요.

해시 함수는 여러 개의 입력을 받을 수도 있으므로 주어진 2D 또는 3D 좌표에 대한 난수를 얻을 수 있습니다:

알 수 없는 블록 유형 "codeBlock"인 경우 `serializers.types` 프롭에서 해당 블록에 대한 직렬화기를 지정하세요.

절차적 생성은 해시 함수의 일반적인 사용법이 아니며, 모든 해시 함수가 절차적 생성에 적합한 것은 아니며, 충분히 무작위 분포가 아니거나 불필요하게 비쌀 수 있기 때문입니다.

해시 함수는 해시 테이블이나 사전과 같은 데이터 구조 구현의 일부로 사용됩니다. 이는 무작위성을 위한 것이 아니라 알고리즘을 효율적으로 수행하기 위한 것이기 때문에 빠르지만 충분히 무작위적이지 않은 경우가 많습니다. 이론적으로는 무작위성이 있어야 하지만 실제로는 무작위성 속성을 비교한 자료를 찾지 못했고, 제가 테스트해 본 결과 무작위성 속성이 상당히 나쁜 것으로 판명되었습니다(자세한 내용은 부록 C 참조).

해시 함수의 또 다른 용도는 암호화입니다. 암호화적으로 강력한 해시 함수에 대한 요구 사항이 단순히 무작위로 보이는 값보다 훨씬 높기 때문에 매우 무작위적인 경우가 많지만 속도도 느립니다.

절차적 생성을 위한 우리의 목표는 무작위로 보이지만 효율적인, 즉 필요 이상으로 느리지 않은 무작위 해시 함수를 사용하는 것입니다. 선택한 프로그래밍 언어에 적합한 기능이 내장되어 있지 않을 수 있으며 프로젝트에 포함할 기능을 찾아야 할 수도 있습니다.

인터넷의 다양한 추천과 정보를 바탕으로 몇 가지 다른 해시 함수를 테스트해 보았습니다. 여기서는 그 중 세 가지를 선택하여 비교해 보았습니다.

• PcgHash: 저는 이 해시 함수를 절차적 콘텐츠 생성에 관한 Google 그룹 포럼 의 토론에서 아담 스미스로부터 얻었습니다. 아담은 약간의 기술만 있으면 자신만의 랜덤 해시 함수를 만드는 것이 그리 어렵지 않다고 제안하며 자신의 PcgHash 코드 스니펫을 예시로 제공했습니다.
• MD5: 이것은 가장 잘 알려진 해시 함수 중 하나일 수 있습니다. 또한 암호화 강도가 높고 우리의 목적에 필요한 것보다 더 비쌉니다. 또한 일반적으로 32비트 정수를 반환값으로 사용하는 반면 MD5는 훨씬 더 큰 해시값을 반환하며, 대부분은 그냥 버리게 됩니다. 그럼에도 불구하고 비교를 위해 포함할 가치가 있습니다.
• xxHash: 이것은 매우 우수한 무작위 속성과 뛰어난 성능을 모두 갖춘 고성능의 최신 비암호화 해시 함수입니다.

노이즈 시퀀스 이미지와 좌표 플롯을 생성하는 것 외에도 ENT - 의사 난수 시퀀스 테스트 프로그램이라는 무작위성 테스트 세트를 사용하여 테스트했습니다. 이미지에 일부 ENT 통계와 제가 직접 고안한 통계인 '대각선 편차'를 포함했습니다. 후자는 좌표 플롯에서 픽셀의 대각선 합계를 보고 이 합계의 표준 편차를 측정합니다.

다음은 세 가지 해시 함수의 결과입니다:

PcgHash는 순차적인 임의 값의 노이즈 이미지에서는 매우 무작위로 보이지만, 좌표 플롯에서는 명확한 패턴을 보여주기 때문에 단순한 변환에 잘 견디지 못한다는 점에서 두드러집니다. 이로부터 결론을 내리자면, 무작위 해시 함수를 직접 굴리는 것은 어렵기 때문에 전문가에게 맡겨야 한다는 것입니다.

MD5와 xxHash는 매우 유사한 랜덤 속성을 가지고 있으며, 그 중 xxHash가 약 50배 더 빠릅니다.

xxHash는 RNG는 아니지만 모든 해시 함수가 그렇지는 않지만 시드 개념을 가지고 있다는 장점도 있습니다. 시드를 지정할 수 있으면 엔티티, 그리드 셀 등의 다양한 임의 속성에 대해 서로 다른 시드를 사용하고 해시 함수의 입력으로 엔티티 인덱스/셀 좌표를 그대로 사용할 수 있으므로 절차적 생성에 분명한 이점이 있습니다. 결정적으로, xxHash를 사용하면 서로 다르게 시드된 시퀀스의 숫자는 서로 무작위입니다(자세한 내용은 부록 2 참조).

해시 함수를 조사하면서 범용 해시 벤치마크에서 높은 성능을 보이는 해시 함수를 선택하는 것도 좋지만, 해시 함수를 그대로 사용하는 것보다 절차적 생성 요구에 맞게 최적화하는 것이 성능에 매우 중요하다는 것을 알게 되었습니다.

두 가지 중요한 최적화가 있습니다:

• 정수와 바이트 간의 변환을 피하세요. 대부분의 범용 해시 함수는 바이트 배열을 입력으로 받아 정수 또는 몇 바이트를 해시 값으로 반환합니다. 그러나 일부 고성능 제품은 내부적으로 정수로 작동하기 때문에 입력 바이트를 정수로 변환합니다. 절차적 생성은 정수 입력 값을 기반으로 해시를 얻는 것이 가장 일반적이므로 바이트 단위로 변환하는 것은 전혀 의미가 없습니다. 바이트 의존도를 낮추는 리팩터링을 통해 출력은 100% 동일하게 유지하면서 성능을 세 배로 높일 수 있습니다.
• 하나 또는 몇 개의 입력만 받는 노루프 메서드를 구현하세요. 대부분의 범용 해시 함수는 가변 길이의 입력 데이터를 배열 형태로 받습니다. 이는 절차적 생성에도 유용하지만, 가장 일반적인 용도는 아마도 1, 2 또는 3개의 입력 정수를 기반으로 해시를 얻는 것일 것입니다. 배열이 아닌 고정된 수의 정수를 취하는 최적화된 메서드를 만들면 해시 함수에 루프가 필요하지 않아 성능이 크게 향상될 수 있습니다(제 테스트에서는 약 4~5배). 저는 저수준 최적화에 대한 전문가는 아니지만, 극적인 차이는 for 루프에서 암시적 분기 또는 배열 할당이 필요하기 때문에 발생할 수 있습니다.

현재 해시 함수에 대해 제가 추천하는 것은 절차적 생성에 최적화된 xxHash 구현을 사용하는 것입니다. 그 이유에 대한 자세한 내용은 부록 C를 참조하세요.

비트버킷에서 C#으로 구현한 xxHash 및 기타 해시 함수를 구할 수 있습니다 . 이는 유니티 테크놀로지스가 아닌 제가 여가 시간에 개인적으로 관리하고 있습니다.

최적화 외에도 절차적 생성에서 일반적으로 필요한 출력을 지정된 범위의 정수 또는 지정된 범위의 부동 소수점 숫자로 가져오는 메서드도 추가했습니다.

참고: 이 글을 쓰는 시점에서는 xxHash와 MurmurHash3에 단일 정수 입력 최적화만 추가했습니다. 시간이 되면 2, 3정수 입력에 대해서도 최적화된 과부하를 추가할 예정입니다.

무작위 해시 함수와 난수 생성기를 결합할 수도 있습니다. 합리적인 접근 방식은 시드가 다른 난수 생성기를 사용하되, 시드를 직접 사용하지 않고 무작위 해시 함수를 통과시킨 난수 생성기를 사용하는 것입니다.

무한대에 가까운 거대한 미로 세계가 있다고 상상해 보세요. 세계에는 각 그리드 셀이 미로와 같은 대규모 그리드가 있습니다. 플레이어가 월드에서 이동하면 플레이어를 둘러싼 그리드 셀에 미로가 생성됩니다.

이 경우 각 미로가 방문할 때마다 항상 같은 방식으로 생성되기를 원할 것이므로 이에 필요한 난수는 이전에 생성된 숫자와 독립적으로 생성할 수 있어야 합니다.

하지만 미로는 항상 한 번에 하나의 전체 미로가 생성되므로 하나의 미로에 사용되는 개별 난수의 순서를 제어할 필요가 없습니다.

여기서 이상적인 접근 방식은 무작위 해시 함수를 사용하여 미로의 격자 셀 좌표를 기반으로 미로의 시드를 생성한 다음 이 시드를 난수 생성기 시퀀스의 난수 생성에 사용하는 것입니다.

C# 코드는 다음과 같습니다:

알 수 없는 블록 유형 "codeBlock"인 경우 `serializers.types` 프롭에서 해당 블록에 대한 직렬화기를 지정하세요.

난수를 쿼리하는 순서를 제어해야 하는 경우 절차적 생성에 최적화된 구현에서 적절한 난수 해시 함수(예: xxHash)를 사용하세요.

여러 개의 난수를 가져와야 하고 순서는 중요하지 않은 경우 가장 간단한 방법은 C#의 System.Random 클래스와 같은 난수 생성기를 사용하는 것입니다. 모든 숫자가 서로에 대해 무작위성을 갖도록 하려면 하나의 시퀀스(하나의 시드로 초기화)만 사용하거나 여러 개의 시드를 사용하는 경우 먼저 임의 해시 함수(예: xxHash)를 통과시켜야 합니다.

이 문서에서 언급된 난수 테스트 프레임워크의 소스 코드와 다양한 RNG 및 해시 함수는 BitBucket에서 사용할 수 있습니다. 이는 유니티 테크놀로지스가 아닌 제가 여가 시간에 개인적으로 관리하고 있습니다.

이 글은 원래 제가 여가 시간에 게임 개발과 연구에 전념하는 런티비 블로그에 게재된 글입니다.

특정 사물의 경우 연속적인 노이즈 값, 즉 서로 가까운 입력 값이 서로 가까운 출력 값을 생성하는 값을 쿼리할 수 있어야 할 것입니다. 일반적으로 지형이나 텍스처에 사용됩니다.

이러한 요구 사항은 이 문서에서 설명하는 요구 사항과는 완전히 다릅니다. 지속적인 소음은 펄린 노이즈 또는 그 이상의 심플렉스 노이즈를 살펴보세요.

그러나 이는 연속적인 소음에만 적합하다는 점에 유의하세요. 다른 난수와 무관한 난수를 얻기 위해 연속 노이즈 함수를 쿼리하는 것은 이러한 알고리즘이 최적화되어 있지 않기 때문에 결과가 좋지 않습니다. 예를 들어, 정수 위치에서 심플렉스 노이즈 함수를 쿼리하면 세 번째 입력마다 0을 반환하는 것을 발견했습니다!

또한 연속 노이즈 함수는 일반적으로 계산에 부동 소수점 숫자를 사용하므로 원점에서 멀어질수록 안정성과 정밀도가 떨어집니다.

지난 몇 년 동안 여러 가지 오해를 들었는데, 그 중 몇 가지를 더 설명해 보겠습니다.

아니요, 그런 것을 본 적이 없습니다. 이 글의 테스트 이미지를 보면 시드 값이 낮거나 높을 때의 결과에는 차이가 없습니다.

다시 테스트 이미지를 보면 무작위 값의 시퀀스가 시작(왼쪽 상단 모서리에서 한 줄씩 진행)부터 끝까지 동일한 패턴을 따르는 것을 볼 수 있습니다.

아래 이미지에서는 65535개의 시퀀스에서 0번째 숫자와 동일한 시퀀스에서 100번째 숫자를 테스트했습니다. 보시다시피, 무작위성의 (부족함) 품질에는 뚜렷한 차이가 없습니다.

조금 나아졌을 수도 있지만 충분하지는 않습니다. C#의 랜덤 클래스와 달리 Java의 랜덤 클래스는 제공된 시드를 그대로 사용하는 것이 아니라 시드를 저장하기 전에 비트를 약간 섞어서 저장합니다.

서로 다른 시퀀스의 결과 숫자는 조금 더 무작위로 보일 수 있으며 테스트 통계를 통해 직렬 상관관계가 훨씬 더 우수하다는 것을 알 수 있습니다. 그러나 좌표 플롯에서 좌표에 사용할 때 숫자가 여전히 한 줄로 축소되는 것을 알 수 있습니다.

즉, RNG가 시드에 고품질의 랜덤 해시 함수를 적용하지 못할 이유가 없다는 뜻입니다. 사실 그렇게 하는 것이 매우 좋은 생각인 것 같고 단점도 생각나지 않습니다. 제가 알고 있는 인기 있는 RNG 구현은 그렇게 하지 않으므로 앞서 설명한 대로 직접 구현해야 합니다.

본질적인 이유는 없지만, xxHash 및 MurmurHash3와 같은 해시 함수는 시드 값을 입력과 유사하게 처리하므로, 말하자면 시드에 고품질의 무작위 해시 함수를 적용하는 것과 같습니다. 이러한 방식으로 구현되었기 때문에 서로 다르게 시드된 임의의 해시 객체에서 N번째 숫자를 사용하는 것이 안전합니다.

이 글의 원래 버전에서는 PcgHash, MD5, MurmurHash3를 비교하고 MurmurHash3 사용을 권장했습니다.

머머해시3는 뛰어난 무작위성 속성과 매우 괜찮은 속도를 자랑합니다. 저자는 이러한 목적으로 널리 사용되는 프레임워크인 SMHasher라는 해시 함수 테스트 프레임워크와 병행하여 이를 구현했습니다.

이 스택 오버플로우 질문에는 더 많은 해시 함수를 비교하고 MurmurHash에 대해서도 똑같이 유리한 그림을 그리는 것 같은, 고유성과 속도에 좋은 해시 함수에 대한 좋은 정보도 있습니다.

기사를 게시한 후 Aras Pranckevičius로부터 xxHash에 대해 알아보라는 추천을 받았고, Nathan Reed로부터는 그가 여기에 쓴 왕 해시에 대해 알아보라는 추천을 받았습니다.

xxHash는 SMHasher 테스트 프레임워크에서 높은 품질 점수를 받으면서도 훨씬 더 나은 성능을 보여줌으로써 자체 영역에서 MurmurHash를 능가하는 해시 함수입니다. xxHash에 대한 자세한 내용은 Google 코드 페이지에서 확인하세요.

제가 처음 구현했을 때, 바이트 변환을 제거한 후에는 MurmurHash3보다 더 빨랐지만 SMHasher 결과에 표시된 것만큼 빠르지는 않았습니다.

왕해시도 구현했습니다. 좌표 플롯에서 명확한 패턴을 보여주기 때문에 품질은 충분하지 않았지만, xxHash보다 5배 이상 빨랐습니다. 저는 그 결과가 자체적으로 공급되는 '왕더블해시'를 구현해 보았는데, 테스트 결과 품질이 좋으면서도 xxHash보다 3배 이상 빨랐습니다.

하지만 왕해시(및 왕더블해시)는 단일 정수만 입력으로 받기 때문에, 성능에 어떤 영향을 미치는지 알아보기 위해 단일 입력 버전인 xxHash와 MurmurHash3도 구현하기로 했습니다. 그리고 성능이 크게 향상(약 4~5배 빨라짐)된 것으로 나타났습니다. 실제로 xxHash가 왕더블해시보다 훨씬 빨라졌습니다.

품질과 관련해서는, 제 자체 테스트 프레임워크에서 상당히 명백한 결함이 발견되었지만 SMHasher 테스트 프레임워크만큼 정교하지는 않으므로, 여기서 높은 점수를 받은 해시 함수는 제 자체 테스트에서 괜찮아 보이는 것보다 무작위성 속성에 대한 품질이 더 좋다고 가정할 수 있습니다. 일반적으로는 테스트 프레임워크에서 테스트를 통과하는 것만으로도 절차적 생성 목적으로 충분할 수 있지만, (최적화된 버전의) xxHash는 어쨌든 자체 테스트를 통과하는 가장 빠른 해시 함수이므로 이를 사용하는 것은 당연한 일입니다.

시중에는 매우 다양한 해시 함수가 있으며, 비교를 위해 더 많은 해시 함수를 포함할 수 있습니다. 하지만 저는 주로 무작위성 품질과 성능 측면에서 널리 알려진 최고 성능의 몇 가지에 집중한 다음 절차적 생성을 위해 추가로 최적화했습니다.

이 버전의 xxHash로 생성된 결과는 최적에 상당히 근접해 있으며, 더 나은 것을 찾아서 사용함으로써 얻을 수 있는 추가 이득은 크지 않을 것으로 생각됩니다. 즉, 더 많은 구현을 통해 테스트 프레임워크를 자유롭게 확장할 수 있습니다.