근처 정렬 알고리즘 - 언제 사용해야합니까?

Question

때때로 나는 웹을 탐색하고 내 트릭 백에 넣을 흥미로운 알고리즘과 데이터 구조를 찾습니다. 1 년 전에 나는 만났다 소프트 힙 데이터 구조와 거의 정렬에 대해 배웠습니다.

이것의 배후에있는 아이디어는 정렬 알고리즘이 약간 속임수를 쓰고 있다는 사실과 함께 살 수 있다면 비교 기반 정렬의 O (n log n) 장벽을 깨뜨릴 수 있다는 것입니다. 거의 정렬 된 목록을 얻지 만 몇 가지 오류가 있어야합니다.

나는 테스트 환경에서 알고리즘을 가지고 놀았지만 그것들을 위해 사용을 찾지 못했습니다.

그래서 질문 : 실제로 정렬을 사용한 사람이 실제로 본 적이 있습니까? 그렇다면 어떤 종류의 애플리케이션? 가까운 정렬이 옳은 일이 어디에 있는지 유스 케이스를 생각할 수 있습니까?

Answer 1

정기적으로 세트를 선택하는 "욕심 많은"휴리스틱이 많이 있습니다. 욕심 많은 휴리스틱은 완벽하지 않으므로 최소한을 선택하더라도 최고의 최종 답변을 보장하지는 않습니다. 사실, 파악 메타 허풍으로, 당신은 의도적으로 임의의 오류를 도입하여 여러 최종 솔루션을 얻고 최고의 솔루션을 선택할 수 있습니다. 이 경우 속도와 교환하여 정렬 루틴에 약간의 오류를 도입하는 것은 좋은 거래입니다.

Answer 2

이것은 전체 비행 추측이지만 검색 결과를 정렬 할 때 "관련성"측정의 고유 한 주관성을 감안할 때, 그들이 완벽하게 정렬되었는지 여부는 중요하지 않다는 것을 알게 될 것입니다. 권장 사항도 마찬가지입니다. 어떻게 든 그러한 것들에 대한 알고리즘의 다른 모든 부분이 O (n)이라는 것을 정리할 수 있다면 종류를 피할 수 있습니다.

또한 최악의 경우 "거의 정렬 된"데이터 하지 않습니다 "거의 분류 된"에 대한 직관적 인 아이디어 중 하나를 충족시킵니다. 이는 적은 수의 반전 만 가지고 있다는 것입니다. 그 이유는 데이터에 O (n) 반전 만 있으면 삽입 정렬 또는 칵테일 정렬 (예 : 양방향 버블 정렬)을 사용하여 O (N) 시간으로 정렬 할 수 있기 때문입니다. O (n) 시간 (비교 사용)에서 완전히 분류되지 않은이 시점에 도달 할 수는 없습니다. 따라서 데이터의 다수 하위 집합이 정렬되고 나머지가 흩어져있는 응용 프로그램을 찾고 있습니다. ~ 아니다 모든 요소가 올바른 위치에 가까워 지도록 요구하는 응용 프로그램의 경우.

Answer 3

여기서 추측하지만, 내가 상상하는 한 가지는 데이터베이스 쿼리 최적화입니다.

SQL과 같은 선언적 언어의 데이터베이스 쿼리는 "실행 계획"이라는 단계별 프로그램으로 변환되어야합니다. 하나의 SQL 쿼리는 일반적으로 여러 실행 계획으로 변환 될 수 있으며, 모두 동일한 결과를 제공하지만 매우 다양한 성능을 가질 수 있습니다. 쿼리 옵티마이저는 가장 빠른 것, 또는 적어도 합리적으로 빠른 것을 찾아야합니다.

비용 기반 쿼리 최적화기에는 "비용 함수"가있어 주어진 계획의 실행 시간을 추정하는 데 사용합니다. 철저한 최적화제는 가능한 모든 계획 ( "모든 가능"의 일부 가치에 대해)을 거치고 가장 빠른 계획을 선택합니다. 복잡한 쿼리의 경우 가능한 계획의 수는 엄청나게 클 수 있으므로 (데이터베이스에서 검색을 시작하기 전에!) 비 수명 최적화기도 있습니다. 그들은 어떤 계획을 선택할 때 임의의 요소를 가진 일부 계획 만 본다. 이것은 일반적으로 많은 "좋은"계획이 있기 때문에 가장 좋은 계획을 찾는 것이 중요하지 않을 수 있습니다. 최적의 2 초 계획 대신 5 초 계획을 선택하는 것이 좋습니다. , 2 초 계획을 찾기 위해 몇 분의 최적화가 필요한 경우.

일부 최적화 알고리즘은 "Promising"(부분) 계획의 정렬 된 대기열을 사용합니다. 절대적으로 최고의 계획을 찾는 것이 중요하지 않다면 거의 소개 된 대기열을 사용할 수 있습니까?

또 다른 아이디어 (그리고 여전히 추측하고 있음)는 시간 공유 시스템의 프로세스 또는 스레드를위한 스케줄러이며, 특정 프로세스 나 스레드가 우선 순위에 의해 엄격하게 정렬되는 것보다 몇 밀리 초반에 시간이 지나면 중요하지 않을 수 있습니다. .

Answer 4

거의 자리 잡기를위한 일반적인 응용 프로그램은 인간이 쌍별 비교를하고 있는데 많은 질문을하고 싶지 않을 때입니다.

인간이 쌍별 비교를 통해 분류하기를 원하는 항목이 많이 있다고 가정 해보십시오. 주문이 정확하지 않다는 것을 기꺼이 받아들이려면 필요한 비교 수를 크게 줄일 수 있습니다. 예를 들어, 인접한 품목이 선호하는 항목이 상단에 있기 때문에 오랫동안 교체되었는지 신경 쓰지 않을 수 있습니다.

Answer 5

어딘가에

1. 당신은 빨리 반응해야합니다.
2. 당신은 고객에게 정확한 행동을 약속하지 않습니다.
3. 그러나 내부적으로 몇 가지 규칙이 있습니다

당신은 그것을 사용할 수 있습니다. "그렇게 엄격하지 않은"규칙 기반 우선 순위 대기열은 어떻습니까? 그것이 어디에 유용할까요? 스레드/프로세스/리소스 스케줄링 일 수 있습니다. 스레드/프로세스 스케줄링에서는 실제로 한 스레드가 먼저, 두 번째 또는 마지막으로 갈 것이라고 약속하지는 않지만 일반적으로 모든 사람에게 기회를주고 싶습니다. 느슨한 규칙을 시행하여 선제 적, 우선 순위, Blabla ..

자원 일정 예제는 피자 배달 또는 사람들에게 책 배송 상자에 응답하는 것입니다.

Answer 6

o (n log n)은 이미 꽤 빠릅니다. 나는 아무도 생각하지 않습니다 시작하다 근접 소트 알고리즘 사용. 당신은 단지 완전한 종류를 수행하는 코드로 시작합니다 (선택한 프로그래밍 언어가 sort 기능이 아니라 기능 nearsort 기능), 그리고 당신이 종류가 너무 오래 걸렸다는 것을 경험적으로 발견하면, 당신은 당신의 데이터가 당신의 데이터를 질문하기 시작할 것입니다 진짜 완전히 분류되어야하며 근처에 서리를 사용하는 것을 고려하십시오.

기본적으로 프로그램에서 심각한 병목 현상이라는 정렬을 처음 발견하지 못한다면 거의 정렬을 사용하는 것을 고려하지 않습니다.