새로운 책 정렬 알고리듬, 완벽에 가까운 성과

 (quantamagazine.org)
2P by GN⁺ | ★ favorite | 댓글 1개
  • 도서관 정렬 문제는 책장 정리를 넘어 하드드라이브와 데이터베이스의 순차 저장 비용을 좌우하며, 새 연구는 평균 삽입 시간을 이론적 한계에 매우 가깝게 낮춤
  • 1981년 알고리듬은 결정적이고 매끄러운(smooth) 방식으로 평균 삽입 시간 ((log n)^2)를 보장했지만, 40년 넘게 더 낮은 상한이 나오지 않았음
  • 이후 하한 연구는 일반 알고리듬의 최선이 (log n), 매끄러운 알고리듬과 결정적 알고리듬의 한계가 ((log n)^2)임을 보여 무작위적·비매끄러운 접근이 필요해짐
  • 2022년 Bender, Kuszmaul 등은 이력 독립(history independent) 무작위 알고리듬으로 상한을 ((log n)^{1.5})까지 낮췄고, 최신 연구는 제한적 과거 정보까지 활용해 ((log n)(log log n)^3)를 달성함
  • 남은 차이는 (log log n) 항이며, 이 진전은 리스트 라벨링 기반 동적 그래프 저장·처리 같은 응용의 속도 개선으로 이어질 수 있음

도서관 정렬 문제가 묻는 것

  • 도서관 정렬 문제는 정렬된 순서를 유지하면서 새 항목을 넣을 때 필요한 이동 시간을 최소화하는 문제임
  • 책을 한쪽에 몰아두면 중간에 새 책을 넣을 때 많은 책을 다시 옮겨야 함
    • Isabel Allende 책을 추가할 때 전체 책을 옮겨야 할 수 있음
    • 이후 Douglas Adams 책을 추가하면 같은 작업이 반복될 수 있음
  • 빈 공간을 책장 전체에 적절히 분산하면 삽입 비용을 줄일 수 있지만, 공간을 어디에 얼마나 남길지가 핵심임
  • 더 형식적으로는 리스트 라벨링(list labeling) 문제로 불리며, 1981년 논문에서 도입됨
  • 적용 범위는 책장을 넘어 하드드라이브와 데이터베이스의 파일·항목 배치까지 확장됨
    • 항목 수가 수십억 개에 이를 수 있음
    • 비효율적인 배치는 긴 대기 시간과 큰 계산 비용으로 이어짐

상한과 하한으로 보는 성능

  • 정렬된 배치의 성능은 보통 새 항목 하나를 삽입하는 데 걸리는 시간으로 평가함
  • 항목 수가 (n)일 때 모든 책을 옮겨야 한다면 삽입 시간은 (n)에 비례함
    • 이는 새 항목 추가에 걸릴 수 있는 시간의 상한으로 볼 수 있음
  • 1981년 논문은 평균 삽입 시간을 (n)보다 훨씬 줄일 수 있는지를 물었고, ((log n)^2)를 보장하는 알고리듬을 제시함
    • 무작위성에 의존하지 않는 결정적 알고리듬임
    • 삽입이나 삭제가 일어나는 구간 안에서 항목이 고르게 퍼져야 하는 매끄러운(smooth) 성질을 가짐
  • 연구자들은 상한과 하한의 간격을 좁혀 두 값이 일치할 때 알고리듬이 최적이라고 판단함

기존 하한 결과가 만든 제약

  • 2004년 연구는 도서관 정렬 문제의 가장 일반적인 버전에서 어떤 알고리듬도 (log n)보다 나을 수 없다는 궁극적 하한을 보임
  • 1990년에는 매끄러운 알고리듬의 하한이 ((log n)^2)임이 확인됨
  • 2012년에는 무작위성을 쓰지 않는 결정적 알고리듬도 같은 하한 ((log n)^2)을 가진다는 결과가 나옴
  • 이 결과들은 매끄러운 알고리듬이나 결정적 알고리듬만으로는 1981년의 ((log n)^2) 상한을 개선하기 어렵다는 뜻임
  • Michael Bender는 더 나은 결과를 위해 무작위적이고 비매끄러운 알고리듬이 필요하다고 판단함
    • 비매끄러운 방식은 항목을 고르게 벌려두지 않아 직관적으로 위험해 보였음
    • 무작위 선택이 왜 도움이 되는지도 분명하지 않았음

