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

> Clean Markdown view of GeekNews topic #18914. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=18914](https://news.hada.io/topic?id=18914)
- GeekNews Markdown: [https://news.hada.io/topic/18914.md](https://news.hada.io/topic/18914.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-01-26T10:12:40+09:00
- Updated: 2025-01-26T10:12:40+09:00
- Original source: [quantamagazine.org](https://www.quantamagazine.org/new-book-sorting-algorithm-almost-reaches-perfection-20250124/)
- Points: 2
- Comments: 1

## Topic Body

### 소개
- 새로운 알고리듬이 도서관 정렬 문제를 해결하는 방법을 제시함.
- 이 문제는 단순히 책을 정렬하는 것뿐만 아니라, 하드 드라이브와 데이터베이스의 파일 배열에도 적용됨.
- 새로운 접근법은 책장의 과거 내용과 무작위성을 결합하여 이론적 이상에 가까운 결과를 도출함.

### 경계 좁히기
- 잘 정렬된 책장을 측정하는 일반적인 방법은 개별 항목을 삽입하는 데 걸리는 시간을 보는 것임.
- 1981년 논문에서는 평균 삽입 시간이 n보다 훨씬 적은 알고리듬을 설계할 수 있는지에 대한 질문을 제기함.
- 2004년 연구에서는 도서관 정렬 문제의 최적 하한이 log n임을 발견함.
- 매끄럽거나 결정적인 알고리듬으로는 (log n)²보다 나은 평균 삽입 시간을 달성할 수 없음을 보여줌.

### 비밀의 역사
- 2022년, Bender와 동료들은 무작위적이고 비매끄러운 알고리듬을 시도하여 평균 삽입 시간을 (log n)¹.⁵로 줄임.
- 이 알고리듬은 과거의 책장 기록에 의존하지 않으며, 이는 보안상의 이유로 유용할 수 있음.

### 격차 줄이기
- Bender와 Kuszmaul은 상한을 (log n) × (log log n)³로 낮추어 이론적 하한에 매우 근접함.
- 이 알고리듬은 제한된 정도의 역사 의존성을 사용하여 미래의 사건을 계획함.
- 이 결과는 이전 연구를 기반으로 하여 무작위성을 완전히 다른 방식으로 사용함.

### 결론
- 이 연구는 이론적 측면에서 중요한 개선을 나타내며, 응용 측면에서도 큰 개선 가능성을 가짐.
- 여전히 log log n 용어가 완전한 해결책을 방해하고 있으며, 상한을 낮추거나 하한을 높이는 것이 해결책이 될 수 있음.

## Comments



### Comment 33866

- Author: neo
- Created: 2025-01-26T10:12:40+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=42814275) 
- 암호화 기술이 성능을 향상시키는 데 사용될 수 있다는 점이 흥미로움. 성능은 단순히 더 많은 명령을 실행하는 것이 아니라, 어떻게 일을 덜 할지를 선택하는 것임. "역사 독립성"이라는 보안 속성은 과거를 추적하는 작업을 하지 않음을 의미함

- 기사에 언급된 주요 논문을 찾는 것이 어려움. 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)

- 데이터베이스 테이블에서 항목을 임의로 배치하는 문제를 해결하기 위해 복잡한 알고리즘이 존재함. 그러나 이 문제의 간단한 해결책은 분수 값을 사용하고 가끔 리스트를 재배치하는 것임

- 'Library Sort' 알고리즘을 기반으로 학생들에게 문제를 제시했던 기억이 있음. 원 논문의 제목은 'Insertion Sort is O(n log n)'임

- 현재 사용 중인 알고리즘보다 실제로 더 빠를 이유가 있는지 의문임. B-tree 노드의 배열에서는 `memmove()`를 사용하는 것이 더 빠를 수 있음. 큰 배열의 경우 B 트리를 사용하는 것이 더 쉬움

- 문제 진술이 고정 길이의 미리 할당된 배열을 가정하는지 궁금함

- 영국 도서관이 책을 관리하는 방식에 놀라움. 책이 도착하면 전자 카탈로그가 나머지를 처리하여 책을 재배치할 필요가 없음

- 기사 상단의 애니메이션을 화면 보호기로 만들고 싶음

- 모바일 사용자를 위한 깨끗한 링크 제공

  - 게임: [링크](https://patorjk.com/games/subpixel-snake/)
  - 코드: [링크](https://github.com/patorjk/subpixel-snake)
  - 서브픽셀 기하학 리소스: [링크](https://geometrian.com/resources/subpixelzoo/)

- 상한을 (log n) 곱하기 (log log n)^3으로 낮추는 것이 사실임. 다항식 참조 클래스를 사용한 big-O 복잡성에서 로그가 무한소 값을 제공하는 것이 흥미로움