내가 좋아하는 알고리듬: 선형 시간 중앙값 찾기 (2018)

 (rcoh.me)
2P by GN⁺ | ★ favorite | 댓글 1개
  • 중앙값은 정렬하면 쉽게 구할 수 있지만, 정렬 비용 때문에 단일 원소 선택 문제에서도 O(n log n) 한계에 묶임
  • quickselect는 필요한 쪽만 재귀적으로 탐색해 평균 O(n) 에 kth 원소나 중앙값을 찾을 수 있음
  • 무작위 피벗은 실전에서 잘 동작하지만, 계속 나쁜 피벗을 고르면 한 번에 원소 하나만 제거되어 O(n²) 까지 악화됨
  • median-of-medians는 5개씩 묶은 그룹 중앙값에서 다시 중앙값을 골라, 최악의 경우에도 최소 30%의 원소를 제거할 수 있게 함
  • 실제 구현에서는 피벗 계산 비용이 커질 수 있어, C++ 표준 라이브러리처럼 quickselect와 heapselect를 조합한 introselect가 더 실용적인 선택이 될 수 있음

정렬로 중앙값을 찾을 때의 한계

  • 가장 단순한 중앙값 계산은 리스트를 정렬한 뒤 중앙 인덱스의 값을 고르는 방식임
  • 홀수 길이 리스트는 가운데 원소를 반환하고, 짝수 길이 리스트는 가운데 두 원소의 평균을 반환함
  • 비교 기반 정렬의 가장 빠른 시간복잡도는 O(n log n) 이므로, 이 방식의 실행 시간도 정렬이 지배함
  • 코드가 단순하다는 장점은 있지만, 중앙값 하나만 찾기에는 필요 이상의 작업을 함

평균 O(n)을 만드는 quickselect

  • quickselect는 Tony Hoare가 만든 재귀 알고리듬이며, 중앙값뿐 아니라 리스트의 임의 kth 원소를 찾을 수 있음
  • 기본 흐름은 피벗을 기준으로 리스트를 나눈 뒤, kth 원소가 들어 있는 쪽만 계속 탐색하는 방식임
    • 리스트에서 피벗(pivot)을 하나 고름
    • 피벗 이하 원소와 피벗 초과 원소로 리스트를 나눔
    • 찾는 kth 원소가 어느 쪽에 있는지 판단해 해당 부분 리스트에서만 재귀 호출함
    • 오른쪽 부분 리스트로 내려갈 때는 이미 제외한 왼쪽 원소 수만큼 k 값을 조정함
  • 예시 리스트 [9,1,0,2,3,4,6,8,7,10,5]에서는 길이가 11이므로 6번째로 작은 원소를 찾고, 피벗에 따라 범위를 좁혀 최종적으로 5를 반환함
  • quickselect_median은 리스트 길이가 홀수면 중앙 인덱스 하나를 quickselect로 찾고, 짝수면 가운데 두 인덱스를 찾아 평균을 냄
  • 피벗이 리스트를 거의 절반씩 나누면 처리량은 n + n/2 + n/4 + ... = 2n이 되어 O(n) 이 됨

최악의 경우를 피하려면 좋은 피벗이 필요함

  • quickselect의 평균 O(n)은 피벗 선택이 충분히 괜찮다는 조건에 기대고 있음
  • 매 단계에서 최댓값을 피벗으로 고르는 식으로 운이 나쁘면, 각 단계에서 원소 하나만 제거되어 O(n²) 가 됨
  • 최악의 경우에도 선형 시간을 보장하려면, quickselect에 충분히 좋은 피벗을 선형 시간에 제공해야 함
  • 이 피벗 선택 알고리듬은 1973년 Blum, Floyd, Pratt, Rivest, Tarjan이 개발했으며, 관련 논문은 1973 paper로 연결됨

