정렬 된 연결 목록 집합 정렬

Question

다음과 같은 문제에 대한 고급 고성능 솔루션을 찾고 있습니다.

256 개의 링크 된 목록이 있습니다.

• 각 목록에는 정렬 순서를 정의하는 데 사용되는 정수가 들어있는 동일한 유형의 개체가 포함되어 있습니다. 모든 목록에서
• 모든 번호는 고유
각각의 개별 목록이 단일 상승이 256 원 연결리스트에서 모든 개체의 목록을 주문 만들 것입니다 방법이 숫자

으로 오름차순으로 정렬됩니다

? 나는 그것을 무력화시키지 않고 몇 가지 다른 아이디어를 갖고 싶다.하지만 이것은 표준적이고 최적의 해결책이있는 문제 중 하나 인 것처럼 보인다.

Answer 1

256 개의 연결된 목록 각각의 "최상위"항목을 보유하는 우선 순위 대기열을 사용할 수 있습니다. 이 "최상위"항목은 결과 목록에 삽입되도록 예약 된 항목입니다. 이 방법은, 그냥, 우선 순위 큐에서 가장 작은 요소를 가지고 당신의 결과로 큐에 삽입하고, 우선 순위 큐에 그 다음 요소를 삽입 할 수 있습니다

# Preprocessing: 
result = list.new() 
queue = priority_queue.new() 

foreach (list in lists): 
    queue.push(list.first()) 

# Main loop: 
while (not queue.empty()): 
    node = queue.pop() 
    result.insert(node) 
    if (node.next() != null): 
     queue.push(node.next()) 

Answer 2

개별 목록이 이미 정렬되어 있다면, 그것의 merge algorithm의 직접 신청. 즉, 모든 머리를 비교하고 가장 작은 것을 골라 내고 그 목록에서 꺼내어 출력 목록에 넣으십시오. 모든 소스 목록이 비어있을 때까지 반복하십시오.

편집 : Konrad의 우선 순위 대기열 (heap)은 훨씬 더 우아하고 확장 가능한 솔루션이지만 256 개의 입력 목록은 너무 적어 간단한 비교가 더 빠를 수도 있습니다.

Answer 3

각 목록을 위의 목록 128과 병합하면됩니다. (결과적으로 128 개의 목록이 생성됨)
그런 다음 각 목록을 위에있는 목록 64와 병합하십시오. (결과적으로 64 개의 목록이 생성됨)
그런 다음 각 목록을 위에있는 목록 32와 병합하십시오. (결과적으로 32 개의 목록이 생성됨)
그런 다음 각 목록을 위에있는 목록 16과 병합하십시오. (결과적으로 16 개의리스트가됩니다)
그런 다음 각리스트를 위에있는리스트 8과 병합하십시오. (결과적으로 8 개의 목록이 생성됩니다)
그런 다음 각 목록을 위에있는 목록 4와 병합하십시오. (결과적으로 4 개의 목록이 생성됨)
그런 다음 각 목록을 위에있는 목록 2와 병합하십시오. (결과적으로 2 개의 목록이 생성됨)
그런 다음 각 목록을 위에있는 목록 1과 병합하십시오. (결과는 1 목록)
(위의 경우 루프를 사용할 수 있음).

Answer 4

이 목록의 기간은 밝히지 않지만 모두 동시에 RAM에 맞다고 가정합니다. 내가 시도 할 첫 번째 일은 모두 함께 추가하고 내 환경의 내장 정렬 루틴을 호출하는 것입니다. 구현하기 쉽고 테스트에 오래 걸리지 않습니다. 그것이 허용 가능한 성능을 제공하지 못한다면 Konrad Rudolph가 제공 한 우선 순위 큐 병합으로 진행할 것입니다.