[Algorithms] 2.4 Medians

저자 Dasgupta의 Algorithms을 해석하면서 정리한 글입니다.

2.4 Medians

중앙값(Median)은 리스트가 존재할 때 정중앙에 있는 값으로, 이 값을 기준으로 절반은 이 값보다 작고, 나머지 절반은 이 값보다 크게 분포되어 있습니다.

Ex 01)
list [45, 1, 10, 30, 25]가 있을 때, Median = 25
e.g. 숫자들을 오름차순으로 정렬하게 되면 [1, 10, 25, 30, 45]가 되어 홀수개의 원소는 중앙값이 정확하게 가운데 숫자기 때문에 25가 됩니다.

만약에 리스트의 길이가 짝수일 경우, 무엇이 중앙값이 될지 2가지 선택이 있습니다. Lower Mediand은 n/2에 위치해있고, Higher Median은 (n/2)+1에 위치해 있습니다. (흔히 둘 중에서 더 작은 것을 선택하곤 합니다)

중앙값을 찾는 목적은 하나의 전형적인 값으로 숫자들의 집합을 요약하기 위해서 입니다. 보통 리스트에서 어떠한 값을 찾을 때, 평균(Mean)이나 중앙값이 자주 사용이 되는데, 중앙값은 평균에 비해 데이터에 더 전형적입니다.
그 이유는 항상 주어진 데이터에서 하나의 값을 뽑아낼 수 있기 때문입니다.
n개의 데이터에서 중앙값을 계산하는 것은 매우 간단합니다. 하지만 쉬운만큼 수행 시간이 O(nlogn)으로 이상적이지는 못합니다. 대개 선형적인(linear) 시간을 선호하기에 이 수행 시간을 더 효율적으로 개선시킬 수 있으면 좋습니다.

저희는 앞으로 재귀적인 해를 찾을 때, 그 문제의 좀 더 일반적인 상황으로 문제를 해결해볼 것입니다. 그래서 굳이 중앙값이 아닌, 어떠한 리스트에서 어떠한 값을 찾아내는 상황을 생각해볼 것입니다.

선택(Selection)

Selection은 어떤 리스트 S와 정수 k가 주어졌을 때, S에서 k번째로 작은 원소를 찾아내는 과정입니다.

여기서 $v$값에 주목해야 합니다.($v$는 $k$를 찾기 위한 임의의 값) 리스트 S를 3개의 범주로 나누었을 때, $v$보다 작은 원소들($S_L$), $v$와 같은 원소들(중복 포함)($S_v$), 그리고 $v$보다 큰 원소들($S_R$)로 나눌 수 있습니다.

예를 들어 위의 그림에서 $v = 5$라고 했을 때, [2, 4, 1] / [5, 5] / [36, 21, 8, 13, 11, 20]으로 나눌 수가 있습니다.
이렇게 나누었을 때, 탐색 단계에서 3개의 부분 리스트들 중 하나로 좁혀나갈 수 있습니다. 만일 $S$의 8번째로 minimum element를 찾아야 한다면, 첫번째 리스트와 두번째 리스트의 원소 개수의 합은 5이기 때문에 자동적으로 마지막 리스트의 3번째 값이 됩니다.
즉, $selection(S, 8) = selection(S_R, 3)$이 되는 셈입니다. 좀 더 일반적으로 부분 리스트의 크기에 따라 $k$를 검사함으로써, 이 리스트들 중 어느 것이 원하는 원소를 지니고 있는지를 빠르게 결정이 가능합니다.

$v$ 결정하는 법

$v$를 고를 때 빠르게 선택하고 이것이 원하는 $k$에 근접하면 가장 좋습니다.
가장 이상적인 경우는 $v$를 선택했을 때, $S_L$과 $S_R$의 크기가 $S$의 절반이면 됩니다. 그러나 이는 $v$가 필히 중앙값이여야 한다는 전제가 깔려 있습니다.
당연히 알고리즘은 $v$를 어떻게 선택하느냐에 따라 수행 시간이 달라질 것입니다. 만약 가장 좋지 않은 경우로 가장 앞의 원소와 가장 뒤의 원소가 $v$로 선택이 되어질 경우, 기존의 알고리즘보다 수행 시간이 더 좋지 않아질 수 있습니다.

