연결된 목록에서 임의의 요소 집합을 효율적으로 선택

StackOverflow https://stackoverflow.com/questions/54059

문제

길이가 다른 숫자로 구성된 연결 목록이 있다고 가정해 보겠습니다. N. N 매우 커서 정확한 값을 미리 알지 못합니다. N.

반환할 함수를 가장 효율적으로 작성하는 방법은 무엇입니까? k 완전히 난수 목록에서?

도움이 되었습니까?

해결책

다음과 같은 방법을 사용하여 이를 위한 매우 훌륭하고 효율적인 알고리즘이 있습니다. 저수지 샘플링.

당신에게 그것을 주는 것부터 시작하겠습니다. 역사:

크누스 이 알고리즘을 R이라고 부릅니다.1997년판 Seminumerical Algorithms(The Art of Computer 프로그래밍의 2권) 중 144페이지에 나와 있으며 이에 대한 일부 코드가 제공되어 있습니다.Knuth는 알고리즘을 Alan G의 것으로 간주합니다.뱃사공.오랜 검색에도 불구하고 나는 Waterman의 원본 문서를 찾을 수 없었습니다. 이것이 존재한다면 Knuth가 이 알고리즘의 소스로 인용되는 것을 가장 자주 볼 수 있는 이유일 것입니다.

맥레오드와 벨하우스, 1983 (1) Knuth보다 더 철저한 토론과 알고리즘이 작동한다는 (내가 알고 있는) 최초의 출판된 증거를 제공합니다.

비터 1985 (2)는 알고리즘 R을 검토한 다음 동일한 출력을 제공하지만 변형된 세 가지 추가 알고리즘을 제시합니다.들어오는 각 요소를 포함하거나 건너뛰도록 선택하는 대신 그의 알고리즘은 건너뛸 들어오는 요소의 수를 미리 결정합니다.그의 테스트(현재는 구식임)에서 이는 난수 생성 및 각 수신 숫자에 대한 비교를 방지함으로써 실행 시간을 극적으로 감소시켰습니다.

~ 안에 의사코드 알고리즘은 다음과 같습니다

Let R be the result array of size s
Let I be an input queue

> Fill the reservoir array
for j in the range [1,s]:
  R[j]=I.pop()

elements_seen=s
while I is not empty:
  elements_seen+=1
  j=random(1,elements_seen)       > This is inclusive
  if j<=s:
    R[j]=I.pop()
  else:
    I.pop()

입력 크기를 지정하지 않기 위해 특별히 코드를 작성했습니다.이것이 이 알고리즘의 멋진 속성 중 하나입니다.입력 크기를 미리 알 필요 없이 실행할 수 있습니다. 아직 당신이 만나는 각 요소가 다음과 같은 결과를 초래할 확률이 동일하다는 것을 보장합니다. R (즉, 편견이 없습니다).뿐만 아니라, R 알고리즘이 항상 고려한 요소의 공정하고 대표적인 샘플이 포함되어 있습니다.즉, 이것을 다음과 같이 사용할 수 있습니다. 온라인 알고리즘.

이것이 작동하는 이유는 무엇입니까?

McLeod와 Bellhouse(1983)는 조합 수학을 사용하여 증명을 제공합니다.예쁘기는 한데 여기서 재구성하기는 좀 어려울 것 같아요.따라서 나는 설명하기 더 쉬운 대체 증거를 생성했습니다.

우리는 유도에 의한 증명을 통해 진행합니다.

우리가 s 요소와 우리가 이미 본 n>s 강요.

우리의 현재 s 요소는 이미 각각 확률로 선택되었습니다. s/n.

알고리즘의 정의에 따라 요소를 선택합니다. n+1 확률적으로 s/(n+1).

이미 결과 세트의 일부인 각 요소에는 확률이 있습니다. 1/s 교체된다는 것.

의 요소가 나올 확률 n-본 결과 집합이 다음에서 대체됩니다. n+1-본 결과 집합은 따라서 (1/s)*s/(n+1)=1/(n+1).반대로, 요소가 대체되지 않을 확률은 다음과 같습니다. 1-1/(n+1)=n/(n+1).

그래서 n+1-본 결과 집합에는 요소가 포함되어 있습니다. n- 결과 세트를 보았지만 대체되지 않았습니다.---이 확률은 다음과 같습니다. (s/n)*n/(n+1)=s/(n+1)---또는 요소가 선택된 경우---확률로 s/(n+1).

