[algorithm] 로드 된 주사위의 데이터 구조?
각 측면 k가 롤링 할 때 p k 가 올 확률이 n 인로드 된 다이를 가지고 있다고 가정 하십시오. 이 정보를 정적으로 (즉, 고정 된 확률 세트) 저장하는 알고리즘이 좋은지 궁금해서 임의의 주사위 굴림을 효율적으로 시뮬레이션 할 수 있습니다.
현재이 문제에 대한 O (lg n) 솔루션이 있습니다. 아이디어는 모든 k에 대한 첫 번째 k면의 누적 확률 테이블을 저장하고 [0, 1) 범위의 난수를 생성하고 테이블에서 이진 검색을 수행하여 누적되는 가장 큰 인덱스를 얻는 것입니다. 값이 선택한 값보다 크지 않습니다. 나는이 솔루션을 좋아하지만 런타임이 확률을 고려하지 않는 것이 이상해 보입니다. 특히 한쪽이 항상 나타나거나 값이 균일하게 분포되는 극한의 경우 순진 접근 방식을 사용하여 O (1)의 롤 결과를 생성 할 수 있지만 내 솔루션은 여전히 많은 단계를 거쳐야합니다.
누구든지 런타임에서 어떻게 “적응”적인 방식 으로이 문제를 해결하는 방법에 대한 제안이 있습니까?
편집 :이 질문에 대한 답변을 바탕으로, 나는 이 문제에 대한 많은 접근 방식 과 그들의 분석 을 설명하는 기사를 작성했습니다 . Vose의 앨리어스 방법 구현은 Θ (n) 전처리 시간과 다이 롤당 O (1) 시간을 제공하는 것처럼 보입니다. 희망적으로 이것은 답변에 포함 된 정보에 유용한 추가 기능입니다!
답변
일회성 O (n) 설정으로 고정 이산 확률 분포를 생성하기 위해 O (1) 방법을 제공하는 별칭 방법 을 찾고 있습니다 (상수 시간으로 길이 n 배열의 항목에 액세스 할 수 있다고 가정). . Luc Devroye 의 “비 균일 랜덤 변형 생성” 의 3 장 (PDF) 에 문서가 있습니다.
아이디어는 확률 배열 p k 를 가져 와서 3 개의 새로운 n- 요소 배열 q k , a k 및 b k를 생성하는 것 입니다. 각각의 q k 는 0과 1 사이의 확률이고, 각각의 a k 와 b k 는 1과 n 사이의 정수이다.
0과 1 사이의 두 개의 난수 r과 s를 생성하여 1과 n 사이의 난수를 생성합니다. i = floor (r * N) +1이라고합시다. Q 경우 내가 <다음 반환 s의 난 B, 그렇지 난을 . 앨리어스 방법의 작업은 q k , a k 및 b k 를 생성하는 방법을 알아내는 것 입니다.
답변
균형 이진 검색 트리 (또는 배열의 이진 검색)를 사용하여 O (log n) 복잡성을 얻습니다. 각 다이 결과에 대해 하나의 노드가 있고 키가 해당 결과를 트리거 할 간격이되도록합니다.
function get_result(node, seed):
if seed < node.interval.start:
return get_result(node.left_child, seed)
else if seed < node.interval.end:
// start <= seed < end
return node.result
else:
return get_result(node.right_child, seed)
이 솔루션의 장점은 구현하기가 매우 간단하지만 여전히 복잡성이 높다는 것입니다.
답변
나는 당신의 테이블을 세분화하려고 생각하고 있습니다.
각 다이 값에 대해 누적 된 테이블을 갖는 대신 길이 xN의 정수 배열을 만들 수 있습니다. 여기서 x는 확률의 정확도를 높이기 위해 이상적으로 높은 수입니다.
인덱스 (xN에 의해 정규화 됨)를 누적 값으로 사용하여이 배열을 채우고 배열의 각 ‘슬롯’에이 인덱스가 나타나면 주사위 롤을 저장하십시오.
어쩌면 예를 들어 더 쉽게 설명 할 수 있습니다.
주사위 3 개 사용 : P (1) = 0.2, P (2) = 0.5, P (3) = 0.3
배열을 만듭니다.이 경우 10과 같은 간단한 길이를 선택합니다 (즉, x = 3.33333).
arr[0] = 1,
arr[1] = 1,
arr[2] = 2,
arr[3] = 2,
arr[4] = 2,
arr[5] = 2,
arr[6] = 2,
arr[7] = 3,
arr[8] = 3,
arr[9] = 3
그런 다음 확률을 얻으려면 0에서 10 사이의 숫자를 랜덤 화하고 해당 인덱스에 간단히 액세스하십시오.
이 방법은 정확도를 떨어 뜨릴 수 있지만 x를 높이면 정확도가 충분합니다.
답변
사용자 정의 분포 ( 이산 분포 라고도 함)로 임의의 정수를 생성하는 방법에는 여러 가지가 있습니다 . 선택은 선택할 정수의 수, 분포의 모양, 시간에 따른 분포의 변화 여부 등 많은 것들에 달려 있습니다.
사용자 지정 가중치 함수와 정수를 선택하는 가장 간단한 방법 중 하나 f(x)는 IS 거부 샘플링 방법. 다음은 가능한 가장 높은 값이 있다고 가정 f입니다 max. 거부 샘플링의 시간 복잡도는 평균적으로 일정하지만 분포 형태에 따라 크게 다르며 영원히 실행되는 최악의 경우가 있습니다. k거부 샘플링을 사용하여 [1, ] 에서 정수를 선택하려면 :
i[1,k] 에서 균일 한 난수를 선택하십시오 .- 확률
f(i)/max로 반환i합니다. 그렇지 않으면 1 단계로 이동하십시오.
다른 알고리즘의 평균 샘플링 시간은 분포 (보통 상수 또는 로그)에 크게 의존하지 않지만 설정 단계에서 가중치를 미리 계산하여 데이터 구조에 저장해야하는 경우가 종종 있습니다. 그들 중 일부는 평균적으로 사용하는 임의의 비트 수 측면에서 경제적입니다. 이러한 알고리즘 중 다수는 2011 년 이후에 도입되었으며 다음을 포함합니다.
- Bringmann–Larsen 간결한 데이터 구조 ( “이산 분포에서 간결한 샘플링”, 2012),
- Yunpeng Tang의 다단계 검색 ( “이산 분포를 변경하기위한 무작위 샘플링 방법에 대한 실증적 연구”, 2019) 및
- 빠른로드 주사위 롤러 (2020).
다른 알고리즘으로는 별칭 방법 (기사에서 이미 언급), Knuth–Yao 알고리즘, MVN 데이터 구조 등이 있습니다. 설문 조사는 내 섹션 ” 가중 선택 알고리즘에 대한 참고 사항 “을 참조하십시오 .
