GN⁺: 새로운 책 정렬 알고리즘, 완벽에 가까운 성과
(quantamagazine.org)소개
- 새로운 알고리듬이 도서관 정렬 문제를 해결하는 방법을 제시함.
- 이 문제는 단순히 책을 정렬하는 것뿐만 아니라, 하드 드라이브와 데이터베이스의 파일 배열에도 적용됨.
- 새로운 접근법은 책장의 과거 내용과 무작위성을 결합하여 이론적 이상에 가까운 결과를 도출함.
경계 좁히기
- 잘 정렬된 책장을 측정하는 일반적인 방법은 개별 항목을 삽입하는 데 걸리는 시간을 보는 것임.
- 1981년 논문에서는 평균 삽입 시간이 n보다 훨씬 적은 알고리듬을 설계할 수 있는지에 대한 질문을 제기함.
- 2004년 연구에서는 도서관 정렬 문제의 최적 하한이 log n임을 발견함.
- 매끄럽거나 결정적인 알고리듬으로는 (log n)²보다 나은 평균 삽입 시간을 달성할 수 없음을 보여줌.
비밀의 역사
- 2022년, Bender와 동료들은 무작위적이고 비매끄러운 알고리듬을 시도하여 평균 삽입 시간을 (log n)¹.⁵로 줄임.
- 이 알고리듬은 과거의 책장 기록에 의존하지 않으며, 이는 보안상의 이유로 유용할 수 있음.
격차 줄이기
- Bender와 Kuszmaul은 상한을 (log n) × (log log n)³로 낮추어 이론적 하한에 매우 근접함.
- 이 알고리듬은 제한된 정도의 역사 의존성을 사용하여 미래의 사건을 계획함.
- 이 결과는 이전 연구를 기반으로 하여 무작위성을 완전히 다른 방식으로 사용함.
결론
- 이 연구는 이론적 측면에서 중요한 개선을 나타내며, 응용 측면에서도 큰 개선 가능성을 가짐.
- 여전히 log log n 용어가 완전한 해결책을 방해하고 있으며, 상한을 낮추거나 하한을 높이는 것이 해결책이 될 수 있음.
Hacker News 의견
-
암호화 기술이 성능을 향상시키는 데 사용될 수 있다는 점이 흥미로움. 성능은 단순히 더 많은 명령을 실행하는 것이 아니라, 어떻게 일을 덜 할지를 선택하는 것임. "역사 독립성"이라는 보안 속성은 과거를 추적하는 작업을 하지 않음을 의미함
-
기사에 언급된 주요 논문을 찾는 것이 어려움. Quanta가 모든 참고 문헌을 기사 끝에 나열하도록 하면 독자에게 도움이 될 것임
-
데이터베이스 테이블에서 항목을 임의로 배치하는 문제를 해결하기 위해 복잡한 알고리즘이 존재함. 그러나 이 문제의 간단한 해결책은 분수 값을 사용하고 가끔 리스트를 재배치하는 것임
-
'Library Sort' 알고리즘을 기반으로 학생들에게 문제를 제시했던 기억이 있음. 원 논문의 제목은 'Insertion Sort is O(n log n)'임
-
현재 사용 중인 알고리즘보다 실제로 더 빠를 이유가 있는지 의문임. B-tree 노드의 배열에서는
memmove()를 사용하는 것이 더 빠를 수 있음. 큰 배열의 경우 B 트리를 사용하는 것이 더 쉬움 -
문제 진술이 고정 길이의 미리 할당된 배열을 가정하는지 궁금함
-
영국 도서관이 책을 관리하는 방식에 놀라움. 책이 도착하면 전자 카탈로그가 나머지를 처리하여 책을 재배치할 필요가 없음
-
기사 상단의 애니메이션을 화면 보호기로 만들고 싶음
-
모바일 사용자를 위한 깨끗한 링크 제공
-
상한을 (log n) 곱하기 (log log n)^3으로 낮추는 것이 사실임. 다항식 참조 클래스를 사용한 big-O 복잡성에서 로그가 무한소 값을 제공하는 것이 흥미로움