정렬 된 링크 된 목록의 정렬 세트

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

개별 목록이 이미 정렬 된 경우 병합 알고리즘. 한마디로 : 모든 헤드를 비교하고 가장 작은 것을 골라 목록에서 꺼내어 출력 목록으로 밀어 넣으십시오. 모든 소스 목록이 비어있을 때까지 반복하십시오.

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

Answer 3

각 목록을 위의 목록 128과 병합하십시오. (128 목록으로 결과)
그런 다음 각 목록을 위의 목록 64와 병합하십시오. (64 목록으로 결과)
그런 다음 각 목록을 위의 목록 32와 병합하십시오. (32 목록으로 결과)
그런 다음 각 목록을 위의 목록과 병합하십시오. (16 개 목록으로 결과)
그런 다음 각 목록을 위의 목록 8과 병합하십시오. (8 목록으로 결과)
그런 다음 각 목록을 위의 목록 4와 병합하십시오. (4 개의 목록으로 결과)
그런 다음 각 목록을 위의 목록 2와 병합하십시오. (2 목록으로 결과)
그런 다음 각 목록을 위의 목록 1과 병합하십시오. (1 목록으로 결과)
(위의 루프를 사용할 수 있습니다).

Answer 4

당신은이 목록이 얼마나 오래 걸리는지 말하지 않지만, 나는 그들이 모두 RAM에 동시에 적합하다고 생각합니다. 내가 시도 할 첫 번째는 모두 함께 추가하고 환경의 내장 정기를 부르는 것입니다. 구현하기 쉽고 테스트하는 데 시간이 오래 걸리지 않습니다. 그것이 수용 가능한 성능을 제공하지 않았다면, 나는 Konrad Rudolph가 제공 한 우선 순위 대기열 병합을 가지고 갈 것입니다.