Reservoir Sampling? 날 괴롭히지마 [leetcode]

웃겨서 넣기

 

n개중에 랜덤 한 k를 뽑는다고 할 때 Array list에서는 random.randInt(0, n) 식으로

랜덤 한 index를 추출, 해당 index를 접근해 값을 반환하는 식으로 구현할 수 있다.

이때 확률은 k/n 을 만족한다.

 

문제의 조건을 조금 바꿔서

linked list에서 특정 노드의 value를 랜덤 하게 k개를 선택하려고 할 때

해당 랜덤 선택 확률이 k/n (n = length of linked list)를 만족하려면?

 

단순하게 생각하기

linked list를 순회하면서 노드들의 value를 따로 저장해 둔다. (Linked list → Array list)

동일하게 Array의 length로 random.randInt(0, n) 식으로 index를 추출한다.

해당 index를 접근해 값을 반환하는 식으로 구현

이때 문제가 생긴다.

 

만약 linked list 전부를 메모리에 다 담을 수 없이 엄청 길다면?

이번에 얘기하려는 random sampling 방법인 reservoir sampling을 사용하면 된다.

• reservoir는 저장소라는 뜻이 있답니다.

현재 요소는 i번째, 길이는 알 수 없기에 n, 뽑아야 하는 랜덤 요소의 개수가 k라고 할 때

• 현재 요소 i
• linked list의 현재까지 이동한 거리(길이?) n
• 뽑아야 하는 요소의 개수 k

i 번째 요소가 linked list를 끝까지 순회했을 때까지 선택될 확률은?

1. n ≤ k 일 때는
   1. i번째 요소는 무조건 k에 포함이 된다.
2. n > k 일 때
   1. i 번째 요소가 k에 포함될 경우의 수는 (k / n) (우리는 P(a)라고 부르자.)
   2. i+1 번째 요소가 k에 포함될 경우의 수는 ( k / n+1 ) * ( 1 / k ) ( P(b)라고 하자.)
   3. i 번째가 마지막 선택까지 k개에 포함될 경우의 수는 (독립이므로)
   4. k / n+1의 확률을 만족해야 한다!

   P(a) * (1 - P(b)) 
   = (k/n) * (1 - P(b))
   = (k/n) (1 - ((k / n+1) * (1 / k)) )
   = (k/n) (1 - (1/n+1)) = (k/n) * (n / n+1)
   = (k / n+1)
   -> n+1 일때도 역시 k/n+1의 확률을 만족!!
   

직관적으로 안 와닿으니 실제 값을 넣어서

뽑아야 하는 랜덤 요소의 개수 (= K)가 1개라고 생각해 보자.

K = 1일 때

• i = 1 일 때 (n=1) 뽑을 확률은? (1/n = 1/1 = 1) 무조건 선택!
• i = 2 일때 (n=2) 뽑을 확률은 (1/n = 1/2)

random.randInt(1,2) == 1
# 1,2 중 랜덤으로 1이 선택될 확률은 1/2 이므로 k/n 을 만족

• i = 3 일때 (n=3) 뽑을 확률은 (1/n = 1/3)

random.randInt(1, 3) == 1
#1,2,3 중 랜덤으로 1이 선택될 확률은 1/3 이므로 k/n 을 만족

일반화해보자면

random.randInt(1, n) == 1 이 만족하면 해당 요소를 선택! 아니면 pass

이제 해당 reservoir sampling을 사용해야 하는 알고리즘 문제를 살펴보자.

LeetCode - The World's Leading Online Programming Learning Platform

Linked List Random Node - LeetCode

코드로 구현해 보자면

각 요소를 순회하면서 n이 증가할 때 고정된 숫자가 등장하면

random.randInt(1, n) == 1

해당 요소를 반환하면 된다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        ans = 0
        p, i = self.head, 0
        while p:
            if random.randint(0, i) == 0:
                ans = p.val
            p = p.next
            i += 1
        return ans

확률… 언제나 어렵고, 직관적으로 이해가 잘 안 된다.

그래서 그런지 이번 알고리즘 문제 풀이를 보는데 더더욱 힘들었던 거 같다.

 

참고

• 해당 알고리즘 문제) https://leetcode.com/problems/linked-list-random-node/description/
• 잘 정리된 블로그) https://trancekim.tistory.com/3
• 갓 위키피디아) https://en.wikipedia.org/wiki/Reservoir_sampling
• 알고리즘 문제 해설) https://leetcode.com/problems/linked-list-random-node/editorial/