따라서 $v$를 임의로 선택해줍니다. 의문이 들수도 있겠지만, 실제로 $v$를 가운데 어느 지점에서 선택하게 되면, 좋지 않은 케이스가 나올 경우는 꽤 드뭅니다.

만약 100개의 원소 중 25th element를 택한다고 했을 때, 부분 리스트 중에서 길이가 가장 길어봐야 원래 리스트의 3/4 크기일 것입니다.(25%와 75% 사이에 $v$가 놓이면 lucky case로 봅니다) 임의로 선택된 $v$가 lucky case가 될 확률은 50%라는 것이 주어만 진다면, 수행 시간을 원하는대로 효율적으로 바꿀 수 있습니다.

Ex 02)
“평균적으로 평평한 동전은 앞면이 보이려면 두 번은 던져야 할 필요가 있다”를 증명할 것입니다.
동전이 앞면이 보이기 전에 던져지는 기대 횟수(Expected number)를 $E$라고 하면, 분명히 최소한 한 번의 던져짐은 필요하고, 그것이 앞면이 나왔다면, 원하는 결과를 얻은 것입니다.
만약 그것이 뒷면일 경우 다시 할 필요가 있습니다. 따라서 $E = 1 + (1 / 2)E$ 이고, $E$는 $2$로 해결됩니다.

그래서 우리는 평균적으로 2번의 분할하는 연산 후에 리스트는 길어봐야 원래 크기의 3 / 4 정도까지 줄어들 것입니다.
위 수행 시간은 $(3 / 4)n$ 크기의 리스트에 수행해야 하는 시간과 리스트를 $(3 / 4)n$ 이하로 줄이기 위한 시간이 최종 수행 시간이 되는 것이고, 합의 성질을 이용해서 최종적으로 $T(n) = O(n)$이라는 결론을 내릴 수 있습니다.

Implementation of the Median-finding Algorithm

def median_of_medians(A, i):

    #divide A into sublists of len 5
    sublists = [A[j:j+5] for j in range(0, len(A), 5)]
    medians = [sorted(sublist)[len(sublist)/2] for sublist in sublists]
    if len(medians) <= 5:
        pivot = sorted(medians)[len(medians)/2]
    else:
        #the pivot is the median of the medians
        pivot = median_of_medians(medians, len(medians)/2)

    #partitioning step
    low = [j for j in A if j < pivot]
    high = [j for j in A if j > pivot]

    k = len(low)
    if i < k:
        return median_of_medians(low,i)
    elif i > k:
        return median_of_medians(high,i-k-1)
    else: #pivot = k
        return pivot

#Here are some example lists you can use to see how the algorithm works
#A = [1,2,3,4,5,1000,8,9,99]
#B = [1,2,3,4,5,6]
#print median_of_medians(A, 0) #should be 1
#print median_of_medians(A,7) #should be 99
#print median_of_medians(B,4) #should be 5

Ex 03)
Say you wanted to use the above implementation to find the $i^\text{th}$ largest element in $A$ instead of the $i^\text{th}$smallest. What change could you make to the implementation (not to the function’s inputs) to achieve this?

low와 high을 swap 해줍니다.

high = [j for j in A if j < pivot]
low = [j for j in A if j > pivot]

수정 후 test 구현 결과,

B = [1,2,3,4,5,6]
print median_of_medians(B,0) 
#the first largest element should be 6
print median_of_medians(B,5) 
#the fifth largest element should be 1 (remember 0 indexing)

Ex 04)
What could you input to the original implementation above to find the largest element in a list?

D = [1,2,3,4,5,6] # 6 is the largest (least small) element in D
print median_of_medians(D, len(D)-1)

E = [9,5,4,3] #9 is the largest (least small) element in E
print  median_of_medians(E, len(E)-1)

Reference

Algorithms - Dasgupta
https://brilliant.org/wiki/median-finding-algorithm/