2022년: 이력 독립으로 상한을 낮춤

  • Bender, William Kuszmaul 등 6명은 2022년 이력 독립·비매끄러운·무작위 알고리듬을 만들었음
  • 이력 독립 알고리듬은 책장의 과거 상태를 드러내지 않음
    • Kuszmaul은 책장에 있던 책을 뺐을 때 다른 사람이 그 사실을 알 수 없는 예를 들었음
    • 이런 성질은 프라이버시나 보안상의 이유로 활용될 수 있음
  • 이 알고리듬은 1981년 상한을 처음으로 낮춰 평균 삽입 시간을 ((log n)^{1.5})로 줄임
  • Kuszmaul은 보통 프라이버시를 위해 쓰는 도구가 알고리듬을 더 빠르게 만들 수 있다는 점을 뜻밖으로 받아들임
  • Georgia Institute of Technology의 Helen Xu는 보안 이외의 이유로 이력 독립을 쓰는 아이디어가 다른 문제에도 영향을 줄 수 있다고 평가함

최신 연구: 제한적 과거 정보와 무작위성의 결합

  • Bender, Kuszmaul 등은 최신 논문에서 상한을 다시 낮춰 ((log n)(log log n)^3)를 달성함
  • 이 값은 ((log n)^{1.000…1})에 해당하며, 궁극적 하한인 (log n)에 매우 가까움
  • 새 접근도 비매끄럽고 무작위적이지만, 이번에는 제한적인 이력 의존(history dependence) 을 사용함
  • 알고리듬은 과거 추세를 일부 보고 미래 삽입에 대비함
    • Nabokov, Neruda, Ng처럼 성이 N으로 시작하는 저자의 책이 많이 들어왔다면 N 구역에 조금 더 여유 공간을 둠
    • 다만 너무 많은 공간을 예약하면 A로 시작하는 저자의 책이 많이 들어올 때 문제가 될 수 있음
  • Bender는 결정을 내릴 때 얼마나 많은 과거를 볼지 전략적으로 무작위화해 이 접근을 유용하게 만들었다고 설명함
  • Seth Pettie는 이번 연구가 2022년 논문과 완전히 다른 방식으로 무작위성을 사용한다고 평가함