median-of-medians 피벗 선택

  • median-of-medians는 quickselect가 사용할 좋은 피벗을 고르는 절차임
  • 구현 흐름은 다음과 같음
    • 원소가 5개 미만이면 기존 정렬 기반 중앙값 함수를 사용함
    • 리스트를 5개씩 묶음으로 나눔
    • 5개가 안 되는 불완전한 묶음은 단순화를 위해 버림
    • 각 묶음을 정렬하고 인덱스 2의 중앙값을 모음
    • 모인 중앙값 리스트에서 다시 중앙값을 찾아 피벗으로 반환함
  • 각 묶음의 크기는 고정된 5개이므로, 묶음별 정렬은 상수 시간으로 취급되고 전체로는 O(n) 작업임
  • 중앙값들의 중앙값을 찾는 재귀 호출은 크기 n/5인 하위 문제로 분석에 포함됨

왜 최소 30%를 제거할 수 있는가

  • 5개짜리 묶음을 정렬해 열로 놓고, 각 열의 중앙값을 다시 정렬해 중앙값들의 중앙값을 고른다고 보면 피벗의 품질을 분석할 수 있음
  • 피벗이 가능한 한 앞쪽에 치우치는 최악의 경우에도, 특정 사분면의 원소들은 피벗보다 작거나 크다고 보장됨
  • 각 열에서 3개 원소를 취하고 열의 절반을 고려하면, 최소한 3/5 * 1/2 * n = 3/10 n개의 원소를 제거할 수 있음
  • 제거 보장 비율: {p:30}
  • 전체 실행 시간은 다음 점화식으로 표현됨
T(n) = n + T(n/5) + T(7n/10)
  • 여기서 n은 분할 작업, T(n/5)는 median-of-medians 계산, T(7n/10)은 quickselect의 재귀 탐색에 해당함
  • 이 점화식에는 재귀항이 두 개 있으므로 단순한 마스터 정리를 적용할 수 없고, 귀납법이 직관적인 증명 방법임

조합 결과: 선형 시간 중앙값 찾기

  • quickselect는 충분히 좋은 피벗이 주어지면 중앙값을 선형 시간에 찾을 수 있음
  • median-of-medians는 quickselect에 필요한 좋은 피벗을 O(n) 에 고를 수 있음
  • 두 알고리듬을 결합하면 중앙값 또는 리스트의 n번째 원소를 선형 시간에 찾는 알고리듬이 됨