알고리즘의 정의는 첫 번째 s 요소는 자동으로 첫 번째 요소로 포함됩니다. n=s 결과 집합의 구성원입니다.그러므로, n-seen 결과 집합에는 다음과 같은 각 요소가 포함됩니다. s/n (=1) 유도에 필요한 기본 사례를 제공하는 확률입니다.

참고자료

  1. 맥레오드, A.이안, 데이비드 R.벨하우스."간단한 랜덤 샘플을 그리기위한 편리한 알고리즘." 왕실 통계 학회지.시리즈 C(응용통계) 32.2(1983):182-184.(링크)

  2. 비터, 제프리 S."저수지를 사용한 무작위 샘플링." 수학 소프트웨어 (TOMS) 11.1 (1985)에 대한 ACM 트랜잭션 :37-57.(링크)

다른 팁

이것은 저수지 샘플링 문제.간단한 해결책은 목록의 각 요소에 표시된 대로 임의의 숫자를 할당한 다음 위쪽(또는 아래쪽) k개 요소를 임의의 숫자 순서대로 유지하는 것입니다.

내가 제안 할게:먼저 k개의 난수를 찾으세요.정렬하세요.그런 다음 연결된 목록과 난수를 모두 한 번 순회합니다.

어떻게든 연결된 목록의 길이를 모른다면(어떻게?) 첫 번째 k를 배열로 가져온 다음 노드 r에 대해 [0, r)에 난수를 생성할 수 있습니다. k보다 배열의 r번째 항목을 교체합니다.(편향이 없다고 완전히 확신하지는 않습니다 ...)

그 이외의:"내가 당신이라면, 나는 여기서부터 시작하지 않을 것입니다." 링크 된 목록이 문제에 적합합니까?좋은 오래된 평면 배열 목록과 같은 더 나은 데이터 구조가 없습니까?

목록의 길이를 모르는 경우 무작위 선택을 보장하기 위해 전체를 탐색해야 합니다.이 경우 내가 사용한 방법은 Tom Hawtin(54070).당신이 보관하는 목록을 순회하는 동안 k 해당 지점까지 무작위 선택을 구성하는 요소입니다.(처음에는 첫 번째 k 당신이 만나는 요소.) 그런 다음 확률로 k/i, 선택한 요소 중 임의의 요소를 i목록의 번째 요소(예:현재 당신이 있는 요소).

이것이 무작위 선택을 제공한다는 것을 보여주는 것은 쉽습니다.본 후 m 요소(m > k), 우리는 각각의 첫 번째 m 목록의 요소는 확률에 따라 무작위 선택의 일부입니다. k/m.이것이 처음에 유지되는 것은 사소한 것입니다.그런 다음 각 요소에 대해 m+1, 확률에 따라 선택 항목에 넣습니다(임의의 요소 대체). k/(m+1).이제 다른 모든 요소에도 확률이 있음을 보여야 합니다. k/(m+1) 선발된다는 것.우리는 확률이 k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (즉.요소가 목록에 있을 확률과 해당 요소가 아직 존재할 확률을 곱한 값입니다.미적분학을 사용하면 이것이 다음과 같다는 것을 직접적으로 보여줄 수 있습니다. k/(m+1).

글쎄, N을 계산하기 위해 목록에 대한 추가 전달을 수행하는 경우에도 최소한 런타임에 N이 무엇인지 알아야 합니다.이를 수행하는 가장 간단한 알고리즘은 N에서 임의의 숫자를 선택하고 해당 항목을 제거하는 것입니다(k번 반복).또는 반복 번호를 반환하는 것이 허용되는 경우 항목을 제거하지 마십시오.

N이 매우 크고 성능 요구 사항이 매우 엄격하지 않은 한 이 알고리즘은 다음과 같이 실행됩니다. O(N*k) 복잡성은 허용되어야 합니다.

편집하다:신경 쓰지 마세요. Tom Hawtin의 방법이 훨씬 더 좋습니다.먼저 난수를 선택한 다음 목록을 한 번 순회합니다.이론적 복잡성은 동일하지만 예상 런타임은 훨씬 더 좋습니다.

왜 당신은 다음과 같은 일을 할 수 없습니까?

List GetKRandomFromList(List input, int k)
  List ret = new List();
  for(i=0;i<k;i++)
    ret.Add(input[Math.Rand(0,input.Length)]);
  return ret;

그렇게 간단한 것을 의미하는 것은 아닌 것 같은데 더 구체적으로 말씀해 주실 수 있나요?

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top