남은 간격과 응용 가능성

  • 남은 간격은 작은 (log log n) 항임
  • Bender는 상한을 더 낮춰야 하는지, 하한을 올려야 하는지 아직 알 수 없다고 말함
  • Pettie는 간격이 이 정도로 좁고 한쪽 경계가 자연스럽고 다른 쪽이 부자연스러워 보일 때 보통 자연스러운 쪽이 정답이 된다고 봄
    • 향후 개선은 상한을 (log n)까지 낮추는 방향일 가능성이 더 크다고 평가함
    • 다만 “세상은 이상한 놀라움으로 가득하다”고 덧붙임
  • University of Chicago의 Brian Wheatman은 이 논문들이 이론적으로 상당한 개선이며, 응용 측면에서도 큰 개선 가능성이 있다고 봄
  • Helen Xu는 최근 리스트 라벨링 기반 데이터 구조로 동적 그래프를 저장하고 처리하는 데 관심이 있었고, 이번 진전이 거의 확실히 더 빠르게 만들 것이라고 봄

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • “개인정보 보호에 쓰이던 도구가 다른 이점도 줄 수 있다”는 점이 나도 놀라웠음
    곰곰이 보면 성능 대부분은 문자 그대로 “시간당 더 많은 명령을 실행”하는 문제가 아니라, 덜 일하도록 방법을 고르는 것에 가까움
    여기서 보안 속성인 이력 독립성은 “이력을 추적하는 일을 할 필요도 없고, 문자 그대로 할 수도 없다”는 뜻이기도 해서, 암호학을 제약으로 써서 불필요한 일을 막는 흥미로운 성능 접근처럼 느껴짐

    • 그 해석은 정확하지 않아 보임. 알고리즘의 느림을 계산 시간으로 측정한다면 맞겠지만, 여기서 실제 측정 기준은 옮겨야 하는 책의 수임
      이해한 바로는 계산 시간은 무한히 써도 되는 모델임
    • 좋은 통찰임. 좋은 알고리즘/자료구조 설계의 핵심은 데이터셋에 있는 정보를 모두 활용하는 것이라고 생각해 왔음
      예를 들어 목록이 정렬돼 있음을 알면 이진 탐색을 쓸 수 있음. 그런데 어쩌면 얼마나 정보를 생략할지를 고르는 것도 핵심일 수 있겠음. 다만 이런 경우는 덜 자주 보이고, 간단한 예시는 바로 떠오르지 않음
    • 결국 알고리즘이 “더 열심히”가 아니라 “더 똑똑하게” 동작하도록, 문제 맥락 중 무엇을 선택적으로 숨길 수 있고 숨겨야 하는지 찾는 문제처럼 보임. 묘함
    • 실제로 더 나은 알고리즘은 이력 의존성을 사용함. 그래서 기사에서 이 부분은 다소 오해를 부른다고 봄

  • 기사에서 설명하는 핵심 논문, 즉 원래 문제와 거의 최적인 알고리즘 논문 [1], [2]를 찾으려 한 사람이 나뿐인지 궁금함
    둘 다 기사 깊숙한 곳에 링크된 듯한데, Quanta가 기사 끝에 모든 참고문헌을 의무적으로 모아두면 독자에게 아주 도움이 될 것 같음
    [1] Nearly Optimal List Labeling:
    https://arxiv.org/abs/2405.00807
    [2] A sparse table implementation of priority queues:
    https://link.springer.com/chapter/10.1007/3-540-10843-2_34

    • 두 논문 모두 기사에 아주 명확히 링크돼 있고, 읽지 않고 훑기만 해도 금방 찾을 수 있었음
      “This problem was introduced in a 1981 paper”에서 “1981 paper”가 https://link.springer.com/chapter/10.1007/3-540-10843-2_34로 연결되고, 다음 문단의 “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers”에서 “a study”가 https://arxiv.org/abs/2405.00807로 연결됨
      둘 다 도입부의 세 번째, 네 번째 문단에 있고 세부 내용·역사·맥락으로 들어가기 전임. 이 정도를 “기사 깊숙한 곳”이라고 한다면, 깊숙한 곳의 기준이 꽤 다를 수밖에 없겠음

  • 지난주에 바로 이 문제를 보고 있었음. 데이터베이스 테이블의 항목들을 임의 위치에 두되, 가능하면 나머지 목록을 건드리지 않고 싶었음
    사용자가 5번 항목 뒤에 새 원소를 추가하면 그 원소가 6이 되지만, 기존에 5번 뒤에 있던 항목은 업데이트하지 않는 식임. 이 문제를 관리하고 이론적 한계를 최소화하는 매우 정교한 알고리즘들이 실제로 있음
    다만 이 특정 버전에서는 분수 인덱스를 쓰고, 가끔 목록을 다시 배치하는 비용을 치르는 게 가장 단순한 해법처럼 보였음

    • Wikipedia의 exponential labels 섹션에 이 알고리즘이 있음: https://en.m.wikipedia.org/wiki/List-labeling_problem
      기본적으로 라벨 공간이 항목 수에 비해 크면 잘 동작함. 그렇지 않을 때 더 정교한 방법이 필요함. 예를 들어 라벨에 4바이트만 있고 항목이 10억 개라면 문제가 됨
    • 이 문제를 면접 질문으로 그대로 받은 적이 있음
      기억하기로 실제 해법은 원소 사이에 간격을 남기는 방식이었음. 예를 들어 0, 1, 2 대신 0, 100, 200처럼 두고 필요할 때 다시 인덱싱함. 충분히 잘 동작할 것 같음
      내가 떠올린 건 말한 것처럼 분수 인덱싱이었는데, 소수를 다루기 귀찮으니 벡터로 표현하고, 이를 사전식으로 정렬되는 숫자 문자열로 나타낼 수 있음
      1과 2 사이에 삽입된 원소는 인덱스 11이 됨. 11~19 사이 아무거나 가능함. 1과 11 사이면 101, 11과 2 사이면 12 같은 식임. 단 이 인덱스들은 숫자가 아니라 사전식으로 비교되는 문자열임
      단점도 분명 있을 것 같음. 예를 들어 이런 인덱스를 정렬하려면 메모리를 훨씬 더 많이 씀. 문자열은 숫자보다 훨씬 크니까. 예상치 못한 단점이 없기엔 너무 영리한 느낌도 듦
    • 옛날 BASIC 프로그램의 줄 번호 같음
    • 이론적으로 분수를 목록 라벨로 쓰려면 분수를 저장하는 데 무한한 메모리가 필요함
      실제로는 그 한계가 아주 제한적이지만, 단순히 컬렉션에 순서 라벨을 붙이는 게 아니라 이 라벨을 배열 인덱스로 직접 써서 원소를 저장하려 하면 차이가 정말 문제가 됨. 그쪽이 도서관 정렬 문제를 더 문자 그대로 모델링한 형태임
    • 그건 해시 테이블 체이닝 아닌가?

  • 몇 년 전에 Library Sort 알고리즘을 바탕으로 한 문제를 학생들에게 발표했던 기억이 있음
    원 논문 제목이 아직도 또렷함: “Insertion Sort is O(n log n)”

  • 이 알고리즘이 실제 현장에서 현재 쓰는 방식보다 정말 빠를 이유가 있는지 궁금함
    내가 이 문제를 주로 만난 곳은 B-tree 노드의 배열인데, 거기서는 그냥 memmove()를 쓰는 것보다 빠를지 의심스럽고, 정말 큰 배열이라면 B-tree를 쓰는 편이 더 쉬울 듯함
    그렇다면 이 알고리즘도 점근적으로는 더 빠르지만 역설적으로 실제 사용 알고리즘보다 느린 부류에 들어감. 빠른 행렬 곱셈 알고리즘들이 좋은 구현의 교과서적 O(n^3) 알고리즘(GEMM)보다 느린 것이 예시임

    • 이런 알고리즘을 가끔 Galactic Algorithms라고 부름: https://en.wikipedia.org/wiki/Galactic_algorithm
      페이지의 첫 예시가 유용성을 잘 설명하는 인용을 담고 있음
      “galactic algorithm의 예로, 두 수를 곱하는 알려진 가장 빠른 방법은 1729차원 푸리에 변환에 기반한다. O(n log n) 비트 연산만 필요하지만, 빅오 표기 안에 숨은 상수가 커서 실제로는 쓰이지 않는다. 그래도 이런 알고리즘이 왜 유용할 수 있는지는 보여준다. 저자들은 ‘추가 개선을 통해 수십억 또는 수조 자리 숫자만으로도 실용화되길 바란다’고 말한다”

  • 상한을 (log n) × (log log n)^3로 낮춘다 — (log n)^(1.000...1)에 해당한다는 말은 사실임
    다항식 기준 계열로 빅오 복잡도를 볼 때 멋진 점 중 하나가 로그가 무한소 값을 준다는 것임. “무한소는 실제로 존재하지 않는다”는 사람들에게 한 방임

    • 잠깐, 뭐라고? 이걸 배울 수 있는 참고자료가 있을까?

  • British Library가 수백만 권의 책과 매주 수많은 신간을 어떻게 관리하는지 알고 놀랐음
    올해 초 가장 먼저 들어온 책은 선반의 2025.0000001 위치에 놓였고, 다음 책은 바로 옆 2025.0000002에 놓였음. 나머지는 전자 카탈로그가 처리함
    책을 다시 뒤섞을 필요는 없지만, 서가를 둘러보며 책을 찾는 방식에는 맞지 않는 해법임

    • Amazon이 물건을 매장처럼 비슷한 것끼리 배치하지 않는 방식이 떠오름. 진공청소기 모델 옆에 주방 접시 세트가 있을 수 있음
      오히려 의도적으로 유사성을 피해서 피커가 비슷하지만 잘못된 물건을 집지 않게 함
      집에서도 가끔 쓰는 물건을 어디 뒀는지 자주 잊어버림. x-acto 칼날 리필을 어느 벽장의 어느 수납함에 넣었는지 같은 것들임. 비슷한 물건끼리 모으려다 보니 한 수납함은 넘치고 다른 하나는 반쯤 비어 있기도 함
      가끔 모든 소지품을 스프레드시트로 추적해서 어느 수납함에 있는지 기록하면, 물건을 잃어버리지 않고 수납 공간도 최대 효율로 쓸 수 있겠다고 상상함. 하지만 새 물건을 넣을 때 업데이트를 빼먹을 게 뻔하고, 사람보다는 로봇이 할 법한 비인간적으로 이상한 방식처럼 느껴짐

  • 기사 맨 위의 애니메이션으로 화면 보호기를 만들고 싶어졌음

  • 핵심 제약을 파악하려는 중임. 문제 정의가 고정 길이로 미리 할당된 배열을 가정하나?

    • 아니, 배열을 전혀 가정하지 않음. 전체 순서가 있는 집합을 유지하는 자료구조이고 연산은 세 가지임:
      insert(X), delete(X), label(X)
      label은 이전에 삽입됐고 아직 삭제되지 않은 원소 X의 라벨을 꺼냄. 라벨은 0부터 n-1까지의 숫자이고, n은 현재 저장된 원소 수임
답변달기