실제 구현에서의 선택

  • 실전에서는 무작위 피벗 선택이 거의 항상 충분함
  • median-of-medians도 선형 시간이지만, 실제로는 피벗 계산 비용이 커서 느릴 수 있음
  • C++ 표준 라이브러리는 introselect를 사용하며, heapselect와 quickselect를 조합하고 O(n log n) 상한을 가짐
  • introselect는 보통 빠르지만 상한이 나쁜 알고리듬으로 시작하고, 효과적인 피벗을 고르지 못할 때 더 느리지만 상한이 좋은 알고리듬으로 전환함
  • quickselect 함수가 살펴본 원소 수 비교에서는 결정적 피벗이 무작위 피벗보다 거의 항상 더 적은 원소를 고려했지만, 이 비교에는 median-of-medians 계산 비용이 포함되지 않음
  • 2017년에 나온 new paper는 median-of-medians 접근을 다른 선택 알고리듬과 경쟁 가능하게 만드는 내용을 담고 있음

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 약 4년 전에 여러 중앙값 알고리즘을 비교했는데, 글이 예상보다 훨씬 길어졌음 :)
    https://danlark.org/2020/11/11/miniselect-practical-and-generic-selection-algorithms/

    • 이 중에서 arg-median, 즉 중앙값을 가진 인덱스를 반환하도록 쉽게 바꿀 수 있는 알고리즘이 있나?

  • 10~15년 전, 멀티 킬로바이트 로그 항목에서 파싱한 수십억 개 값의 중앙값을 정기적으로 찾아야 했음. 당시 대용량 처리는 MapReduce를 쓰고 있었고, 이 정도 데이터에서는 선형 시간뿐 아니라 가능하면 단일 패스에 여러 머신으로 분산되는 방식이 필요했음
    데이터의 정밀도와 범위를 알고 있다는 점이 도움이 됨. 값은 정수 밀리초 단위의 타이밍이라 음수가 아니었고, 90번째 백분위수가 1초보다 훨씬 작다는 것도 알고 있었음
    보통 중앙값 찾기는 정렬과 비슷한 작업을 요구하지만, 이런 조건에서는 버킷 정렬이 가능해짐. 키를 정수 밀리초 타이밍으로, 값을 등장 횟수로 둔 딕셔너리, 즉 히스토그램을 만들면 됨
    최대 타이밍은 모르므로 딕셔너리 크기가 폭증하지 않게 999ms를 넘는 값은 모두 999ms 버킷에 넣었고, 그러면 0~999 키와 값으로 총 2000개 정수 정도에 제한됨. 이 부분이 일반적인 버킷 정렬과 달랐고, MapReduce로 분산해도 단일 패스로 매우 쉽게 처리 가능했으며 이후 히스토그램에서 중앙값을 뽑으면 됐음

    • 실제로 수십억 개 값의 정확한 중앙값이 필요했나? 아니면 49.9%와 50.1% 사이의 값이면 충분했나? 후자라면 훨씬 쉬움. 무작위로 균등하게 10,000개를 샘플링해서 그 중앙값을 쓰면 됨
      10,000이라는 숫자는 임의로 든 것이지만, 원하는 신뢰수준에 필요한 샘플 수는 통계적으로 계산할 수 있고 그렇게 엄청 크지는 않을 것 같음
    • 확실하진 않지만, 바깥에서 보기엔 Prometheus가 내부에서 하는 방식과 비슷해 보임
      내가 다뤘던 일부 시스템에서는 Prometheus가 지연 시간에 약 10초 제한을 둔 것처럼 동작했음. 그래서 그 한계를 넘는 요청은 실제로 더 길 수 있어도 전부 10초로 들어갔음. 흥미로움
    • 혹시 가용성 지표를 만들던 일이었고, 그때 인턴이었나? 그 시스템이 어, 아주 익숙하게 들림
    • 왜 0…999 키를 가진 딕셔너리를 썼는지 모르겠음. 0…999로 인덱싱되는 배열을 쓰면 되지 않나?

  • 2017년에 median-of-medians 접근을 다른 선택 알고리즘과 경쟁 가능하게 만든 새 논문이 나왔고, 논문 저자인 Andrei Alexandrescu가 알려줬다는 추신이 있음
    그는 2016년에 자기 알고리즘에 대한 발표도 했음. 발표가 재미있는 사람이라 강력 추천함
    There's Treasure Everywhere - Andrei Alexandrescu
    https://www.youtube.com/watch?v=fd1_Miy1Clg

    • Andrei Alexandrescu는 대단함. 2000년쯤 잠금 없는(lock-free) 대기 없는(wait-free) 알고리즘 발표를 했고, 당시 거대한 C++ 산업 제어 네트워킹 프로젝트에 바로 적용했음
      소프트웨어를 쓰는 사람이라면 찾을 수 있는 Andrei의 글과 발표를 전부 들어보고 읽어보길 추천함. 이 발표도 정말 보물임
    • 컴퓨터 과학 기준으로도 꽤 박식한 인물이라 놀라움. 템플릿 메타프로그래밍으로 알고 있었는데, 여기서는 프로그래밍 언어에서 알고리즘 쪽으로 옮겨가고 있음

  • 학부 때 median-of-medians quickselect 알고리즘을 배웠고 정말 인상 깊었음. 직접 구현해 봤지만 끔찍하게 느렸음. 실행 시간은 선형으로 늘었지만, 그게 의미 있으려면 리스트에 최소 수십억 개 항목은 있어야 했음
    이 얘기를 대학원생 친구와 하다가 “느리긴 하지만, 중요한 건 정렬되지 않은 리스트에서 선택을 O(n) 시간에 할 수 있다는 걸 증명한다는 점이야. 한때는 그게 가능한지도 몰랐고, 이제 가능하다는 걸 알았으니 더 빠른 선형 알고리즘도 있을 수 있지”라는 식의 말을 들었음
    너무 단순하면서도 깊은 교훈이라 거의 대학원에 지원할 뻔했음. 그 친구가 이 대화를 기억하는지는 모르겠지만, 내 교육에서 전환점 같은 순간이었음

    • 선형 시간 알고리즘이 하나 존재한다는 사실이 더 빠른 선형 시간 알고리즘의 존재를 시사하나? 그렇지 않다면 그 지식에서 얻는 이득이 뭔가?
      “이미 어떤 알고리즘이 존재한다는 걸 아니까 더 빠른 알고리즘도 있을 수 있다”고도 생각할 수 있음. O(n) 알고리즘의 존재가 O(n log n) 알고리즘의 존재보다 더 강한 신호가 되는 이유가 뭘까?
    • 컴퓨터 과학 4학년 때 이 알고리즘을 배운 것 같음. 말한 것처럼 이론적인 측면도 다뤘지만, 현실 대부분의 경우 느린 선형 알고리즘이 빠른 n log n 알고리즘보다 빠르지 않다는 걸 보여주는 예로도 쓰였음
      이 알고리즘의 상수 계수가 22 정도였던 것 같은데, 아마 관련 알고리즘이었을 수도 있음

  • median-of-medians 알고리즘의 재미있는 점 중 하나는 저자 목록이 완전히 스타급이라는 것임
    Manuel Blum - 1995년 튜링상 수상자
    Robert Floyd - 1978년 튜링상 수상자
    Ron Rivest - 2002년 튜링상 수상자
    Bob Tarjan - 1986년 튜링상 수상자이자 1982년 초대 Nevanlinna상 수상자
    Vaughan Pratt - 목록에서 유일하게 튜링상 수상자가 아니지만, Stanford 명예교수이고 Sun Microsystems가 되기 전 SUN 프로젝트를 이끌었으며 Sun 초기에 연구 책임자이자 Sun 로고 디자이너로 중요한 역할을 했고, Pratt 소수성 인증서처럼 멋진 것들도 많이 남겼음
    독립적인 튜링상이 네 개에 SPARCstation까지, 이 논문엔 다 있음

    • 신입 프런트엔드 개발자 면접 질문: “앞으로 30분 안에 튜링상 수상자 네 명의 작업을 재현하세요. 더러운 화이트보드와 마른 펜이 있습니다. 시간은 지금부터입니다”
    • 원 논문을 읽고 싶은 사람을 위한 직접 링크: https://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf
      저자 목록은 확실히 인상적임
    • Pratt의 다른 멋진 작업으로는 Pratt 파싱이 있음. HN 논의: https://news.ycombinator.com/item?id=39066465
      KMP 알고리즘의 “P”도 Pratt임

  • return l[len(l) / 2]
    Python 전문가는 아니지만, Python에서 / 연산자는 부동소수점을 반환하지 않나? 배열 인덱스로 부동소수점을 쓰는 대신 정수 나눗셈인 //를 쓰지 않는 이유가 뭘까?
    아주 큰 배열이 아니면 문제 되지 않을 수 있지만, 그래도 꽤 코드 냄새가 남. Python 초보라 두 연산자가 따로 있다는 걸 몰랐다면 넘어갈 수도 있지만, 글에는 한 분기에서는 정수 나눗셈을 쓰고 다른 분기에서는 부동소수점 나눗셈을 쓰는 더 이상한 코드도 있음
    def quickselect_median(l, pivot_fn=random.choice):
    if len(l) % 2 == 1:
    return quickselect(l, len(l) // 2, pivot_fn)
    else:
    return 0.5 * (quickselect(l, len(l) / 2 - 1, pivot_fn) +
    quickselect(l, len(l) / 2, pivot_fn))
    댓글이 50개나 됐는데 아무도 이걸 못 본 듯해서, 평균적인 Python 코드 품질에 대한 내 기존 편견만 더 강해짐

    • 잘 찾아냈음. Python 2에는 연산자가 하나뿐이었지만 Python 3에서는 둘이 구분됨
      부동소수점으로 배열을 인덱싱하면 예외가 발생할 거라고 봄
    • 코드 냄새라는 데는 동의함. 다만 알고리즘 글이므로 코드 품질로 판단하는 게 정확히 공정하진 않다고 봄
      의사코드 대신 의사코드처럼 보이는 실제 프로그래밍 언어를 골랐고, 설명용으로는 아마 잘 실행되는 코드라고 생각함

  • 원문은 정말 재미있게 읽었지만, “매 단계에서 가장 큰 원소를 피벗으로 고르면 O(n) 대신 O(n²)가 될 수 있다”는 부분은 걸림
    적대적 입력이 걱정이라면 데이터를 먼저 O(n)에 셔플하면 그런 일이 강제로 일어나는 걸 막을 수 있음. 데이터가 너무 커서 셔플하기 어렵다면, 버킷이 셔플 가능한 크기로 작아졌을 때 한 번만 섞으면 됨
    셔플을 했다면 확률이 최악의 경우가 사실상 일어나지 않음을 보장함. 누가 “기술적으로는” 가능하다고 하면, “기술적으로는” 공격자가 256비트 개인키의 모든 비트를 맞힐 수도 있다고 답하겠음
    우리 세계는 확률 위에 세워져 있음. 모든 개인키는 누군가 정확히 맞힐 수 없다는 수학적 비가능성에 보호받고 있음
    내가 읽은 바로는 셔플 후 quickselect는 실용적으로는 O(n)임

    • 이미 피벗을 무작위로 고르는 데 자체 난수를 쓰고 있으니, 셔플이 왜 더 도움이 되는지 모르겠음
      그래도 난수를 신뢰할 수 있다면 O(n)을 넘는 실행 시간이 나올 확률은 매우 낮음
    • “적대적 입력이 걱정이라면 데이터를 먼저 O(n)에 셔플하면 이를 보장한다”는 건 최악의 경우를 피한다고 보장하는 게 아니라, 최악의 경우를 강제할 가능성을 제거하는 것임

  • Floyd-Rivest도 그 일을 해냄. 기억이 맞다면 조금 더 효율적임
    하지만 나는 작동 원리를 끝내 이해하지 못했음
    https://en.m.wikipedia.org/wiki/Floyd%E2%80%93Rivest_algorithm

  • n번째 원소를 고를 때 n이 아주 작거나 아주 크다면 median-of-medians가 최선이 아닐 수 있음
    대신 [1]처럼 편향된 피벗을 쓰거나, 내가 “j번째 of k번째”라고 부르는 방식을 쓸 수 있음. Floyd-Rivest도 속도를 높일 수 있음
    잘 구현된 quickselect와 비교해 처리량이 1.2~2.0배 나오는 취미 프로젝트가 있음: https://github.com/koskinev/turboselect
    빠른 범용 제자리 선택 알고리즘에 대한 자료가 있으면 관심 있음
    [1] https://doi.org/10.4230/LIPIcs.SEA.2017.24

  • 전체 데이터를 메모리에 저장하지 않고도 임의 분위수의 근삿값을 계산할 수 있는 스트리밍 알고리즘을 쓸 수도 있음

    • 근삿값을 허용할 수 있다면 멋진 방식임. 하지만 곧 불편한 질문들이 생김
      근사 계산을 허용할 수 있는가? 오차 한계를 정하려면 데이터에 대해 어떤 가정이 필요한가? 그 가정이 계속 유효한지 어떻게 검증할 것인가?
      개인적으로는 스트리밍 중앙값 근사 방식을 고려해야만 하는 상황이 오기 전까지는 원문에 나온 quickselect 알고리즘 쪽으로 기울 것 같음
    • 스트리밍 분위수 알고리즘이 유용했을 상황이 분명 있었음. 참고할 만한 자료가 있나?
답변달기